什么是栈？

我们先回顾一下我们对于队列的学习。我们对于队列的理解，是一个队伍，在队尾进入，先进先出。
那么我们应该通过什么来理解栈呢？
你可以想象一堆叠在一起的书构成“书塔”，由下往上叠放。每次放书都放在最上面那层书的上面，如果你想取书，由于书的重力你很难从“书塔”的中间取出来书，所以你只能从这一叠书的最上面取书。所以我们每次取书都是取得最上面得一本。你可以理解为一个单头的队列，只有队首，插入元素和删除元素都是针对队首进行的。
这种性质使得栈中先插入的元素会在后插入元素的“下方”,但是出栈是从所谓“上面”出栈，所以这就使得先插入的元素的出栈顺序在后插入的元素之后，所以栈具有先进后出的性质。

栈的代码实现

1
2
3

const int MAXN = 10000007;
int stack[MAXN];
int p = 0; //栈顶指针

不难理解，依然类似于队列，我们通过数组和指针实现栈。这里的MAXN指的是栈最大支持的大小;
接下来是操作代码的实现

void push(int a)
{
	if(p >= MAXN) cout<<"Stack overflow（栈溢出）";
	else stack[p++] = x;
}
void pop()
{
	if(p == 0) cout<<"Stack is empty（栈为空）";
	else p--;
}

你可以理解下一个插入的元素为stack[p],如果弹出过一次，我们通过更改stack[p-1]来实现
所以弹出栈顶用p--来减少指针的值，使得下一次插入的元素通过赋值顶替已经删除的栈顶来实现栈顶的删除。
比如3 5 1 7 指针为4,弹出一次操作进行后指针变为3，弹出的元素是stack[3]，下一次插入元素插入到stack[3],通过后续新的元素的插入来实现之前已经删除的栈顶指针索引下的数值的变化（删除）。
所以这就是为什么MAXN在队列中表示最大插入次数，因为他的元素没有经过实际意义上数组中的删除，只是滚动过去实现队列的模拟。
但在栈中是实际上通过删除来实现的，所以在栈中MAXN指的是栈的大小。

接着给出访问栈顶的代码

int top()
{
	if(p == 0)
	{
		cout<<"Stack is empty（栈为空）";
		return -1; //指的是栈为空这个概念 
	}
	else return stack[p - 1];
}

这样我们就实现了栈的基本操作。和队列一样，栈也有对应的STL中的栈,接下来给出通过STL操作的栈的用法。

<stack> : 栈所需要的头文件 
stack<int> s : 建立一个栈s,其内部元素类型为int
s.push(k) : 将元素k压入栈s
s.pop() : 弹出栈顶元素
s.top() : 访问栈定元素
s.size() : 查询栈s的元素个数
s.empty() : 查询s是否为空

写在最后

栈的实现相对于队列比较简单，这里不给出具体的例题了，大家可以自行拟定一些数据进行模拟。在栈的基础之上，我们还有一种数据结构——单调栈，它将在后续的进阶数据结构中讲到,敬请期待

栈（stack）

什么是栈？

栈的代码实现

写在最后