大话数据结构（二）| 栈和队列

发表于

本文主要介绍栈和队列。

关键词：数据结构

栈的定义

栈（stack）是限定仅仅在栈尾进行插入和删除操作的线性表。

  • 允许插入和删除的一端称为栈顶
  • 另一端被称为栈底
  • 不含任何元素的栈称为空栈
  • 栈被称为后进先出（LIFO，Last In First Out）的线性表
  • 栈的插入操作叫做进栈，栈的删除操作叫做出栈

进栈出栈变化形式

最先进栈的元素不一定最后出栈。

栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制。在不是所有元素都进栈的情况下事先进入的元素也可以出栈，只要保证栈顶元素出栈即可。

举例：假设有三个元素1、2、3依次进栈，出栈次序如何？

  1. 1、2、3进，3、2、1出。出栈次序为321。
  2. 1进，1出，2进，2出，3进，3出。此时出栈次序为123。
  3. 1进，2进，2出，1出，3进，3出。此时出栈次序为213。
  4. 1进，1出，2进，3进，3出，2出。此时出栈次序为132。
  5. 1进，2进，2出，3进，3出，1出。此时出栈次序为231。

不可能出现312这样的答案，因为进栈的顺序是123，因此2一定先于1出栈。

抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
DATA
	元素具有相同的类型，相邻具有前驱和后继的关系
Operation
	InitStack(*S): 初始化操作，建立一个空栈S
	DestroyStack(*S): 若栈存在，则销毁它
  ClearStack(*S): 将栈清空
  StackEmpty(*S): 若栈为空，返回True；否则返回False
  GetTop(S, *e): 若栈存在且非空，用e返回S的栈顶元素
  Push(*S, e): 若栈存在，插入新元素e到栈并成为栈顶元素
  Pop(*S, *e): 删除栈S中栈顶元素, 并用e返回其值
  StackLength(S): 返回栈S的元素个数
endADT