基础数据结构---栈

顺序表实现

一、栈类的声明

栈是一种特殊的线性表，可以由顺序表来实现，也可以由链表来实现，这节课，我们采用顺序表来实现栈。

#include <iostream>#include <stdexcept>using namespace std;template<typename 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) template<typename 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() 是一个公共成员函数，用于获取栈中元素的数量。

二、栈的扩容

template<typename T>void Stack<T>::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) template<typename T> 是模板声明的一部分，表示 resize 函数是一个通用的模板函数，可以用于处理任何类型的元素 T。

(2) 这一行计算了新的容量，并将其赋值给 newCapacity 变量。新的容量是当前容量的两倍。

(3) 创建一个新的数组 newData，用于存储新扩容后的元素。新数组的大小为新的容量。

(4) 这是一个循环，用于将当前栈中的元素从旧数组 data 复制到新数组 newData 中。

(5) 释放了旧数组 data 所占用的内存空间。

(6) 将 newData 数组赋值给 data，使其成为栈的新存储数组。

(7) 更新了栈的容量为新的容量。

三、栈的销毁

template<typename T>Stack<T>::~Stack() { // (1)delete[] data; // (2)}

(1) 这是析构函数的声明，用于在对象销毁时执行清理操作。

(2) 释放了动态分配的数组 data 所占用的内存空间。delete[] 用于释放动态分配的数组内存。

四、入栈

template<typename T>void Stack<T>::push(T element) {if (size == capacity) { // (1)resize();}data[size++] = element; // (2)}

(1) 如果栈的当前大小 size 等于容量 capacity，则调用 resize 函数进行扩容操作。代表如果栈已满，需要先进行扩容以增加栈的容量。

(2) 将元素 element 赋值给栈数组 data 的 size 位置，并将 size 的值增加 1，以表示栈中元素的数量增加。

五、出栈

template<typename T>T Stack<T>::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 数组中栈顶元素的值。

六、获取栈顶元素

template<typename T>T Stack<T>::top() const {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[size - 1]; // (1)}

(1) 如果栈不为空，返回 data 数组中最后一个元素的值，即栈顶元素。

七、栈的完整源码

#include <iostream>
#include <stdexcept>using namespace std;template<typename 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;
};template<typename T>
void Stack<T>::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;
}template<typename T>Stack<T>::~Stack() {delete[] data;
}template<typename T>void Stack<T>::push(T element) {if (size == capacity) {resize();}data[size++] = element;
}template<typename T>T Stack<T>::pop() {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[--size];
}template<typename T>
T Stack<T>::top() const {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[size - 1];
}template<typename T>
int Stack<T>::getSize() const {return size;
}int main() {Stack<int> 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 <stdexcept>using namespace std;
template<typename 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 是一个公共成员函数，用于获取栈的大小。

二、栈的扩容

由链表实现栈时，每次如果是新生成的结点，则不涉及到像顺序表那样的扩容操作。

三、栈的销毁

template<typename T>Stack<T>::~Stack() { // (1)while (head != NULL) { // (2)Node* temp = head;head = head->next;delete temp;}
}

(1) 这是 Stack 类的析构函数的实现代码。它的作用是在对象销毁时，释放动态分配的节点内存。

(2) 不断循环访问栈中的元素，每次取出栈顶元素，存储到临时变量 temp 中，并且弹出栈顶，并且利用 delete 将弹出的元素进行内存释放，直到栈为空为止。

四、入栈

template<typename T>
void Stack<T>::push(T element) {Node* newNode = new Node(element); // （1）newNode->next = head; // （2）head = newNode; // （3）++size; // （4）
}

(1) 创建了一个新的 Node 对象，并将传入的元素赋值给该对象的数据成员。通过使用 new 操作符动态分配了内存来存储新的节点。

(2) 将新节点的 next 指针指向当前的头节点。这样，新节点就被添加到了栈的头部。

(3) 将头节点的指针更新为新节点，使新节点成为栈的新头部。

(4) 将栈的大小计数器加 1，以反映栈中元素数量的增加。

五、出栈

template<typename T>T Stack<T>::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 变量传递返回值。

六、获取栈顶元素

template<typename T>T Stack<T>::top() const {if (head == NULL) {throw std::underflow_error("Stack is empty"); // (1)}return head->data; // (2)
}

(1) 如果栈为空，那么获取栈顶的这个操作是不合法的，抛出异常。

(2) 如果栈不为空，head 指针的 data 域，即栈顶元素。

七、栈的完整源码

#include <iostream>
#include <stdexcept>using namespace std;template<typename T>class 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;
};template<typename T>Stack<T>::~Stack() {while (head != NULL) {Node* temp = head;head = head->next;delete temp;}
}template<typename T>void Stack<T>::push(T element) {Node* newNode = new Node(element);newNode->next = head;head = newNode;++size;
}template<typename T>T Stack<T>::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;
}template<typename T>T Stack<T>::top() const {if (head == NULL) {throw std::underflow_error("Stack is empty");}return head->data;
}template<typename T>int Stack<T>::getSize() const {return size;
}int main() {Stack<int> 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 << bitset<10>(n).to_string().substr(10 - (int)log2(n) - 1) << endl;}return 0;
}

这段代码中，我们使用了bitset库，它可以方便地将整数转换为固定长度的二进制字符串。由于题目中指出0 < n < 1000，我们知道最大值999的二进制表示是1111100111，这需要10个二进制位来表示。所以我们创建了一个大小为10的bitset。

然而，当使用bitset<10>(n).to_string()时，它总是返回一个长度为10的字符串，即使对于较小的数字也是如此，比如1会被表示为0000000001。为了去除前导零，我们计算了数字n在二进制下的实际位数（即log2(n)+1），然后从结果字符串中切片得到正确的二进制表示。

需要注意的是，对于n=1的情况，log2(n)会给出0，所以我们对log2(n)的结果进行了类型转换并加1，确保我们不会尝试访问无效的索引。对于n=0的情况，题目已经说明不会出现，因此无需特别处理。

另外，如果想要更简单的实现，可以忽略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:vector<int> reverseBookList(ListNode* head) {stack<int> stk;while (head) {stk.push(head->val);head = head->next; }vector<int> ans;while (!stk.empty()) {ans.push_back(stk.top());stk.pop();}return ans;}
};

4. 回文链表

class Solution {
public:bool isPalindrome(ListNode* head) {stack<int> 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. **找到链表的中间节点**：使用快慢指针（Floyd's 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. 矩阵中最大的矩形

接雨水

直方图的水量

最大子矩阵