文档介绍：3 栈和队列
信息学院暑期培训
栈和队列
学****目标
掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。
熟练掌握循环队列和链队列的基本操作实现算法。
理解递归算法执行过程中栈的状态变化过程。
重点和难点
栈和队列是在程序设计中被广泛使用的两种线性数据结构,本章的学****重点是掌握这两种结构的特点,以便能在应用问题中正确使用。
知识点
顺序栈、链栈、循环队列、链队列
栈和队列
栈和队列是在程序设计中被广泛使用的两种线性数据结构。
与线性表相比,它们的插入和删除操作受更多的约束和限定,故又称为限定性的线性表结构。
线性表允许在表内任一位置进行插入和删除;
栈只允许在表尾一端进行插入和删除;
队列只允许在表尾一端进行插入,在表头一端进行删除。
3 栈和队列
栈在计算机的实现有多种方式:
◆硬堆栈:利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限,但速度很快;
◆软堆栈:这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上,又有动态方式和静态方式两种。
本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。
栈
1 栈的概念
栈(Stack):是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top):允许进行插入、删除操作的一端,又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom):是固定端,又称为表头。
空栈:当表中没有元素时称为空栈。
栈的基本概念
栈的基本概念
设栈S=(a1,a2,…an),则a1称为栈底元素,an为栈顶元素,如图3-1所示。
栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。
图3-1 顺序栈示意图
a1
a2
ai
an
⋯⋯
⋯⋯
bottom
top
进栈(push)
出栈(pop)
栈的示意图
特点
先进后出(FILO)
后进先出(LIFO)
a1
a2
a3
入栈
出栈
栈底
栈顶
插入:入栈、进栈、压栈
删除:出栈、弹栈
栈顶
栈顶
栈的逻辑结构
例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种?
栈底
栈顶
a
b
栈顶
c
栈顶
情况1:
栈的逻辑结构
栈底
栈顶
a
b
栈顶
c
栈顶
出栈序列:c
出栈序列:c、b
出栈序列:c、b、a
例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种?
情况1:
栈的逻辑结构
栈底
栈顶
a
b
栈顶
出栈序列:b
情况2:
例:有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种?