数据结构的概念大合集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++];
1.4 栈的链式存储
即采用链式存储的栈称为链栈，但是与链表不同的是，链栈只有单链栈，不存在双链栈，所以将单链栈也直接称为链栈。
1.4.1 链栈的实现
采用带头结点的单链表来实现栈链
1.4.2 链栈的4个要素
- 栈空：s->next == NULL;
- 栈满：因为是链栈，只有在内存溢出的情况下，才会出现满栈的情况，所以一般情况不考虑；
- 进栈：新建一个结点存放元素e（由p指向它），将结点p插入头结点之后。
- 出栈：取出首结点的data值并将其删除
注：
本文将主要探讨栈的概念，其中提及的各个函数操作将在后续的文章中详细展示，敬请读者期待。
上一篇文章
数据结构的概念大合集02（线性表）
下一篇文章
数据结构的概念大合集04（队列）