本篇介绍数据结构-栈
思维导图
栈
-
定义
是限制仅在表的一端进行插入和删除运算的线性表。
-
属性
-
通常称插入、删除的这一端为 栈顶(Top),另一端称为 栈底(Bottom)。
-
当表中没有元素时称为 空栈
-
栈为 后进先出(Last In First Out)的线性表,简称为 LIFO 表。
-
-
顺序栈-基本运算
- 置空栈
void InitStack (SeqStack *s){ s-top=-1; // 置空顺序栈,由于c语言数组下标是从0开始,所以栈中元素亦从0开始 // 存储,因此空栈时栈顶指针不能是0,而只能是-1 }
- 判栈空
int StackEmpty (SeqStack *S){ return S->top===-1; }
- 判栈满
int StackFull(SeqStack *S){ return S->top==StackSize-1; }
- 进栈
void Push(SeqStack *S,DataType x){ if(StackFull(s)){ printf("stack overflow"); }else{ S->top=S->top+1; S->data[S->top]=x; } }
- 退栈
DataType Pop(SeqStack *S){ if(StackEmpty(S)){ printf("stack underflow"); exit(0); }else{ return S->data[S->top-1] } }
- 取栈顶元素
DataType GetTop(SeqStack *S){ if(StackEmpty(S)){ printf("stack empty"); exit(0); }else{ return S->data[S->data]; } }
-
链栈-基本运算
- 判栈空
int StackEmpty(LinkStack top){ return top==null; }
- 进栈
LinkStack Push(LinkStack top,DataType x){ StacKNode *p; p=(StackNode *)malloc(sizeof (StacKNode)); p->data=x; p-next=top; top=p; return top; }
- 退栈
LinkStack Pop(LinkStack top, DataType *x){ SrackNode *p=top; if(StackEmpty(top)){ printf("stack empty"); exit(0); }else{ *x=p->data; top=p->next; free(p); return top; } }
- 取栈顶元素
DataType GetTop(LinkStack top){ if(StackEmpty(top)){ printf("stack empty"); exit(0); }else{ return top->data; } }