2009-7-28第 3章
1
第 3章 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列
2009-7-28 第 3章 2
3.1 栈 ( Stack )
1.定义：限定只在表的一端 (表尾 )进行插入和删除操作的线性表
特点,后进先出 (LIFO)
允许插入和删除的一端称为 栈顶
(top)，另一端称为 栈底 (bottom)
表尾表头
2009-7-28第 3章
3
2,栈的表示和实现
1）顺序栈 ——栈的顺序存储结构
2）链栈 ——栈的链式存储结构
3）静态分配整型指针
2009-7-28第 3章
4
1）顺序栈 ——栈的顺序存储结构限定在表尾进行插入和删除操作的顺序表类型定义,p46
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
SqStack s;
2009-7-28第 3章
5
说明：
base称为栈底指针，始终指向栈底；
当 base = NULL时，表明栈结构不存在。
top为栈顶指针
a,top的初始值指向栈底，即 top=base
b,空栈：当 top=base时为栈空的标记
c,当栈非空时,top的位置：指向当前栈顶元素的下一个位置
stacksize ——当前栈可使用的最大容量
2009-7-28第 3章
6
进栈示例
base base base base base
stacksize
2009-7-28第 3章
7
退栈示例
base base base base base
2009-7-28第 3章
8
几点说明：
栈空条件,s,top =s,base 此时不能出栈
栈满条件,s.top-s.base>=s.stacksize
进栈操作,*s.top++=e; 或 *s.top=e; s.top++;
退栈操作,e=*--s.top； 或 s.top--； e=*s.top；
当栈满时再做进栈运算必定产生空间溢出，
简称“上溢” ;
当栈空时再做退栈运算也将产生溢出，简称“下溢”。
2009-7-28第 3章
9
基本操作的实现
栈的初始化操作 p47
Status InitStack(SqStack &S)
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
进栈操作 p47
Status Push(SqStack &S,SElemType e)
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
2009-7-28第 3章
10
栈的初始化操作 p47
Status InitStack (SqStack &S) {
S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top=S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
2009-7-28第 3章
11
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}
2009-7-28第 3章
12
进栈操作 p47
Status Push(SqStack &S,SElemType e)
{
if (S.top-S.base>=S.stacksize)
{ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top = S.base +S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; /* *S.top = e; S.top = S.top+1;
return OK;
}
2009-7-28第 3章
13
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e=*--S.top; /* S.top= S.top;-1; e=*S.top;
return OK;
}
2009-7-28第 3章
14
2）链栈 ——栈的链式存储结构
不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。
类型定义：
typedef struct SNode{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack s;
2009-7-28第 3章
15
链栈示意图 p47 图 3.3
栈空条件,s=NULL
栈满条件,无 / 无 Free Memory可申请
2009-7-28第 3章
16
进栈操作：
Status Push_L (LinkStack &s,SElemType e)
{ p=(LinkStack)malloc(sizeof(SNode));
if (!p) exit(Overflow);
p->data = e; p->next = s; s=p;
return OK;
}
2009-7-28第 3章
17
退栈操作
Status Pop_L (LinkStack &s,SElemType &e)
{ if (!s) return ERROR;
e=s->data; p=s; s=s->next;
free(p);
return OK;
}
2009-7-28第 3章
18
3）静态分配整型指针
定义
#define MAXSIZE 100
typedef struct {
SElemType base[MAXSIZE];
int top;
}SqStack;
SqStack s;
2009-7-28第 3章
19
初始化
status InitStack(SqStack &s)
{ s.top = 0;
return OK;
}
2009-7-28第 3章
20
进栈
Status Push(SqStack &s,SElemType e)
{ if (s.top == MAXSIZE) return ERROR;
s.base[s.top] = e; s.top++;
return OK;
}
2009-7-28第 3章
21
退栈
Status Pop(SqStack &s,SElemType &e)
{ if (s.top ==0) return ERROR;
s.top--;
e=s.base[s.top];
return OK;
}
2009-7-28第 3章
22
取栈顶元素
Status GetTop(SqStack s,SElemType &e)
{
if (s.top == 0) return ERROR;
e=s.base[s.top-1];
return OK;
}
2009-7-28第 3章
23
3.2 栈的应用
1,数制转换 p48 算法 3.1
2,行编辑程序 p50 算法 3.2
3,表达式求值 p52 ~ p54
2009-7-28第 3章
24
1,数制转换 p48
十进制 N和其它进制数的转换是计算机实现计的基本问题，基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
低位高位
2009-7-28第 3章
25
算法 3.1
要求：输入一个非负十进制整数，输出任意进制数
void Conversion()
{ InitStack(s);
scanf("%d,%d",&N,&base);
N1=N;
while (N1)
{ Push(s,N1%base);
N1 = N1/base; }
while (!(StackEmpty(s))
{ Pop(s,e);
if (e>9) printf("%c",e+55);
else printf("%c",e+48); }
printf("\n");
}
2009-7-28第 3章
26
2,行编辑程序 p50 算法 3.2
void lineedit( )
{ initstack(s);
ch=getchar( );
while(ch!=eof)
{ while(ch!=eof && ch!=‘\n’)
{ switch(ch)
{ case ‘#’,pop(s,c);
case ‘@’,clearstack(s);
default,push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
2009-7-28第 3章
27
3,表达式求值 p52 ~ p54
算符间的优先级关系 p52 ~ p53
先括弧内后括弧外
左括号：比括号内的算符的优先级低比括号外的算符的优先级高
右括号：比括号内的算符的优先级低比括号外的算符的优先级高
#：优先级总是最低
为实现算符优先算法，可使用两个工作栈：
OPND栈：存数据或运算结果
OPTR栈：存运算符
2009-7-28第 3章
28
算法思想：
1.初态,置 OPND栈为空；将,#”作为 OPTR栈的栈底元素
2.依次读入表达式中的每个字符
1）若是操作数，则进入 OPND栈；
2）若是运算符，则与 OPTR栈的栈顶运算符进行优先权（级）的比较：
若读入运算符的优先权高，则进入 OPTR栈；
若读入运算符的优先权低，则 OPTR退栈（退出原有的栈顶元素）,OPND栈退出两个元素
（先退出 b，再退出 a），中间结果再进入 OPND栈；
若读入,）,,OPTR栈的原有栈的栈顶元素若为
,（,,则 OPTR退出,（,；
若读入,#”,OPTR栈栈顶元素也为,#”，则 OPTR栈退出,#”，结束。
例,3*（ 7-2）
2009-7-28第 3章
29
3.4 队列
1,定义
2,链队列 ----队列的链式存储结构
3,循环队列 ----队列的顺序存储结构
2009-7-28第 3章
30
1,定义
是限定在表的一端进行删除，在表的另一端进行插入操作的线性表。
允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性,FIFO(First In First Out)
图示 p59
表头 表尾
2009-7-28第 3章
31
2,链队列 ——队列的链式存储结构
实质是 带头结点的线性链表 ；
两个指针,
队头指针 Q.front指向头结点
队尾指针 Q.rear指向尾结点
初始态,队空条件
头指针和尾指针均指向头结点
Q.front = Q.rear
2009-7-28第 3章
32
1）链队列的类型定义 p61
typedef struct QNode { //元素结点
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //特殊结点
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
LinkQueue Q;
Q.front——指向头结点
Q.rear ——指向链尾结点
2009-7-28第 3章
33
2）链队列示意图 p61图 3.10
2009-7-28第 3章
34
队列运算指针变化状况空队列
2009-7-28第 3章
35
3）基本操作与实现
初始化 p62
Status InitQueue (LinkQueue &Q)
销毁队列 p62
Status DestroyQueue (LinkQueue &Q)
入队 p62
Status EnQueue(LinkQueue &Q,QElemType e)
出队 p62
Status DeQueue(LinkQueue &Q,QElemType &e)
判队空
Status QueueEmpty(LinkQueue Q)
取队头元素
Status GetHead(LinkQueue Q,QElemType &e)
2009-7-28第 3章
36
链队列初始化
Status InitQueue (LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
2009-7-28第 3章
37
链队列的销毁
Status DestroyQueue (LinkQueue &Q)
{ while (Q.front)
{ Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
2009-7-28第 3章
38
Status EnQueue (LinkQueue &Q,QElemType e)
{ p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
链队列的插入（入队）
2009-7-28第 3章
39
Status DeQueue (LinkQueue &Q,ElemType &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if (Q.rear == p) Q.rear=Q.front;
free(p);
return OK;
}
链队列的删除（出队）
2009-7-28第 3章
40
Status QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
判断链队列是否为空
2009-7-28第 3章
41
Status GetHead(LinkQueue Q,QElemType &e)
{
if (QueueEmpty(Q)) return ERROR;
e=Q.front->next->data;
return OK;
}
取链队列的第一个元素结点
2009-7-28第 3章
42
3,循环队列 ——队列的顺序存储结构
顺序队列,
– 用一组地址连续的存储单元依次存放从队列头到队列尾的元素
设两个指针,
– Q.front 指向队列头元素；
– Q.rear 指向队列尾元素的下一个位置
初始状态（空队列）,
– Q.front = Q.rear=0
队列的真满与假满
2009-7-28第 3章
43
类型定义 p64
#define MAXSIZE 100
typedef struct {
QElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
2009-7-28第 3章
44
队列的进队和出队
进队时，将新元素按 Q.rear 指示位置加入，再将队尾指针增 1,Q.rear = Q.rear + 1 。
出队时，将下标为 Q.front 的元素取出，再将队头指针增 1,Q.front = Q.front + 1 。
队满时再进队将溢出出错；队空时再出队作队空处理。上图为,假满,
2009-7-28第 3章
45
存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加 1时从 maxSize -1直接进到 0，
可用语言的取模 (余数 )运算实现。
队头指针进 1,Q.front = (Q.front + 1)% MAXSIZE
队尾指针进 1,Q.rear = (Q.rear + 1)% MAXSIZE;
队列初始化,Q.front = Q.rear = 0;
队空条件,Q.front == Q.rear;
队满条件,(Q.rear + 1) % MAXSIZE == Q.front
队列长度,(Q.rear-
Q.front+MAXSIZE)%MAXSIZE
循环队列 (Circular Queue)
2009-7-28第 3章
46
循环队列的进队和出队
2009-7-28第 3章
47
说明
不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最大队列长度。
循环队列中要有一个元素空间浪费掉 --
--p63 约定队列头指针在队列尾指针的下一位置上为“满”的标志
解决 Q.front=Q.rear不能判别队列“空”
还是“满”的其他办法：
– 使用一个计数器记录队列中元素的总数
（即队列长度）
– 设一个标志变量以区别队列是空或满
2009-7-28第 3章
48
基本操作
初始化 p64
Status InitQueue (SqQueue &Q)
求队列的长度 p64
int QueueLength(SqQueue Q)
入队 p65
Status EnQueue (SqQueue &Q,QElemType e)
出队 p65
Status DeQueue(SqQueue &Q,QElemType &e)
判队空
Status QueueEmpty(SqQueue Q)
取队头元素
Status GetHead(SqQueue Q,QElemType &e)
2009-7-28第 3章
49
Status InitQueue (SqQueue &Q)
{
Q.base=(QElemTye
*)malloc(MAXQSIZE*sizeof(QElemType
));
if (!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
2009-7-28第 3章
50
int QueueLength(SqQueue Q)
{
return (Q.rear-
Q.front+MAXQSIZE)%MAXQSIZE;
}
2009-7-28第 3章
51
Status EnQueue (SqQueue &Q,
QElemType e)
{
if ((Q.rear+1) % MAXQSIZE
==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
2009-7-28第 3章
52
Status DeQueue(SqQueue &Q,
QElemType &e)
{
if (Q.rear==Q.front) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
2009-7-28第 3章
53
Status QueueEmpty(SqQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
2009-7-28第 3章
54
Status GetHead(SqQueue Q,QElemType
&e)
{
if QueueEmpty(Q) return ERROR;
e=Q.base[Q.front];
return OK;
}
2009-7-28第 3章
55
非循环队列
类型定义：与循环队列完全一样
关键：修改队尾 /队头指针 Q.rear =
Q.rear + 1; Q.front = Q.front+1;
在判断时，有 %MAXQSIZE为循环队列，
否则为非循环队列
队空条件,Q.front = Q.rear
队满条件,Q.rear>= MAXQSIZE
注意“假上溢”的处理
长度,Q.rear - Q.front
1
第 3章 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列
2009-7-28 第 3章 2
3.1 栈 ( Stack )
1.定义：限定只在表的一端 (表尾 )进行插入和删除操作的线性表
特点,后进先出 (LIFO)
允许插入和删除的一端称为 栈顶
(top)，另一端称为 栈底 (bottom)
表尾表头
2009-7-28第 3章
3
2,栈的表示和实现
1）顺序栈 ——栈的顺序存储结构
2）链栈 ——栈的链式存储结构
3）静态分配整型指针
2009-7-28第 3章
4
1）顺序栈 ——栈的顺序存储结构限定在表尾进行插入和删除操作的顺序表类型定义,p46
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
SqStack s;
2009-7-28第 3章
5
说明：
base称为栈底指针，始终指向栈底；
当 base = NULL时，表明栈结构不存在。
top为栈顶指针
a,top的初始值指向栈底，即 top=base
b,空栈：当 top=base时为栈空的标记
c,当栈非空时,top的位置：指向当前栈顶元素的下一个位置
stacksize ——当前栈可使用的最大容量
2009-7-28第 3章
6
进栈示例
base base base base base
stacksize
2009-7-28第 3章
7
退栈示例
base base base base base
2009-7-28第 3章
8
几点说明：
栈空条件,s,top =s,base 此时不能出栈
栈满条件,s.top-s.base>=s.stacksize
进栈操作,*s.top++=e; 或 *s.top=e; s.top++;
退栈操作,e=*--s.top； 或 s.top--； e=*s.top；
当栈满时再做进栈运算必定产生空间溢出，
简称“上溢” ;
当栈空时再做退栈运算也将产生溢出，简称“下溢”。
2009-7-28第 3章
9
基本操作的实现
栈的初始化操作 p47
Status InitStack(SqStack &S)
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
进栈操作 p47
Status Push(SqStack &S,SElemType e)
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
2009-7-28第 3章
10
栈的初始化操作 p47
Status InitStack (SqStack &S) {
S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top=S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
2009-7-28第 3章
11
取栈顶元素 p47
Status GetTop(SqStack S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}
2009-7-28第 3章
12
进栈操作 p47
Status Push(SqStack &S,SElemType e)
{
if (S.top-S.base>=S.stacksize)
{ S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.top = S.base +S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; /* *S.top = e; S.top = S.top+1;
return OK;
}
2009-7-28第 3章
13
退栈操作 p47
Status Pop(SqStack &S,SElemType &e)
{
if (S.top == S.base) return ERROR;
e=*--S.top; /* S.top= S.top;-1; e=*S.top;
return OK;
}
2009-7-28第 3章
14
2）链栈 ——栈的链式存储结构
不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。
类型定义：
typedef struct SNode{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack s;
2009-7-28第 3章
15
链栈示意图 p47 图 3.3
栈空条件,s=NULL
栈满条件,无 / 无 Free Memory可申请
2009-7-28第 3章
16
进栈操作：
Status Push_L (LinkStack &s,SElemType e)
{ p=(LinkStack)malloc(sizeof(SNode));
if (!p) exit(Overflow);
p->data = e; p->next = s; s=p;
return OK;
}
2009-7-28第 3章
17
退栈操作
Status Pop_L (LinkStack &s,SElemType &e)
{ if (!s) return ERROR;
e=s->data; p=s; s=s->next;
free(p);
return OK;
}
2009-7-28第 3章
18
3）静态分配整型指针
定义
#define MAXSIZE 100
typedef struct {
SElemType base[MAXSIZE];
int top;
}SqStack;
SqStack s;
2009-7-28第 3章
19
初始化
status InitStack(SqStack &s)
{ s.top = 0;
return OK;
}
2009-7-28第 3章
20
进栈
Status Push(SqStack &s,SElemType e)
{ if (s.top == MAXSIZE) return ERROR;
s.base[s.top] = e; s.top++;
return OK;
}
2009-7-28第 3章
21
退栈
Status Pop(SqStack &s,SElemType &e)
{ if (s.top ==0) return ERROR;
s.top--;
e=s.base[s.top];
return OK;
}
2009-7-28第 3章
22
取栈顶元素
Status GetTop(SqStack s,SElemType &e)
{
if (s.top == 0) return ERROR;
e=s.base[s.top-1];
return OK;
}
2009-7-28第 3章
23
3.2 栈的应用
1,数制转换 p48 算法 3.1
2,行编辑程序 p50 算法 3.2
3,表达式求值 p52 ~ p54
2009-7-28第 3章
24
1,数制转换 p48
十进制 N和其它进制数的转换是计算机实现计的基本问题，基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
低位高位
2009-7-28第 3章
25
算法 3.1
要求：输入一个非负十进制整数，输出任意进制数
void Conversion()
{ InitStack(s);
scanf("%d,%d",&N,&base);
N1=N;
while (N1)
{ Push(s,N1%base);
N1 = N1/base; }
while (!(StackEmpty(s))
{ Pop(s,e);
if (e>9) printf("%c",e+55);
else printf("%c",e+48); }
printf("\n");
}
2009-7-28第 3章
26
2,行编辑程序 p50 算法 3.2
void lineedit( )
{ initstack(s);
ch=getchar( );
while(ch!=eof)
{ while(ch!=eof && ch!=‘\n’)
{ switch(ch)
{ case ‘#’,pop(s,c);
case ‘@’,clearstack(s);
default,push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
2009-7-28第 3章
27
3,表达式求值 p52 ~ p54
算符间的优先级关系 p52 ~ p53
先括弧内后括弧外
左括号：比括号内的算符的优先级低比括号外的算符的优先级高
右括号：比括号内的算符的优先级低比括号外的算符的优先级高
#：优先级总是最低
为实现算符优先算法，可使用两个工作栈：
OPND栈：存数据或运算结果
OPTR栈：存运算符
2009-7-28第 3章
28
算法思想：
1.初态,置 OPND栈为空；将,#”作为 OPTR栈的栈底元素
2.依次读入表达式中的每个字符
1）若是操作数，则进入 OPND栈；
2）若是运算符，则与 OPTR栈的栈顶运算符进行优先权（级）的比较：
若读入运算符的优先权高，则进入 OPTR栈；
若读入运算符的优先权低，则 OPTR退栈（退出原有的栈顶元素）,OPND栈退出两个元素
（先退出 b，再退出 a），中间结果再进入 OPND栈；
若读入,）,,OPTR栈的原有栈的栈顶元素若为
,（,,则 OPTR退出,（,；
若读入,#”,OPTR栈栈顶元素也为,#”，则 OPTR栈退出,#”，结束。
例,3*（ 7-2）
2009-7-28第 3章
29
3.4 队列
1,定义
2,链队列 ----队列的链式存储结构
3,循环队列 ----队列的顺序存储结构
2009-7-28第 3章
30
1,定义
是限定在表的一端进行删除，在表的另一端进行插入操作的线性表。
允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。
特性,FIFO(First In First Out)
图示 p59
表头 表尾
2009-7-28第 3章
31
2,链队列 ——队列的链式存储结构
实质是 带头结点的线性链表 ；
两个指针,
队头指针 Q.front指向头结点
队尾指针 Q.rear指向尾结点
初始态,队空条件
头指针和尾指针均指向头结点
Q.front = Q.rear
2009-7-28第 3章
32
1）链队列的类型定义 p61
typedef struct QNode { //元素结点
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{ //特殊结点
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
LinkQueue Q;
Q.front——指向头结点
Q.rear ——指向链尾结点
2009-7-28第 3章
33
2）链队列示意图 p61图 3.10
2009-7-28第 3章
34
队列运算指针变化状况空队列
2009-7-28第 3章
35
3）基本操作与实现
初始化 p62
Status InitQueue (LinkQueue &Q)
销毁队列 p62
Status DestroyQueue (LinkQueue &Q)
入队 p62
Status EnQueue(LinkQueue &Q,QElemType e)
出队 p62
Status DeQueue(LinkQueue &Q,QElemType &e)
判队空
Status QueueEmpty(LinkQueue Q)
取队头元素
Status GetHead(LinkQueue Q,QElemType &e)
2009-7-28第 3章
36
链队列初始化
Status InitQueue (LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
2009-7-28第 3章
37
链队列的销毁
Status DestroyQueue (LinkQueue &Q)
{ while (Q.front)
{ Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
2009-7-28第 3章
38
Status EnQueue (LinkQueue &Q,QElemType e)
{ p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e; p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
链队列的插入（入队）
2009-7-28第 3章
39
Status DeQueue (LinkQueue &Q,ElemType &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if (Q.rear == p) Q.rear=Q.front;
free(p);
return OK;
}
链队列的删除（出队）
2009-7-28第 3章
40
Status QueueEmpty(LinkQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
判断链队列是否为空
2009-7-28第 3章
41
Status GetHead(LinkQueue Q,QElemType &e)
{
if (QueueEmpty(Q)) return ERROR;
e=Q.front->next->data;
return OK;
}
取链队列的第一个元素结点
2009-7-28第 3章
42
3,循环队列 ——队列的顺序存储结构
顺序队列,
– 用一组地址连续的存储单元依次存放从队列头到队列尾的元素
设两个指针,
– Q.front 指向队列头元素；
– Q.rear 指向队列尾元素的下一个位置
初始状态（空队列）,
– Q.front = Q.rear=0
队列的真满与假满
2009-7-28第 3章
43
类型定义 p64
#define MAXSIZE 100
typedef struct {
QElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
2009-7-28第 3章
44
队列的进队和出队
进队时，将新元素按 Q.rear 指示位置加入，再将队尾指针增 1,Q.rear = Q.rear + 1 。
出队时，将下标为 Q.front 的元素取出，再将队头指针增 1,Q.front = Q.front + 1 。
队满时再进队将溢出出错；队空时再出队作队空处理。上图为,假满,
2009-7-28第 3章
45
存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加 1时从 maxSize -1直接进到 0，
可用语言的取模 (余数 )运算实现。
队头指针进 1,Q.front = (Q.front + 1)% MAXSIZE
队尾指针进 1,Q.rear = (Q.rear + 1)% MAXSIZE;
队列初始化,Q.front = Q.rear = 0;
队空条件,Q.front == Q.rear;
队满条件,(Q.rear + 1) % MAXSIZE == Q.front
队列长度,(Q.rear-
Q.front+MAXSIZE)%MAXSIZE
循环队列 (Circular Queue)
2009-7-28第 3章
46
循环队列的进队和出队
2009-7-28第 3章
47
说明
不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最大队列长度。
循环队列中要有一个元素空间浪费掉 --
--p63 约定队列头指针在队列尾指针的下一位置上为“满”的标志
解决 Q.front=Q.rear不能判别队列“空”
还是“满”的其他办法：
– 使用一个计数器记录队列中元素的总数
（即队列长度）
– 设一个标志变量以区别队列是空或满
2009-7-28第 3章
48
基本操作
初始化 p64
Status InitQueue (SqQueue &Q)
求队列的长度 p64
int QueueLength(SqQueue Q)
入队 p65
Status EnQueue (SqQueue &Q,QElemType e)
出队 p65
Status DeQueue(SqQueue &Q,QElemType &e)
判队空
Status QueueEmpty(SqQueue Q)
取队头元素
Status GetHead(SqQueue Q,QElemType &e)
2009-7-28第 3章
49
Status InitQueue (SqQueue &Q)
{
Q.base=(QElemTye
*)malloc(MAXQSIZE*sizeof(QElemType
));
if (!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
2009-7-28第 3章
50
int QueueLength(SqQueue Q)
{
return (Q.rear-
Q.front+MAXQSIZE)%MAXQSIZE;
}
2009-7-28第 3章
51
Status EnQueue (SqQueue &Q,
QElemType e)
{
if ((Q.rear+1) % MAXQSIZE
==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1)%MAXQSIZE;
return OK;
}
2009-7-28第 3章
52
Status DeQueue(SqQueue &Q,
QElemType &e)
{
if (Q.rear==Q.front) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
2009-7-28第 3章
53
Status QueueEmpty(SqQueue Q)
{
if (Q.front==Q.rear) return TRUE;
return FALSE;
}
2009-7-28第 3章
54
Status GetHead(SqQueue Q,QElemType
&e)
{
if QueueEmpty(Q) return ERROR;
e=Q.base[Q.front];
return OK;
}
2009-7-28第 3章
55
非循环队列
类型定义：与循环队列完全一样
关键：修改队尾 /队头指针 Q.rear =
Q.rear + 1; Q.front = Q.front+1;
在判断时，有 %MAXQSIZE为循环队列，
否则为非循环队列
队空条件,Q.front = Q.rear
队满条件,Q.rear>= MAXQSIZE
注意“假上溢”的处理
长度,Q.rear - Q.front
