栈的顺序存储表示
栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。静态顺序栈实现简单，但不能根据需要增大栈的存储空间；动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。
栈的动态顺序存储表示
采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
- 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
- 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。
- 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;
- 结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。
栈的静态顺序存储表示
采用静态一维数组来存储栈。
- 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。
- 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。
- 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。
- 结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。
若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。
/*! * \file 栈的顺序存储实现.cpp * * \author ranjiewen * \date 2017/03/17 11:13 * * */#include#include typedef int Position;typedef int ElemType;#define ERROR NULL#define MAXSIVE 100struct SNode{ ElemType *Data; /*存储元素的数组，动态分配内存*/ Position Top; /*栈顶元素数组下标*/ int MaxSize; // 堆栈最大容量};typedef struct SNode* Stack;Stack CreateStack(int MaxSize){ Stack S = (Stack)malloc(sizeof(struct SNode)); S->Data = (ElemType*)malloc(MaxSize*sizeof(ElemType)); S->Top = -1; //顺序存储结构时，表示空 S->MaxSize = MaxSize; return S;}bool IsFull(Stack S){ return (S->Top == S->MaxSize - 1);}bool Push(Stack S, ElemType x){ if (IsFull(S)) { printf("堆栈满.\n"); //栈满时可以再申请空间 return false; } else { S->Data[++(S->Top)] = x; return true; }}bool IsEmpty(Stack S){ return (S->Top == -1);}ElemType Pop(Stack S){ if (IsEmpty(S)) { printf("堆栈为空。\n"); return ERROR; } else { return S->Data[(S->Top)--]; }}int main(){ struct SNode *S = CreateStack(MAXSIVE); for (int i = 9; i >= 0;i--) { Push(S,i); } for (int i = 0; i < S->Top;i++) { printf("%d ", S->Data[i]); } printf("\n"); Pop(S); Pop(S); for (int i = 0; i < S->Top; i++) { printf("%d ", S->Data[i]); } printf("\n"); return 0;}
存储栈的链式表示
栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。记住栈顶指针Top只能在表尾，在表头时删除操作不行。
/*! * \file 线性结构栈的链式存储实现.cpp * * \author ranjiewen * \date 2017/03/17 14:27 * * */#include#include typedef int ElementType;#define ERROR NULLtypedef struct SNode *PtrToSNode;struct SNode { ElementType Data; PtrToSNode Next;};typedef PtrToSNode Stack;Stack CreateStack(){ /* 构建一个堆栈的头结点，返回该结点指针 */ Stack S; S = (Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S;}bool IsEmpty(Stack S){ /* 判断堆栈S是否为空，若是返回true；否则返回false */ return (S->Next == NULL);}bool Push(Stack S, ElementType X){ /* 将元素X压入堆栈S */ PtrToSNode TmpCell; TmpCell = (PtrToSNode)malloc(sizeof(struct SNode)); if (!TmpCell) { printf("申请结点失败!"); exit(-1); } TmpCell->Data = X; //相当于在表头插入 TmpCell->Next = S->Next; S->Next = TmpCell; return true;}ElementType Pop(Stack S){ /* 删除并返回堆栈S的栈顶元素 */ PtrToSNode FirstCell; ElementType TopElem; if (IsEmpty(S)) { printf("堆栈空"); return ERROR; } else { FirstCell = S->Next; TopElem = FirstCell->Data; S->Next = FirstCell->Next; free(FirstCell); return TopElem; }}int main(){ PtrToSNode stack; stack = CreateStack(); for (int i = 9; i >= 0;i--) { Push(stack, i); } PtrToSNode pTemp; for (pTemp = stack->Next; pTemp != NULL;pTemp=pTemp->Next) //链式不能用++ { printf("%d ", pTemp->Data); } printf("\n"); Pop(stack); Pop(stack); for (pTemp = stack->Next; pTemp != NULL; pTemp=pTemp->Next) { printf("%d ", pTemp->Data); } printf("\n");}
reference：