堆栈 堆叠（stack）又称为栈或-{zh-cn:堆叠; 堆栈;，是计算机科学中的一种抽象资料型别，只允许在有序的线性资料集合的一端（称为堆叠顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆叠常用一维数组或连结串列来实现。常与另一种有序的线性资料集合伫列相提并论。 操作. 堆叠使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）： 特点. 堆栈的基本特点： 抽象定义. 以下是堆栈的VDM（""）： 函数签名： init: -> Stack push: N x Stack -> Stack top: Stack -> (N formula_1 ERROR) pop: Stack -> Stack isempty: Stack -> Boolean 此处的N代表某个元素（如自然数），而formula_1表示集合求并。 语义： top(init()) = ERROR top(push(i,s)) = i pop(init()) = init() pop(push(i, s)) = s isempty(init()) = true isempty(push(i, s)) = false 软件堆栈. 堆栈可以用数组和链表两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是codice_1结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。 这里的例程是以C语言实现的。 阵列堆叠. 存储结构. /* c3-1.h 栈的顺序存储表示 */ typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack; /* 顺序栈 */ 基本操作. /* bo3-1.c 顺序栈(存储结构由c3-1.h定义)的基本操作(9个) */ void InitStack(SqStack *S) (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; void DestroyStack(SqStack *S) free((*S).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; void ClearStack(SqStack *S) (*S).top=(*S).base; Status StackEmpty(SqStack S) if(S.top==S.base) return TRUE; else return FALSE; int StackLength(SqStack S) return S.top-S.base; Status GetTop(SqStack S,SElemType *e) if(S.top>S.base) *e=*(S.top-1); return OK; else return ERROR; void Push(SqStack *S,SElemType e) if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */ (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACK_INCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACK_INCREMENT; *((*S).top)++=e; Status Pop(SqStack *S,SElemType *e) if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; void StackTraverse(SqStack S,void(*visit)(SElemType)) while(S.top>S.base) visit(*S.base++); printf("\n"); 串列堆叠. 存储结构. /* c2-2.h 线性表的单链表存储结构 */ struct LNode ElemType data; struct LNode *next; typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */ 基本操作. /* bo3-5.c 链栈(存储结构由c2-2.h定义)的基本操作(4个) */ /* 部分基本操作是由bo2-8.cpp中的函数改名得来 */ /* 另一部分基本操作是由调用bo2-8.cpp中的函数(取特例)得来 */ typedef SElemType ElemType; /* 栈结点类型和链表结点类型一致 */ typedef LinkList LinkStack; /* LinkStack是指向栈结点的指针类型 */ Status GetTop(LinkStack S,SElemType *e) return GetElem(S,1,e); Status Push(LinkStack *S,SElemType e) return ListInsert(S,1,e); Status Pop(LinkStack *S,SElemType *e) return ListDelete(S,1,e); void StackTraverse(LinkStack S,void(*visit)(SElemType)) LinkStack temp,p=S; /* p指向栈顶元素 */ InitStack(&temp); /* 初始化临时栈temp */ while(p) Push(&temp,p->data); /* 由S栈顶到栈底，依次将栈元素入栈到temp栈 */ p=p->next; ListTraverse(temp,visit); /* 遍历temp线性表 */ 链表基本操作. /* bo2-8.c 不带头结点的单链表(存储结构由c2-2.h定义)的部分基本操作(9个) */ void InitList(LinkList *L) *L=NULL; /* 指针为空 */ void ClearList(LinkList *L) LinkList p; while(*L) /* L不空 */ p=*L; /* p指向首元结点 */ *L=(*L)->next; /* L指向第2个结点(新首元结点) */ free(p); /* 释放首元结点 */ Status ListEmpty(LinkList L) if(L) return FALSE; else return TRUE; int ListLength(LinkList L) int i=0; LinkList p=L; while(p) /* p指向结点(没到表尾) */ p=p->next; /* p指向下一个结点 */ i++; return i; Status GetElem(LinkList L,int i,ElemType *e) int j=1; LinkList p=L; if(inext; if(j==i) /* 存在第i个元素 */ *e=p->data; return OK; else return ERROR; int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0 */ int i=0; LinkList p=L; while(p) i++; if(compare(p->data,e)) /* 找到这样的数据元素 */ return i; p=p->next; return 0; Status ListInsert(LinkList *L,int i,ElemType e) int j=1; LinkList p=*L,s; if(idata=e; /* 给s的data域赋值 */ if(i==1) /* 插在表头 */ s->next=*L; *L=s; /* 改变L */ else { /* 插在表的其余处 */ while(p&&jnext; j++; if(!p) /* i大于表长+1 */ return ERROR; s->next=p->next; p->next=s; return OK; Status ListDelete(LinkList *L,int i,ElemType *e) int j=1; LinkList p=*L,q; if(i==1) /* 删除第1个结点 */ *L=p->next; /* L由第2个结点开始 */ *e=p->data; free(p); /* 删除并释放第1个结点 */ else while(p->next&&jnext; j++; if(!p->next||j>i-1) /* 删除位置不合理 */ return ERROR; q=p->next; /* 删除并释放结点 */ p->next=q->next; *e=q->data; free(q); return OK; void ListTraverse(LinkList L,void(*vi)(ElemType)) LinkList p=L; while(p) vi(p->data); p=p->next; printf("\n"); 堆栈有时候也常用来指代堆栈段。 硬件堆栈. 架构层次上的堆栈通常被用以申请和访问内存。 硬件支持. 大多数CPU都有用作堆栈指针的寄存器。