重学数据结构003——栈的基本操作及实现(链式存储)
1.栈的概念
?? ?展示只允许在其一端进行插入语删除操作的表。从定义上来说，栈其实也是线性表，因此栈也具备大多数线性表所具备的基本操作。但是，从定义上可知，栈在进行插入、删除操作时，只能在一端进行操作，这一端成为栈顶(top)。
?? ?栈最核心的操作主要是：进栈(Push)、出栈(Pop)、返回栈顶元素(Top)。 此外，栈还判断栈是否为空、创见栈、清空栈等操作。
?? ?既然是线性表，那么栈从实现方式来说主要有两种：顺序存储实现(数组)、链式存储实现(链表)。下面是链式存储实现方式下，站的数据结构定义：
typedef?struct?Node?*PtrToNode;?typedef?PtrToNode?Stack;?typedef?struct?Node?{?????int?Element;?????PtrToNode?Next;?};?? ?栈的基本操作：
//判断栈是否为空?int?IsEmpty(Stack?S);?//创见栈?Stack?CreateStack();?//销毁栈?void?DisposeStack(Stack?S);?//清空栈?void?MakeEmpty(Stack?S);?//进栈?void?Push(int?X,Stack?S);?//返回栈顶元素?int?Top(Stack?S);?//出栈?void?Pop(Stack?S);?
?? ?下面是一个完整的关于栈的基本操作的例子：?
#include?<stdio.h>?#include?<stdlib.h>??typedef?struct?Node?*PtrToNode;?typedef?PtrToNode?Stack;?typedef?struct?Node?{?????int?Element;?????PtrToNode?Next;?};??int?IsEmpty(Stack?S);?Stack?CreateStack();?void?DisposeStack(Stack?S);?void?MakeEmpty(Stack?S);?void?Push(int?X,Stack?S);?int?Top(Stack?S);?void?Pop(Stack?S);??//判断栈是否为空?int?IsEmpty(Stack?S)?{?????return?S->Next?==?NULL;?}?//创建链栈?Stack?CreateStack()?{?????Stack?S?=?malloc(sizeof(struct?Node));?????if(S?==?NULL)?????{?????????printf("No?enough?memory!");?????????return?NULL;?????}?????S->Next?=?NULL;?????MakeEmpty(S);?????return?S;?}??void?MakeEmpty(Stack?S)?{?????if(S?==?NULL)?????{?????????printf("Use?CreateStack?First!");?????}?????else?????{?????????while(!IsEmpty(S))?????????{?????????????Pop(S);?????????}?????}?}??void?Push(int?X,Stack?S)?{?????PtrToNode?Tmp;?????Tmp?=?malloc(sizeof(struct?Node));?????if(Tmp?!=?NULL)?????{?????????Tmp->Element?=?X;?????????Tmp->Next?=?S->Next;?????????S->Next?=?Tmp;?????}?????else?????{?????????printf("Out?of?space!");?????}?}??void?Pop(Stack?S)?{??????????if(IsEmpty(S))?????{?????????printf("The?Stack?is?Empty!");?????}?????else?????{?????????PtrToNode?Tmp?=?S->Next;?????????S->Next?=?Tmp->Next;?????????free(Tmp);?????}?}??int?Top(Stack?S)?{?????if(IsEmpty(S))?????{?????????printf("The?stack?is?empty!");?????????return?0;?????}?????else?????{?????????return?S->Next->Element;?????}?}??int?main(void)?{?????Stack?S?=?CreateStack();?????int?i;?????for(i?=?0;?i?<?5;?i++)?????{?????????Push(i,S);?????}??????while(!IsEmpty(S))?????{?????????printf("%d\n",Top(S));?????????Pop(S);?????}?????return?0;?}???