|
链栈 栈的链式存储结构称为链栈 链栈的类型定义 链栈是没有附加头结点的运算受限的单链表栈顶指针就是链表的头指针 链栈的类型说明如下 typedef struct stacknode{ DataType data struct stacknode *next }StackNode; typedef struct{ StackNode *top; //栈顶指针 }LinkStack; 注意 ①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身 ②若要记录栈中元素个数可将元素个数属性放在LinkStack类型中定义 链栈的基本运算 () 置栈空 Void InitStack(LinkStack *S) { S>top=NULL; } () 判栈空 int StackEmpty(LinkStack *S) { return S>top==NULL; } () 进栈 void Push(LinkStack *SDataType x) {//将元素x插入链栈头部 StackNode *p=(StackNode *)malloc(sizeof(StackNode)); p>data=x; p>next=S>top;//将新结点*p插入链栈头部 S>top=p; } () 退栈 DataType Pop(LinkStack *S) { DataType x; StackNode *p=S>top;//保存栈顶指针 if(StackEmpty(S)) Error(Stack underflow); //下溢 x=p>data; //保存栈顶结点数据 S>top=p>next; //将栈顶结点从链上摘下 free(p); return x; } () 取栈顶元素 DataType StackTop(LinkStack *S) { if(StackEmpty(S)) Error(Stack is empty) return S>top>data; } 注意 链栈中的结点是动态分配的所以可以不考虑上溢无须定义StackFull运算 |
