栈

大话数据结构中有这样一段开场白

早先由于子弹质量问题，军官们都爱用左轮手枪，而非弹夹式手枪

因为弹夹式手枪，子弹叠在一起，如果当中有一颗是卡住了的臭弹， 那么就得卸下弹夹把臭蛋取下来，才能用下面的子弹；而左轮手枪如果遇到臭弹，转到下一颗就解决了；在战场上，子弹卡壳还得卸下来再装上去，也许这点时间，生命就没了

其实，这种弹夹构造就类似栈(stack )

栈的定义

本质也是线性表

栈(stack )：限定仅在表尾进行插入和删除操作的线性表

栈顶(top)：允许插入和删除的一端

栈底(bottom)：栈顶对应的另一端

空栈： 不含任何数据元素的栈

栈又称为**后进先出(Last In First Out)**的线性表，简称LIFO结构

插入操作，叫作进栈，也称压栈、入栈

删除操作，叫作出栈

进栈出栈变化形式

讨论一下进栈顺序为123的出栈顺序（全部进出一遍要6步 ）

不可能是312的原因是3都入栈了，12肯定就入栈了，所以2一定先出栈

1是最先进栈的，但不一定是最后出栈的，所以先进后出这种情况并不一定

栈的顺序存储结构

顺序存储就是一组地址连续的存储单元，依次存放自栈底到栈 的数据元素

1
2
3
4
5
6

typedef int SElemType; //SElemType 类型根据实际情况而定 
typedef struct {
SElemType *base; // 在栈构造之前和销毁之后,base的值为NULL 
SElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间,以元素为单位
}SqStack;

栈的链式存储结构

链式存储就是一组地址不连续的存储单元，通过指针前驱指向后继

栈只有栈顶做插入删除，由于单链表有头指针，而栈顶指针是必须的，所以比较好的办法是把栈顶放在单链表的头部；对于栈而言，也就不需要头结点了

但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL

1
2
3
4
5
6
7
8
9
10

typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode, * LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;

栈的基本操作