堆栈

抽象定義

以下是堆疊的VDM（Vienna Development Method）：
函式簽章：
  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都有用作堆疊指標的暫存器。