数据结构（三）：栈
2018-02-11 本文已影响52人
聪明的奇瑞
栈概念
- 栈是仅在表尾（栈顶）进行插入和删除操作的线性表，是后进先出的线性表，简称 LIFO 结构，不含任何元素的栈称为空栈
- 栈的插入操作也叫做进栈，栈的删除操作也叫做出栈
yQOsp.png
栈（stack）的抽象
- Data（数据元素）：同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系
- 基本操作
| 方法 | 描述 |
|---|---|
| InitStack(*S) | 初始化操作，建立一个空栈 S |
| DestoryStack(*S) | 销毁一个栈 |
| ClearStack(*S) | 清空栈 |
| StackEmpty(S) | 若栈为空，返回true，否则false |
| GetTop(S,*e) | 若栈存在且非空，返回 S 的栈顶元素 |
| Push(*S,e) | 插入新元素 e 到栈 s 中并成为栈顶元素 |
| Pop(S,e) | 删除栈 s 中的顶元素，返回其值 |
| StackLength(S) | 返回栈 S 元素个数 |
栈的链式存储结构
- 将栈顶放在链表的头部
- 对于链表来说基本不存在栈满情况，除非没有内存可以使用
栈的进栈 push 与出栈 pop
- 进出栈操作都很简单，没有任何循环操作，时间复杂度为 O(1)
- 顺序栈与链表栈的区别是顺序栈需要确定长度，可能会存在内存空间浪费问题，但优势是存取定位方便，而链表栈每个元素都有指针域，会增加一点内存开销，但栈长度无限制
最先进栈的一定最后出栈？
- 最先进栈的不一定最后出栈，如有3个整形数字元素1、2、3依次进栈，会有以下几个出栈顺序：
- 第一种：1、2、3 进，再 3、2、1 出，出栈顺序为 321
- 第二种：1进，1出，2进，2出，3进，3出，出栈顺序为 123
- 第三种：1进、2进，2出，1出，3进，3出，出栈顺序为 213
- 第四种：1进，1出，2进，3进，3出，2出，出栈顺序为 132
- 第五种：1进、2进、2出、3进、3出，1出，出栈顺序为 231
