数据结构的概念大合集03（栈）

概念大合集03

1、栈
- 1.1 栈的定义和特点
- 1.2 栈的基础操作
- 1.3 栈的顺序存储
- - 1.3.1 顺序栈
  - 1.3.2 栈空，栈满，进栈，出栈的基本思想
  - 1.3.3 共享栈
  - - 1.3.3.1 共享栈的4要素
- 1.4 栈的链式存储
- - 1.4.1 链栈的实现
  - 1.4.2 链栈的4个要素

1、栈

1.1 栈的定义和特点

栈是一种只能在一端进行插入或删除操作的线性表。在栈中，允许插入和删除操作的一端称为栈顶，另一端称为栈底。当栈为空时，称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈退栈。

栈的特点是“后进先出”，即后进栈的元素先出栈，英文表示为“last in first out，即LIFO”

1.2 栈的基础操作

函数名	函数作用
InitStack(&s)	初识化线性表，构造一个空列表
DestroyStack(&s)	销毁线性表，释放为线性表L分配的内存空间
StackEmpty(s)	判断线性表是否为空表，若L为空表，则返回true，否则返回false
Push(&s,e)	进栈，将元素e插入栈中作为栈顶元素
Pop(&s,&e)	出栈，从栈s中删除栈顶元素，并将其赋值给e
GetTop(s,&e)	取栈顶元素，返回当前的栈顶元素，并将其赋值给e。

1.3 栈的顺序存储

1.3.1 顺序栈

同线性表一样，栈里面的元素也可以采用顺序存储结构，即分配一块连续的存储空间来存放栈中的元素，并用一个变量（例如top）指向当前的栈顶元素，以反映栈中元素的变化。这种采用顺序结构的栈称为顺序栈。
请添加图片描述

1.3.2 栈空，栈满，进栈，出栈的基本思想

栈空：s->top == -1。
栈满：s->top == MaxSize - 1 (data数组的最大下标)。
进栈：先将栈顶指针top增1，然后将元素e放在栈顶指针处。
出栈：现将栈顶指针top处元素取出放在e中，然后将栈顶指针减1.

1.3.3 共享栈

顺序栈的一种特殊表现形式，将两个类型相同的栈结合起来，这样可以避免栈溢出或内存浪费的情况。
在设计共享栈的时候，由于一个数组（大小为MaxSize）有两端点，两个栈有两个栈底，让一个栈的栈底为数组的是始端，即下表为0处，另一个栈的栈底的为数组的末端，即下表为MaxSize-1处，这样，在两个栈中进栈元素时，栈顶向中间伸展。
请添加图片描述

1.3.3.1 共享栈的4要素

栈空：栈1为空top == -1;栈2为空top2 == MaxSize。
栈满：top1 == top2-1。
进栈：栈1进栈top1++ ; data[top1] = x; ==> data[++top1] = x;
栈2进栈top-- ; data[top2] = x; ==> data[–top] = x;
出栈：栈1出栈x = data[top1];top-- ; ==> x = data[top1–];
栈2出栈x = data[top2] ; top2++; ==> x = data[top2++];