栈¶
引入¶
什么是栈呢？我们可以用生活中的物品来模拟：比如你有一个存钱罐，每一次都只能往里面放一块钱，当你需要取钱的时候，也只能一次在上面取一块钱。这就是一个最简单的栈。
栈是 OI 当中一个非常基础的数据结构，它具有先进后出（first in last out, FILO）的特性，即最后放入栈中的元素，会第一个被取出。注意这里讲的不是操作系统底层上的栈空间，而是一种名为“栈”的数据结构。
那么，我们该怎么用一段代码来模拟这个存钱罐呢？
数组模拟¶
类的定义：
template <class Ty>
class Stack {
protected:
int *a = new int[1 << 20], c = 0;
public:
Stack() = default;
};
我们可以用一个数组 \(a\) 来模拟这个存钱罐，\(c\) 就表示当前存钱罐的大小，那么我们只需要在 \(c+1\) 的位置上放上新元素，并把 \(c\) 加一，一个压入操作就完成了。
public: void push(const Ty &x) {
a[++c] = x;
}
那么，我们如何取出存钱罐中的元素呢？我们只需要把 \(c\) 减一，就取出了一个元素。因为 \(c\) 表示的是当前存钱罐的大小，所以 \(c\) 减一之后，我们就取出的 \(a_c\) 就是上一个元素了。
public: void pop() {
c--;
}
至于获取栈顶，我们直接返回 \(a_c\) 就行了，毕竟 \(c\) 表示的是当前存钱罐的大小，所以 \(a_c\) 就是栈顶元素。
public: Ty &top() {
return a[c];
}
这就是一个最简单的栈了，但是它有一个致命的缺点：如果存钱罐满了，我们只能重新开一个存钱罐，再压入新元素。
链表模拟¶
我们可以用一个链表来模拟这个存钱罐：首先，我们定义一个节点类 Node 用来存储每一个元素和下一个元素（注意这里的下一个元素其实是上一个元素，只不过用 next 来存储）
template <typename Ty>
class Node final {
public:
Ty data;
Node<Ty> *next;
Node(Ty data) : data(data), next(nullptr) {}
};
然后我们就可以像数组一样来写 Stack 类了，注意指针的时候，搞不好会内存泄漏。
template <typename Ty>
class Stack {
protected:
Node<Ty> *head;
int size;
public:
Stack() : head(nullptr), size(0) { }
void push(Ty data) {
Node<Ty> *newNode = new Node<Ty>(data);
newNode->nexTy = head;
head = newNode;
size++;
}
Ty pop() {
if (isEmpty()) {
throw out_of_range("Stack is empty");
}
Node<Ty> *temp = head;
head = head->next;
size--;
Ty data = temp->data;
delete temp;
return data;
}
bool isEmpty() {
return size == 0;
}
int getSize() {
return size;
}
};
STL 实现¶
在标准头文件 stack 当中，STL 已经帮我们实现了栈，我们只需要引入头文件 #include <stack> 就可以直接使用了。std::stack 的具体使用方式可以看语言基础板块。