data structure

1. 栈的基本概念

1.1 栈的定义

只允许在一端进行插入或删除操作的线性表 。

栈顶(Top):线性表允许进行插入和删除的那一端 。

栈底(Bottom):固定的一端 。

栈的特性是后进先出(Last in First Out ,LIFO)

注意 :数据结构应该功逻辑结构 、存储结构和对数据的运算三方面着手 。

1.2 栈的基本操作

InitStack(&S) :初始化一个空栈 S 。

StackEmpty(S) :判断一个栈是否为空 ,若栈 S 为空则返回 true ,否则返回 false

Push(&S, x) :进栈

Pop(&S, &x) :出栈

GetTop(S,&x) :读栈顶元素

ClearStack(&S) :销毁栈 。

2. 栈的顺序存储结构

2.1 顺序栈的实现

利用一组地址连续的存储单元存放自栈底到栈顶的数据元素 。

  1. top 初始化为 0
  2. 溢出时需要报错
  3. 进栈操作:栈顶+1,赋值
  4. 出栈操作:取元素,栈顶-1

2.2 顺序栈的基本运算

  1. 初始化
  2. 判栈空
  3. 进栈
  4. 出栈
  5. 读栈顶元素

2.3 共享栈

利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸 。

共享栈是为了更有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被占满时才发生上溢 。存取时间复杂度均为 O(1) ,所以对存取效率没有什么影响 。

3. 栈的链式存储结构

采用链式存储的栈称为链栈,可以不需要头结点,不存在栈满上溢 。

4. 习题