堆栈

维基百科,自由的百科全书
跳转至: 导航搜索
中国大陸 堆栈、栈
臺灣 堆疊
港澳 堆疊
堆疊的简单示意图

堆栈英语:stack)又稱為堆叠,是计算机科學中一種特殊的串列形式的抽象資料型別,其特殊之處在於只能允許在鏈結串列或陣列的一端(稱為堆疊頂端指標,英语:top)進行加入数据(英语:push)和輸出数据(英语:pop)的運算。另外栈也可以用一維数组連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列

由於堆疊資料結構只允許在一端進行操作,因而按照後進先出(LIFO, Last In First Out)的原理運作。

操作[编辑]

堆疊資料結構使用兩種基本操作:推入(push)和彈出(pop):

  • 推入:將數據放入堆疊的頂端(陣列形式或串列形式),堆疊頂端top指標加一。
  • 彈出:將頂端數據資料輸出(回傳),堆疊頂端資料減一。

特点[编辑]

栈的基本特点:

  1. 先入后出,后入先出。
  2. 除头尾节点之外,每个元素有一个前驱,一个后继。

抽象定义[编辑]

以下是堆栈的VDM(Vienna Development Method英语Vienna Development Method):[1]

函数签名:

  init: -> Stack
  push: N x Stack -> Stack
  top: Stack -> (N U ERROR)
  pop: Stack -> Stack
  isempty: Stack -> Boolean

此处的N代表某个元素(如自然数),而U表示集合求交。

语义:

  top(init()) = ERROR
  top(push(i,s)) = i
  pop(init()) = init()
  pop(push(i, s)) = s
  isempty(init()) = true
  isempty(push(i, s)) = false

软件堆栈[编辑]

陣列堆疊[编辑]

堆栈可以用链表数组两种方式实现,一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事,所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头。这里的例程是以数组实现的。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <stdbool.h>
 4 #define stack struct Stack
 5 #define STACK_POP_ERR 42
 6 
 7 // 堆疊資料結構 堆栈数据结构
 8 struct Stack {
 9     int val[10]; // 陣列空間
10     int top;     // 堆疊頂端指標(栈顶)
11 };
12 // 檢查堆疊是否為空
13 bool empty(stack *stk) {
14     return stk->top == 0;
15 }
16 // 推入資料
17 void push(stack *stk, int x) {
18     stk->top = stk->top + 1;
19     stk->val[stk->top] = x;
20 }
21 // 彈出并返回資料
22 int pop(stack *stk) {
23     if (empty(stk))
24         return STACK_POP_ERR; // 不能彈出
25     else {
26         stk->top = stk->top - 1;
27         return stk->val[stk->top + 1];
28     }
29 }
30 int main() {
31     // 宣告并初始化資料結構空間
32     stack stk;
33     stk.top = 0;
34     // 推入四个
35     push(&stk, 3);
36     push(&stk, 4);
37     push(&stk, 1);
38     push(&stk, 9);
39     // 弹出三个
40     printf("%d ", pop(&stk));
41     printf("%d ", pop(&stk));
42     printf("%d ", pop(&stk));
43     return 0;
44 }

串列堆疊[编辑]

 1 // 链栈的结构定义
 2 typedef struct {
 3     SLink top; // 棧頂指針
 4     int len​​gth; // 棧中元素個數
 5 } Stack;
 6 
 7 // 构造空栈 S
 8 void InitStack (Stack &S) {
 9     S.top = NULL; // 設棧頂指針的初值為"空"
10     S.length = 0; // 空棧中元素個數為0
11 }
12 // 如果指针反过来从栈底到栈顶的话,删除栈顶元素时,为修改其前驱指针,需要从栈底一直找到栈顶。
13 
14 // 在棧頂S 之上插入元素e為新的棧頂元素,並返回成功與否
15 bool Push (Stack &S, ElemType e) {
16     p = new LNode; // 建新的結點
17     if (!p) // 存儲分配失敗
18         return false;
19     p->data = e;
20     p->next = S.top;// 鏈接到原來的棧頂
21     S.top = p; // 移動棧頂指針
22     ++S.length; // 棧的長度增1
23 }
24 // 在链栈的类型定义中设立“栈中元素个数”的成员是为了便于求得栈的长度。
25 
26 // 刪除S 棧頂且以e 返回其數值,返回成功與否
27 bool Pop (Stack &S, SElemType &e) {
28     if (!S.top)
29         return false;
30     else {
31         e = S.top -> data; // 返回棧頂元素
32         q = S.top;
33         S.top = S.top -> next; // 修改棧頂指針
34         --S.length; // 棧的長度減1
35         delete q; // 釋放被刪除的結點空間
36         return true;
37     }
38 }

堆棧有時候也常用來指代堆棧段

硬件堆栈[编辑]

架构层次上的堆栈通常被用以申请和访问内存。

硬件支持[编辑]

大多数CPU都有用作堆栈指针的寄存器。

堆疊的應用[编辑]

参考文献[编辑]

  1. ^ Jones: "Systematic Software Development Using VDM"

参见[编辑]