数据结构——栈

栈基础知识

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

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

插入一般称为进栈（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)--;
	}
}