本页使用了标题或全文手工转换

堆栈

维基百科,自由的百科全书
(重定向自堆疊
跳到导航 跳到搜索
「堆栈」的各地常用別名
中国大陸 堆栈、栈
港臺 堆疊
堆疊的简单示意图

堆疊英语:stack)又稱為堆叠,是计算机科學中的一種抽象資料型別,只允許在有序的線性資料集合的一端(稱為堆疊頂端,英语:top)進行加入数据(英语:push)和移除数据(英语:pop)的運算。因而按照後進先出(LIFO, Last In First Out)的原理運作。

常與另一種有序的線性資料集合佇列相提並論。

堆疊常用一維数组連結串列來實現。

操作[编辑]

堆疊使用兩種基本操作:推入(压栈,push)和彈出(弹栈,pop):

  • 推入:將資料放入堆疊頂端,堆疊頂端移到新放入的資料。
  • 彈出:將堆疊頂端資料移除,堆疊頂端移到移除後的下一筆資料。

特点[编辑]

堆栈的基本特点:

  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结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头

这里的例程是以C語言实现的。

陣列堆疊[编辑]

 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 #include <stdio.h>
  2 #include <conio.h>
  3 #include <stdlib.h>
  4 
  5 #define elemType int							/* 链栈元素数据类型,以整型为例 */
  6 #define SNODE_SIZE sizeof (struct sNode)		/* 链栈结点空间大小 */
  7 
  8 #define status int	/* 状态型变量 */
  9 #define OVERFLOW -1	/* 内存溢出状态码 */
 10 #define ERROR 0		/* 错误状态码 */
 11 #define OK 1		/* 正确状态码 */
 12 
 13 /* 链栈结点存储结构 */
 14 typedef struct sNode {
 15 	elemType data;
 16 	struct sNode *next;
 17 } sNode, *sNodePtr;
 18 
 19 /* 链栈存储结构 */
 20 typedef struct linkStack {
 21 	sNodePtr top; /* 栈顶指针 */
 22 } linkStack;
 23 
 24 /* 初始化 */
 25 /* 操作结果:构造一个带头结点的空链栈S */
 26 void initStack (linkStack *S) {
 27 	S->top = (sNodePtr) malloc (SNODE_SIZE); /* 产生头结点,栈顶指针指向此头结点 */
 28 	if (!S->top) /* 内存分配失败 */
 29 		exit (OVERFLOW);
 30 	S->top->next = NULL;
 31 }
 32 
 33 /* 销毁 */
 34 /* 初始条件:链栈S已存在。操作结果:销毁链栈S */
 35 void destroyStack (linkStack *S) {
 36 	sNodePtr p, q;
 37 	
 38 	p = S->top; /* p指向S的头结点 */
 39 	while (p) {
 40 		q = p->next; /* q指向p的下一个结点 */
 41 		free (p); /* 回收p指向的结点 */
 42 		p = q; /* p移动到下一个结点 */
 43 	} /* 直到没有下一个结点 */
 44 }
 45 
 46 /* 清空 */
 47 /* 初始条件:链栈S已存在。操作结果:将S重置为空栈 */
 48 void clearStack (linkStack *S) {
 49 	sNodePtr p, q;
 50 	
 51 	p = S->top->next; /* p指向栈的第一个结点 */
 52 	while (p) {
 53 		q = p->next; /* q指向p的下一个结点 */
 54 		free (p); /* 回收p指向的结点 */
 55 		p = q; /* p移动到下一个结点 */
 56 	}  /* 直到没有下一个结点 */
 57 	
 58 	S->top->next = NULL;
 59 }
 60 
 61 /* 判断链栈是否为空 */
 62 /* 初始条件:链栈S已存在。操作结果:若S为空链栈,则返回TRUE,否则返回FALSE */
 63 status stackIsEmpty (linkStack *S) {
 64 	return S->top->next == NULL;
 65 }
 66 
 67 /* 求链栈长度 */
 68 /* 初始条件:链栈S已存在。操作结果:返回S中数据元素个数 */
 69 int stackLength (linkStack *S) {
 70     int i = 0;
 71     sNodePtr p;
 72 	
 73 	p = S->top->next; /* p指向栈的第一个结点 */
 74 	while (p) { /* 未到栈尾 */
 75 		i++;
 76 		p = p->next;
 77     }
 78     
 79     return i;
 80 }
 81 
 82 /* 获取栈顶元素 */
 83 /* 初始条件:链栈S已存在。操作结果:当栈不为空时,将栈顶元素其值赋给e并返回OK,否则返回ERROR */
 84 status getTopElem (linkStack *S, elemType *e) {
 85 	sNodePtr p;
 86 	
 87 	if (stackIsEmpty (S))
 88 		return ERROR;
 89 	
 90 	p = S->top->next; /* p指向栈的第一个结点 */
 91 	*e = p->data;
 92 	
 93 	return OK;
 94 }
 95 
 96 /* 入栈 */
 97 /* 操作结果:在S的栈顶插入新的元素e */
 98 status push (linkStack *S, elemType e) {
 99 	sNodePtr p;
100 	
101 	p = (sNodePtr) malloc (SNODE_SIZE); /* 产生新结点 */
102 	if (!p) /* 内存分配失败 */
103 		exit (OVERFLOW);
104 	
105 	p->data = e;
106 	p->next = S->top->next; /* 将新结点链接到原栈顶 */
107 	S->top->next = p; /* 栈顶指向新结点 */
108 }
109 
110 /* 出栈 */
111 /* 操作结果:删除S的栈顶元素,并由e返回其值 */
112 status pop (linkStack *S, elemType *e) {
113 	sNodePtr p;
114 	
115 	if (stackIsEmpty (S))
116 		return ERROR;
117 	
118 	p = S->top->next; /* p指向链栈的第一个结点 */
119 	*e = p->data; /* 取出数据 */
120 	S->top->next = p->next;
121 	free (p); /* 删除该结点 */
122 	
123     if (S->top == p) /* 栈为空 */
124     	S->top->next = NULL;
125     
126     return OK;
127 }
128 
129 /* 打印栈内容 */
130 /* 初始条件:链栈S已存在。操作结果:当栈不为空时,打印栈内容并返回OK,否则返回ERROR */
131 status printStack (linkStack *S) {
132 	sNodePtr p;
133 	
134 	if (stackIsEmpty (S))
135 		return ERROR;
136 	
137 	p = S->top->next;
138 	while (p) {
139 		printf ("%d\t", p->data);
140 		p = p->next;
141 	}
142 	putchar ('\n');
143 	
144 	return OK;
145 }

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

硬件堆栈[编辑]

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

硬件支持[编辑]

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

堆疊的應用[编辑]

参考文献[编辑]

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

参见[编辑]