栈（stack）又称为堆栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆栈常用一维数组或链表来实现。常与另一种有序的线性资料集合队列相提并论。
特点
- 后进先出（LIFO, Last In First Out）。
- 除头尾节点之外，每个元素有一个前驱，一个后继。
存储结构
- 顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。
- 链栈：采用链式存储结构实现的栈，通常用单链表来实现。
由于顺序栈和顺序表一样，受到最大空间容量的限制，虽然可以在“满员”时重新分配空间扩大容量，但工作量较大，应该尽量避免。因此在应用程序中无法预估栈可能达到的最大容量时，应该使用链栈。
操作
此处，我们以栈的数组实现为例，创建栈 S，当 S.top = 0 时，栈中不包含任何元素，即栈是空（empty）的。如果试图对一个空栈执行弹出操作，则称栈下溢（underflow），这通常是一个错误。如果 S.top 超过了栈最多可容纳的元素个数 n，则称栈上溢（overflow）。
初始化
STACK-INIT(S, MAXSIZE)
# 初始化一个最大容量为 MAXSIZE 的数组空间
# 在初始化链栈时，无需分配空间
# 此处省略了存储分配失败的判断
s = Make(S, MAXSIZE)
s.top = 0 # 将 top 初始化为 0
return s
判断是否为空
STACK-EMPTY(S)
if S.top == 0
return TRUE
else return FALSE
入栈
PUSH(S,x)
# 此处省略了栈是否已满的判断
S.top = S.top + 1 # 将元素压入栈顶，栈顶指针加一
S[S.top] = x
出栈
POP(S)
if STACK-EMPTY(S) # 判断栈是否为空，若空返回错误
return error "underflow"
else S.top = S.top - 1 # 栈顶指针减一，栈顶元素出栈
return S[S.top + 1]
可以看出，顺序栈操作的执行时间都为 O(1)。
参考资料
- 《算法导论》第三版 殷建平 等译
- 《数据结构》（C 语言第二版）严蔚敏 等编著
- 维基百科
网友评论