堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。
常与另一种有序的线性数据集合队列相提并论。
堆栈常用一维数组或链表来实现。
堆栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：
堆栈的基本特点：
以下是堆栈的VDM（）：
函数签名：
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 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 = 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;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 }