网站优化 毕业设计,中国100强软件公司排名公布,广州免费高速,网站建设捌金手指下拉八顺序表实现
一、栈类的声明
栈是一种特殊的线性表#xff0c;可以由顺序表来实现#xff0c;也可以由链表来实现#xff0c;这节课#xff0c;我们采用顺序表来实现栈。
#include iostream#include stdexceptusing namespace std;templatetypename …顺序表实现
一、栈类的声明
栈是一种特殊的线性表可以由顺序表来实现也可以由链表来实现这节课我们采用顺序表来实现栈。
#include iostream#include stdexceptusing namespace std;templatetypename T // (1)class Stack { // (2)private:T *data; // (3)int size; // (4)int capacity; // (5)void resize(); // (6)public:Stack() : data(new T[10]), size(0), capacity(10) {} // (7)~Stack(); // (8)void push(T element); // (9)T pop(); // (10)T top() const; // (11)int getSize() const; // (12)};
(1) templatetypename T 这是一个模板声明表明 Stack 类是一个通用的模板类可以用于存储任何类型的元素 T。
(2) 这是 Stack 类的声明它表示一个栈的数据结构。
(3) data 是一个私有成员变量用于存储栈中的元素。它是一个指向类型为 T 的指针。
(4) size 是一个私有成员变量用于记录栈中元素的数量。
(5) capacity 这是一个私有成员变量用于记录栈的容量。
(6) resize() 是一个私有成员函数用于在栈容量不足时进行扩容。
(7) Stack() 是构造函数用于初始化栈的成员变量。它创建一个新的栈并分配一个容量为 10 的数组来存储元素。
(8) ~Stack() 是析构函数用于释放栈所占用的内存。
(9) void push(T element) 这是一个公共成员函数用于将一个新元素压入栈顶。
(10) T pop() 是一个公共成员函数用于从栈顶弹出一个元素。
(11) T top() 是一个公共成员函数用于获取栈顶的元素但不弹出它。
(12) int getSize() 是一个公共成员函数用于获取栈中元素的数量。
二、栈的扩容
templatetypename Tvoid StackT::resize() { // (1)int newCapacity capacity * 2; // (2)T *newData new T[newCapacity]; // (3)for (int i 0; i size; i) {newData[i] data[i]; // (4)}delete[] data; // (5)data newData; // (6)capacity newCapacity; // (7)}
resize 函数用于在栈的容量不足时进行扩容操作。它创建了一个新的更大的数组并将旧数组的元素复制到新数组中然后更新栈的指针和容量。这样可以确保栈能够容纳更多的元素而不会发生溢出。
(1) templatetypename T 是模板声明的一部分表示 resize 函数是一个通用的模板函数可以用于处理任何类型的元素 T。
(2) 这一行计算了新的容量并将其赋值给 newCapacity 变量。新的容量是当前容量的两倍。
(3) 创建一个新的数组 newData用于存储新扩容后的元素。新数组的大小为新的容量。
(4) 这是一个循环用于将当前栈中的元素从旧数组 data 复制到新数组 newData 中。
(5) 释放了旧数组 data 所占用的内存空间。
(6) 将 newData 数组赋值给 data使其成为栈的新存储数组。
(7) 更新了栈的容量为新的容量。
三、栈的销毁
templatetypename TStackT::~Stack() { // (1)delete[] data; // (2)}
(1) 这是析构函数的声明用于在对象销毁时执行清理操作。
(2) 释放了动态分配的数组 data 所占用的内存空间。delete[] 用于释放动态分配的数组内存。
四、入栈
templatetypename Tvoid StackT::push(T element) {if (size capacity) { // (1)resize();}data[size] element; // (2)}
(1) 如果栈的当前大小 size 等于容量 capacity则调用 resize 函数进行扩容操作。代表如果栈已满需要先进行扩容以增加栈的容量。
(2) 将元素 element 赋值给栈数组 data 的 size 位置并将 size 的值增加 1以表示栈中元素的数量增加。
五、出栈
templatetypename TT StackT::pop() {if (size 0) {throw std::underflow_error(Stack is empty); // (1)}return data[--size]; // (2)}
(1) 检查栈是否为空。如果栈为空即 size 为 0则抛出一个 std::underflow_error 异常提示 Stack is empty。
(2) 如果栈不为空通过 --size 减小栈的大小并返回 data 数组中栈顶元素的值。
六、获取栈顶元素
templatetypename TT StackT::top() const {if (size 0) {throw std::underflow_error(Stack is empty);}return data[size - 1]; // (1)}
(1) 如果栈不为空返回 data 数组中最后一个元素的值即栈顶元素。
七、栈的完整源码
#include iostream
#include stdexceptusing namespace std;templatetypename T
class Stack {
private:T* data;int size;int capacity;void resize();
public:Stack() : data(new T[10]), size(0), capacity(10) {}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};templatetypename T
void StackT::resize() {int newCapacity capacity * 2;T* newData new T[newCapacity];for (int i 0; i size; i) {newData[i] data[i];}delete[] data;data newData;capacity newCapacity;
}templatetypename TStackT::~Stack() {delete[] data;
}templatetypename Tvoid StackT::push(T element) {if (size capacity) {resize();}data[size] element;
}templatetypename TT StackT::pop() {if (size 0) {throw std::underflow_error(Stack is empty);}return data[--size];
}templatetypename T
T StackT::top() const {if (size 0) {throw std::underflow_error(Stack is empty);}return data[size - 1];
}templatetypename T
int StackT::getSize() const {return size;
}int main() {Stackint st;st.push(4);st.push(7);st.push(13);cout st.top() endl;st.push(17);cout st.top() endl;st.pop();st.pop();cout st.top() endl;cout st.getSize() endl;return 0;}
C链表实现
一、栈类的声明
栈是一种特殊的线性表可以由顺序表来实现也可以由链表来实现这节课我们采用链表来实现栈。
#include iostream
#include stdexceptusing namespace std;
templatetypename T // (1)class Stack {
private:struct Node { // (2)T data;Node* next;Node(T d) : data(d), next(NULL) {}};Node* head; // (3)int size; // (4)
public:Stack() : head(NULL), size(0) {} // (5)~Stack(); // (6)void push(T element); // (7)T pop(); // (8)T top() const; // (9)int getSize() const; // (10)};
(1) 这是一个模板声明表示这个类是一个通用的类模板可以用于处理各种不同类型的元素。
(2)这是一个结构体定义用于表示栈中的节点。每个节点包含一个数据成员 data 和一个指向下一个节点的指针 next。
(3) head 是一个私有成员变量用于保存栈的头节点指针。
(4) size 是一个私有成员变量用于保存栈的大小。
(5) Stack() 是构造函数用于初始化栈。它将头节点指针设置为 NULL并将栈的大小设置为 0。
(6) ~Stack() 是析构函数用于释放栈中分配的内存。
(7) void push(T element) 是一个公共成员函数用于将一个元素压入栈顶。它创建一个新的节点并将元素赋值给节点的数据成员然后将新节点插入到栈的头部。
(8) T pop() 是一个公共成员函数用于从栈顶弹出一个元素。它检查栈是否为空如果不为空则删除栈顶节点并返回节点的数据成员。
(9) T top() const 是一个公共成员函数用于获取栈顶元素但不弹出它。它检查栈是否为空如果不为空则返回栈顶节点的数据成员。
(10) int getSize() const 是一个公共成员函数用于获取栈的大小。
二、栈的扩容
由链表实现栈时每次如果是新生成的结点则不涉及到像顺序表那样的扩容操作。
三、栈的销毁
templatetypename TStackT::~Stack() { // (1)while (head ! NULL) { // (2)Node* temp head;head head-next;delete temp;}
}
(1) 这是 Stack 类的析构函数的实现代码。它的作用是在对象销毁时释放动态分配的节点内存。
(2) 不断循环访问栈中的元素每次取出栈顶元素存储到临时变量 temp 中并且弹出栈顶并且利用 delete 将弹出的元素进行内存释放直到栈为空为止。
四、入栈
templatetypename T
void StackT::push(T element) {Node* newNode new Node(element); // 1newNode-next head; // 2head newNode; // 3size; // 4
}
(1) 创建了一个新的 Node 对象并将传入的元素赋值给该对象的数据成员。通过使用 new 操作符动态分配了内存来存储新的节点。
(2) 将新节点的 next 指针指向当前的头节点。这样新节点就被添加到了栈的头部。
(3) 将头节点的指针更新为新节点使新节点成为栈的新头部。
(4) 将栈的大小计数器加 1以反映栈中元素数量的增加。
五、出栈
templatetypename TT StackT::pop() {if (head NULL) {throw std::underflow_error(Stack is empty); // (1)}T result head-data; // (2)Node* temp head; // (3)head head-next; // (4)delete temp; // (5)--size; // (6)return result; // (7)
}
(1) 如果头节点为空即栈为空则抛出一个 std::underflow_error 异常提示 Stack is empty。
(2) 将头节点的数据成员赋值给 result 变量准备返回弹出的元素。
(3) 将头节点的指针赋值给 temp 变量用于后续删除头节点。
(4) 将头节点的 next 指针赋值给头节点本身从而将头节点从链表中移除。
(5) 调用 delete 操作符释放 temp 所指向的节点内存。
(6) 将栈的大小计数器减 1以反映弹出操作后栈中元素数量的减少。
(7) 返回弹出的元素通过 result 变量传递返回值。
六、获取栈顶元素
templatetypename TT StackT::top() const {if (head NULL) {throw std::underflow_error(Stack is empty); // (1)}return head-data; // (2)
}
(1) 如果栈为空那么获取栈顶的这个操作是不合法的抛出异常。
(2) 如果栈不为空head 指针的 data 域即栈顶元素。
七、栈的完整源码
#include iostream
#include stdexceptusing namespace std;templatetypename Tclass Stack {
private:struct Node {T data;Node* next;Node(T d) : data(d), next(NULL) {}};Node* head;int size;
public:Stack() : head(NULL), size(0) {}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};templatetypename TStackT::~Stack() {while (head ! NULL) {Node* temp head;head head-next;delete temp;}
}templatetypename Tvoid StackT::push(T element) {Node* newNode new Node(element);newNode-next head;head newNode;size;
}templatetypename TT StackT::pop() {if (head NULL) {throw std::underflow_error(Stack is empty);}T result head-data;Node* temp head;head head-next;delete temp;--size;return result;
}templatetypename TT StackT::top() const {if (head NULL) {throw std::underflow_error(Stack is empty);}return head-data;
}templatetypename Tint StackT::getSize() const {return size;
}int main() {Stackint st;st.push(4);st.push(7);st.push(13);cout st.top() endl;st.push(17);cout st.top() endl;st.pop();st.pop();cout st.top() endl;cout st.getSize() endl;return 0;}
题集
1. 进制转换 2. Bitset
#include iostream
#include bitset
using namespace std;int main() {int n;// 循环读取输入直到文件结束while (cin n) {// 使用 bitset 将整数转换为二进制字符串// 因为 0 n 1000, 所以我们最多需要 10 位来表示 n 的二进制形式 (2^10 1024 1000)cout bitset10(n).to_string().substr(10 - (int)log2(n) - 1) endl;}return 0;
}
这段代码中我们使用了bitset库它可以方便地将整数转换为固定长度的二进制字符串。由于题目中指出0 n 1000我们知道最大值999的二进制表示是1111100111这需要10个二进制位来表示。所以我们创建了一个大小为10的bitset。
然而当使用bitset10(n).to_string()时它总是返回一个长度为10的字符串即使对于较小的数字也是如此比如1会被表示为0000000001。为了去除前导零我们计算了数字n在二进制下的实际位数即log2(n)1然后从结果字符串中切片得到正确的二进制表示。
需要注意的是对于n1的情况log2(n)会给出0所以我们对log2(n)的结果进行了类型转换并加1确保我们不会尝试访问无效的索引。对于n0的情况题目已经说明不会出现因此无需特别处理。
另外如果想要更简单的实现可以忽略bitset和log2而使用循环方式构建二进制字符串或者使用标准库中的std::stoi与std::string结合自定义逻辑去除前导零。
3. 图书整理 I
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vectorint reverseBookList(ListNode* head) {stackint stk;while (head) {stk.push(head-val);head head-next; }vectorint ans;while (!stk.empty()) {ans.push_back(stk.top());stk.pop();}return ans;}
};4. 回文链表
class Solution {
public:bool isPalindrome(ListNode* head) {stackint stk;ListNode *temp head; // 使用临时指针来遍历链表// 将所有节点值压入栈中while (temp) {stk.push(temp-val);temp temp-next;}// 重置指针到链表头部开始比较temp head;while (temp) {if (stk.top() ! temp-val) return false; // 如果栈顶元素和当前节点值不同则不是回文stk.pop();temp temp-next;}return true; // 所有节点值匹配链表是回文}
}; 暂时看看就好 使用双指针方法检查链表是否为回文可以在O(n)时间复杂度和O(1)空间复杂度下完成。这种方法不需要额外的数据结构来存储节点值。以下是具体步骤 1. **找到链表的中间节点**使用快慢指针Floyds Cycle Detection Algorithm慢指针每次移动一步而快指针每次移动两步。当快指针到达链表末尾时慢指针将位于链表的中间位置。 2. **反转链表的后半部分**从中间节点开始反转链表的后半部分。 3. **比较前后两部分**将链表分为两部分前半部分和反转后的后半部分逐个比较两个部分对应的节点值是否相等。如果所有对应节点的值都相等则链表是回文否则不是。 4. **恢复链表可选**如果需要保持链表的原始状态可以再次反转链表的后半部分以恢复原状。 5. **返回结果**根据比较的结果返回链表是否为回文。 下面是使用双指针方法实现的代码 class Solution {
public:bool isPalindrome(ListNode* head) {if (!head || !head-next) return true;// Step 1: Find the middle of the linked list using slow and fast pointersListNode *slow head, *fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;}// Step 2: Reverse the second half of the list starting from slowListNode *prev nullptr, *curr slow, *nextTemp;while (curr) {nextTemp curr-next;curr-next prev;prev curr;curr nextTemp;}// Step 3: Compare the first half and reversed second halfListNode *firstHalf head, *secondHalf prev;while (secondHalf) { // secondHalf will be shorter or equal in length to firstHalfif (firstHalf-val ! secondHalf-val) return false;firstHalf firstHalf-next;secondHalf secondHalf-next;}// Step 4: Restore the list (optional)curr prev; // prev now points to the new head of the reversed second halfprev nullptr;while (curr) {nextTemp curr-next;curr-next prev;prev curr;curr nextTemp;}return true;}
}; 这段代码实现了上述的每个步骤并且在最后可以选择性地恢复链表的原始顺序。通过这种方式我们既能够有效地检查链表是否为回文又能够在检查结束后保持链表的初始状态。 5. 括号的最大嵌套深度
class Solution {
public:int maxDepth(const std::string inputString) {int stringLength inputString.length(), maximumDepth 0;for (int index 0, currentDepth 0; index stringLength; index) {if (inputString[index] () currentDepth;else if (inputString[index] )) currentDepth--;maximumDepth std::max(maximumDepth, currentDepth);}return maximumDepth;}
};
6. 有效的括号
普通栈
剑指 Offer 06. 从尾到头打印链表
反转链表
括号的最大嵌套深度
有效的括号
最长有效括号
剑指 Offer II 027. 回文链表
回文链表
回文链表
棒球比赛
剑指 Offer II 036. 后缀表达式
比较含退格的字符
三合一
验证栈序列
剑指 Offer 31. 栈的压入、弹出序列
从先序遍历还原二叉树
单调栈
最小栈
栈的最小值
剑指 Offer 30. 包含min函数的栈
剑指 Offer II 038. 每日温度
用栈实现队列
剑指 Offer 09. 用两个栈实现队列
化栈为队
最后 K 个数的乘积
去除重复字母
不同字符的最小子序列
柱状图中最大的矩形
剑指 Offer II 039. 直方图最大矩形面积
最大矩形
剑指 Offer II 040. 矩阵中最大的矩形
接雨水
直方图的水量
最大子矩阵
