数据结构——栈

栈基础知识

栈是只能在某一端插入和删除的特殊线性表。

进行删除和插入的一端称为栈顶，另一端称为栈底。

插入一般称为进栈（push），删除则称为退栈（pop）。

栈也称为后进先出表（LIFO表）。

一个栈可以用定长为n的数组s来表示，用一个栈指针top指向栈顶。

若top=0，表示栈空，若top=n，表示栈满。
			进栈时top+1，退栈时top-1。
			当top<0时为下溢。
			栈指针在运算中永远指向栈顶。

栈的抽象数据类型

ADT 栈 （stack） Data 元素具有相同的类型，相邻元素具有前驱和后继关系。 Operation InitStack(*S):初始化操作，建立一个空栈S。 DestroyStack(*S)：若栈存在，则销毁它。 ClearStack(*S)：将栈清空。 StackEmpty(S)：若栈为空，反会true，否则返回false。 GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素。 Push(*S,e)：若栈S存在，插入新元素e到栈S中并成功称为栈顶元素。 Pop(*S,*e)：删除栈S中栈顶元素，并用e返回其值。 StackLength(S)：返回栈S的元素个数。 endADT

栈基础算法

简单进栈（push）算法

1.若top>=n，则给出溢出信息，做出错处理。
		2.top++。
		3.s[top]=x，结束。

void push(int s[],int* top,int* x) { if(*top==n) printf("overflow"); else { (*top)++; s[*top]=*x; } } 

简单退栈（pop）算法

1.top<=0，则给出下溢信息，做出错处理。
		2.x=s[top]。
		3.top--，结束。

void pop(int s[],int* pop,int* y) { if(*top==0) printf("underflow"); else { *y=s[*top]; (*top)--; } }