顺序表实现
一、栈类的声明
栈是一种特殊的线性表，可以由顺序表来实现，也可以由链表来实现，这节课，我们采用顺序表来实现栈。
#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
3. 图书整理 I
4. 回文链表
5. 括号的最大嵌套深度
6. 有效的括号