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

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

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

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

栈的定义

本质也是线性表

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

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

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

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

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

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

删除操作,叫作出栈

进栈出栈变化形式

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

第一步 第二步 第三步 第四步 第五步 第六步
1进 2进 3进 3出 2出 1出
1进 2进 2出 3进 3出 1出
1进 2进 2出 1出 3进 3出
1进 1出 2进 2出 3进 3出
1进 1出 2进 3进 3出 2出

不可能是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;

栈的基本操作

方法 作用
InitStack( &s) 构造一个空栈s
DestroyStack( &S) 初始条件:栈s已存在
操作结果:销毁栈s
ClearStack( &S) 初始条件:栈s已存在
操作结果:清空栈
StackEnpty(S) 初始条件:栈s已存在
操作结果:判断栈是否为空,是返回TRUE,否则FALSE
StackLength(S) 初始条件:栈s已存在
操作结果:返回栈的长度
GetTop(s, &e) 初始条件:栈S已存在且非空
操作结果;用e返回s的栈顶元素
Push(&s, e) 初始条件:栈S已存在
操作结果:插人元素e为新的栈顶元素