请注意，本文编写于 1838 天前，最后修改于 1838 天前，其中某些信息可能已经过时。
今天先来两个简单的数据结构——栈和队列吧。
栈 (Stack)
栈是一种线性结构，与数组相比，栈对应的操作是数组的子集。
它只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。
Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。
栈的实现
函数说明
| 函数 | 说明 | 复杂度 |
|---|---|---|
| void push(int data) | 向栈中加入元素 | 平均O(1) |
| int pop() | 弹出栈顶元素 | 平均O(1) |
| int top() | 查看栈顶元素 | O(1) |
| int size() | 获取栈中元素个数 | O(1) |
| bool empty() | 判断栈是否为空 | O(1) |
push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。
栈可以用数组和链表来实现，这里我用链表写了一遍。
链表实现
#include <list>
using namespace std;
//我之前写过链表了，所以这里直接用C++里面的list吧
class Stack
{
private:
list<int> value;
public:
/*入栈，出栈*/
void push(int data) { value.push_back(data); }
int pop()
{
int tmp = top();
value.pop_back();
return tmp;
}
/*栈信息*/
int top() { return value.back(); }
int size() { return value.size(); }
bool empty() { return value.empty(); }
};
