栈

定义:是将线性表的插入和删除运算限制为仅在表尾进行。是一种限定性的后进先出(LIFO)的线性表。

• 栈顶(Top): 表中允许进行插入、删除操作的一端。

• 栈底(Bottom)：表的另一端。

• 空栈:栈中没有元素，栈顶指向栈底。

• 进栈(入栈)Push: 栈的插入操作。

• 出栈(退栈)Pop: 栈的删除操作。

顺序栈

定义: 用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。

存储结构定义如下:

typedef struct{
	SElemType *base;	//栈底指针
	SElemType *top;	    //栈顶指针，始终指向栈顶元素的下一个位置
	int stacksize;		//栈可使用的最大容量
｝SqStack;

基本操作: 初始化、取栈顶元素、空栈、入栈、出栈。

链栈

定义: 用链式存储结构实现的栈，实际上就是一个单链表。

存储结构定义如下:

typedef struct StackNode
{
	SElemType data;		//节点数据域
	struct StackNode *next;		//节点指针域
｝StackNode,*LinkStackPtr;		//结点指针域

typedef struct LinkStack
{
	LinkStackPtr top;		//栈顶指针
	int count;				//栈中元素个数
｝LinkStack;

基本操作:初始化、取栈顶元素、空栈、入栈、出栈。

注意：头插法入栈

栈的运用

常见的运用:数制转换、括号匹配问题、表达式求值、递归的消除。

数制转换

假设要将十进制数转换为d进制数

算法描述如下:

1. X = N mod d (其中mod为求余元算),所得余数入栈。
2. N = N div d (其中div为整除运算)。
3. 重复上述步骤，直到N等于0。

具体实现代码

括号匹配问题