第三章栈及队列.doc

第三章 栈和队列
3.1栈
对于线性表（a1，a2，…，an），合理的插入位置i：1<=i<=n+1，合理的删除位置i：1<=i<=n，如果限定插入和删除的位置，得到两种新的线性结构——栈和队列。
3.1.1栈的逻辑结构
1.栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。
理解栈的定义有以下要点：
（1）线性结构：栈元素具有线性（即前驱后继）关系
（2）限制操作：限制了线性表插入和删除的位置
（3）单向延伸性：栈底是固定的，栈顶随着插入和删除操作的进行而变化
（4）插入：也称进栈、压栈、入栈
删除：也称出栈、弹栈
（5）先进后出性：如图所示，栈中有三个元素，插入元素的顺序是a1、a2、a3，删除元素时只能删除a3 ，即最后入栈的元素被最先弹出
注意：栈只是对线性表插入和删除的位置进行了限制，并没有限定插入和删除操作进行的时间。

a1
a2

a3
入栈 出栈
栈顶

栈底
3.1.2栈的顺序存储结构及实现
1.栈的顺序存储结构——顺序栈
顺序栈本质上是顺序表的简化，唯一需要确定的是用数组的哪一端表示栈底。
通常把数组中下标为0的一端作为栈底，同时附设top指示栈顶元素在数组中的位置。

a1

4
3
2
top 1
0
注意：top起到指示栈顶元素的作用，但top的值是栈顶元素在数组中的下标，因此，top也称为游标。
如下图，设存储元素的数组长度为StackSize，则栈空的判定条件是top=-1；栈满的判定条件是top=StackSize-1
a5
a4

a3
a2

a1

a1

a1
top

top 0

2.顺序栈的实现
#define STACK_INIT_SIZE 100；
#define STACKINCREMENT 10；
typedef struct{
SElemType *base；
SElemType *top；
int stacksize；
}Sqstack；
说明：base为栈底指针，若base=NULL则表示栈不存在；
top为栈顶指针，当top=base时可作为栈空的标记。
3.入栈操作
入栈时，只需将栈顶指针top加1，其操作示意如图

a2

a1

a1

a3
a2

a1

a1

top
top
入栈

Status push(Sqstack &S, SElemType e){
if(S.top-S.base>=S.stacksize)
{S.base=(ElemType*)realloc(S.base,(S.stacksize+ STACKINCREMENT)*sizeof(ElemType))；
if(!S.base)exit(OVERFLOW)；
S.top=S.base+S.stacksize；
S.stacksize+= STACKINCREMENT；
}
*S.top++=e；
return OK；
}
4.出栈
出栈时，只需将栈顶指针top减1，操作示意图：

a2

a1

a1

a3
a2

a1

a1
出栈

top
top

Status pop(Sqstack &S, SElemType &e){
if(S.top==S.base)return ERROR
e=*--S.top；
return OK；
}
3.1.3栈的链式存储结构及实现
1.栈的链接存储结构——链栈
讲授思路：
l 因为只能在栈顶执行插入和删除的操作，显然以单链表的头部做栈顶是最方便的，头指针即为栈顶指针。
l 由于链栈只在头部执行操作，因此没有必要像单链表那样为了运算方便附设一个头结点。
链栈的存储示意图：
an
an-1
a1
top 栈顶

栈底
在链栈中，栈空的判定条件是top=NULL，当内存没有可用空间时才会发生栈满的情况。
链栈的入栈操作只需处理栈顶的情况：

x
ai
a1
top s
②
top ①

修改指针：
①s->next=top;
②top=s;
链栈的出栈操作只需处理栈顶的情况：

ai
a-1
a1
p
top

top

修改指针：p=top;
top=top->next;
delete p
链栈的基本操作都非常简单，时间复杂度都为O(1)。
3.1.4顺序栈和链栈的比较
当栈的使用过程中元素变化较大时，用链栈是适宜的，反之，采用顺序栈。
3.2队列
线性表（a1，a2，…，an）：插入位置i：1<=i<=n+1，
删除位置i：1<=i<=n，
栈（a1，a2，…，an）：插入和删除均限定在表尾，即插入位置为n+1；删除位置为n;
队列（a1，a2，…，an）：一端执行插入，另一端执行删除，即插入位置为n+1，删除位置为1；
3.2.1队列的逻辑结构
1.队列的定义
队列是只允许在一端进行插入，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头，如图所示：
队头
队尾
出队 入队
a1 a2 a3 a4 a5

理解队列的定义有以下要点：
（1）线性结构：相邻的元素有前驱后继关系
（2）限制操作：限制了线性表插入和删除的位置
（3）插入：也称入队、进队；删除也称出队
（4）先进先出性：如上图，有5个元素的队列，入队顺序为a1 a2 a3 a4 a5,出队的顺序依然是a1 a2 a3 a4 a5 ，即最先入队者最先出队。
应用举例：排队买票：排队系统
程序设计中：键盘缓冲区，操作系统中的作业调度等
3.2.2队列的顺序存储结构及实现
1.队列的顺序存储结构——循环队列
假设线性表有n个数据元素，顺序表要求把表中所有元素都存在数组的前n个单元。假设队列有n个元素，顺序存储的队列也应该把队列的所有元素都存在数组的前n个单元。
如果把队头元素放在数组中下标为0的一端，则入队操作的时间开销仅为O(1)，此时的入队操作相当于追加，不需要移动元素，但是出队操作的时间开销为O(n)，因此要保证剩下的n-1个元素仍然存储在数组的前n-1个单元，所有元素都要向前移动一个位置。
入队
a1 a2 a3 a1 a2 a3 a4
rear rear
出队
a1 a2 a3 a4 a2 a3 a4
rear rear
放宽队列的所有元素必须存储在数组的前n个单元这一条件，只需要队列的元素存储在数组中的连续位置。
由于队列的队头和队尾都是活动的，因此，需要设置队头、队尾两个指针，并且约定：队头指针front指向队头元素的前一位置，队尾指针rear指向队尾元素，此时入队和出队操作的时间开销都是O(1)，如图：
入队操作：
0 1 2 3 4 入队 0 1 2 3 4
a1 a2 a3
a1 a2 a3 a4

front rear front rear
出队操作：
0 1 2 3 4 出队 0 1 2 3 4
a1 a2 a3 a4
a2 a3 a4

front rear front rear
但是，这种方法带来了一个新的问题：“单向移动性”——随着队列的插入和删除操作的进行，整个队列向数组中下标较大的位置移动过去，当元素被插入到数组中下标最大的位置后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫“假溢出”。
解决假溢出的方法是将存储队列的数组看成是头尾相接的循环结构，即允许队列直接从数组中下标最大的位置延续到下标最小的位置，如下图，这通过取模操作很容易实现。队列的这种头尾相接的顺序存储结构成为循环队列。
0 1 2 3 4 解决方法 0 1 2 3 4
a3 a4 a5
a6 a3 a4 a5

front rear front rear
设循环队列的数组长度为QueueSize，由于与QueueSize取模的结果一定在0—QueueSize-1之间，所以，将front和rear初始化在数组的某一端即可。
0 1 2 3 4 0 1 2 3 4

front rear front rear
初始化在数组的低端 初始化在数组的高端
假设队列中只有一个元素，执行出队操作，则队头指针加1后与队尾指针相等，即判空条件是front=rear；
0 1 2 3 4 出队 0 1 2 3 4
a3

front rear front rear
假设数组中只有一个空闲单元，执行入队操作，则队尾指针加1后与队头指针相等，即队满的条件也是front=rear；

0 1 2 3 4 入队 0 1 2 3 4
a5 a2 a3 a4
a5 a6 a2 a3 a4

front rear front rear
方法一：设置标志flag，当front=rear且flag=0时队空，当front=rear且flag=1时队满；
方法二：附设一个存储队列元素个数的变量num，当num=0时为队空，当num=QueueSize时队满；
方法三：保留对空的条件，修改队满的条件，浪费一个元素空间，队满时数组中还有一个空闲单元；
讨论方法三：
当存储循环队列的数组只有一个空闲单元时，将循环队列视为队满，此时队尾指针和队头指针正好差1，即队满的条件是：（rear+1）%QueueSize=front
0 1 2 3 4 0 1 2 3 4
a5 a2 a3 a4
a2 a3 a4 a5

front rear front rear
front>rear的情况 front<rear的情况
3.2.3队列的链接存储结构及实现
1.队列的链接存储结构——链队列
根据队列的定义，为了操作上的方便，设置队头指针指向链队列的头结点，队头指针即是单链表的头指针，队尾指针指向终端结点。

a21
an
ai
front
rear