文档介绍：第一章数据结构
栈和队列
栈
定义:只允许在线性表的一端进行插入和删除的线性表。
相关术语:
(1)栈顶:允许插入与删除的一端称为栈顶。栈顶指针top初值指向栈底,插入新的栈顶元素时,top增1 ,栈顶指针始终指向栈顶元素的下一个位置。
(2)栈底:不允许插入与删除的一端称为栈底。栈底指针base始终指向栈底位置。
(3)入栈:栈的插入操作(往栈中插入一个元素)
(4)出栈:栈的删除操作(从栈中删除一个元素)
(5)栈空: top=base
(6)栈满: top=m(m为栈最大容量)
栈示意图:
原则:先进后出或后进先出
栈顶元素总是最后入栈,而最先出栈的
栈底元素总是最先入栈,而最后出栈的
堆栈操作
A
进
B
A
进
C
A
进
A
出
D
A
进
A
出
出
初始
出栈元素顺序: B → C → D → A
A
出
出
栈的两种存储结构
顺序存储结构:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素
链式存储结构:也称可利用栈。用于收集计算机存储器中所有空闲存储空间。
顺序栈:顺序存储结构的栈称为顺序栈。
链栈:链式存储结构栈称为链栈。
基本运算:入栈、退栈与读栈顶元素
(1)入栈
步骤:
栈顶指针top加1
新元素插入到栈顶指针指向位置
(2)出栈
步骤:
栈顶元素赋给一个指定的变量
栈顶指针top减1
(3)读栈顶元素
概念:将栈顶元素赋给一个指定变量
注意:不删除栈顶元素,栈顶指针不会改变
注意: 栈顶指针指向存储空间最后一个位置时,栈已满,不能再入栈。称为栈“上溢”错误.
栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误
举例
top
base
空栈
top
base
A入栈
A
top
base
BCDEF入栈
A
B
C
D
E
F
top
base
FEDC退栈
A
B
队列
定义:指允许在一端插入,而在另一端进行删除的线性表。
相关术语(5个):
(1)队尾:允许插入的一端称为队尾。,始终指向队尾元素的下一个位置。
(2)队头:允许进行删除的一端称为队头。,始终指向队头元素。
(3)入队列:队列插入操作(进队列)
(4)出队列:队列的删除操作(退队列)
(5)空队列:队列中无数据元素
原则:先进先出
队头元素总是最先进队列的,也总是最先出队列
队尾元素总是最后进队列,也是最后出队列
队列结构示意图:队列Q=(a1,a2, …, an )
a1
ai
a2
an
…
…
队头
队尾
退队
入队
定义:用链表表示的队列。P29
空队列时,
新元素入队时插在头结点之后,
删除一个元素时,。。
空队列
具有n个元素的队列
a1
a2
an
^
a1入队列
a1
^
a2入队列
a1
a2
^
a1出队列
a1
a2
^