堆栈

抽象定义

以下是堆栈的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都有用作堆栈指针的寄存器。