[数据结构笔记] 线性表

英国房地产因利率上升陷入困境房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

2023-07-27 18:01:31 来源：博客园

栈是一种后进先出（\(\text {Last In First Out,LIFO}\)）的线性表，顾名思义，后入栈的元素反而先出栈，其限制是只能在一端插入与删除，

就像下面这样，只有一端有开口，另一端则是封死的。

(相关资料图)

\[栈顶\large\begin{array}{c|c|c|c|c|c|c|c|{3}{r@{.}l|}} \hline\\text{} 0&1 & 2&3 & 4&5&6&7&...\\ \hline\end{array}栈底\]

一般的，我们将栈能插入与删除的一端称为「栈顶」，而不能进行操作的一端称为「栈底」。

同时，插入操作一般称作入栈或压栈（\(\text {push}\)），删除操作称作出栈或弹出（\(\text {pop}\)）。

一个通俗的例子是把栈看作一个盘子堆，只能在盘子堆的顶上拿取盘子，如果从中间抽出/插入盘子，盘子堆就会倒塌，碎成碎片。

接下来我们尝试一下，使用静态数组来模拟一个栈。

从增加元素开始，先考虑栈底与栈顶的位置，很明显，为了不限制栈的大小与方便，栈底设在 \(1\) 的位置比较好，

再用一个 int\(top\) 指向当前栈顶的位置

int top = 0,s[MAXN] = {0}; // 一开始栈内没有元素，所以 top 指向 0 表示当前栈内为空

当进行压栈时，新的元素会被「放」在原来的栈顶上，

此时的栈顶就是 \(top + 1\)，再赋值即可。

void push(int x){ // 传参需要压栈的元素 x    s[top ++] = x; // 压入元素}

因为只是操作了一次数组 \(s\) 与变量 \(top\)，所以时间复杂度为 \(O(1)\) 。

接下来是删除元素，可以想到将栈顶移动到原栈顶的下一个元素上，以删除原本的元素。

但是要判断一下当前 \(top\) 是否指向的是 \(0\)（空栈），否则就会收获 \(\color {Purple} {\texttt {RE}} \times \infty\)。

int pop(){    if(top)top --;    else return -1;    return 0;}

同样的，时间复杂度为 \(O(1)\)。

而还有一个常用操作就是取栈当前的元素个数，因为 \(top\) 指向了栈顶，所以 \(top\) 就是栈当前的元素个数。

int size(){    return top;}

除了可以手写栈，强大的 \(\text {STL}\) 还为我们提供了 stack关键字，用法如下：

stack s声明一个 int类型的栈 \(s\)。

s.push(x)将元素 \(x\) 压入栈 \(s\)。

s.pop()弹出栈 \(s\) 的栈顶元素。

s.empty()返回一个 bool，true表示栈 \(s\) 为空，false反之。

s.size()返回一个 int，表示栈 \(s\) 的元素个数。

更多方法见微软文档 \(\texttt{stack STL}\) 部分。

关键词：