1
3.2 栈 的应用举例
例 1,括号匹配的检验
假设一个算法表达式中包含圆括号、方括号和花括
号三种类型的括号，编写一个判别表达式中括号是
否正确配对的函数。
设计 思路：用栈暂存左括号
2
void ExpIsCorrect(char exp[],int n)
//判断有 n个字符的字符串 exp左右括号是否配对正确
{ SeqStack myStack; int i; char c;
StackInitiate(&myStack);
for(i=0;i<n;i++)
{if((exp[i]=='(')||(exp[i]== '[')||(exp[i]==
'{')) StackPush(&myStack,exp[i]);
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '(')
StackPop(&myStack,&c);
3
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '(')
{ printf("左右括号配对次序不正确！ \n");
return;}
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '[')
{ printf("左右括号配对次序不正确！ \n"); return;｝
4
else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '{')
StackPop(&myStack,&c);
else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '{')
{printf("左右括号配对次序不正确！ \n");return;}
else if(((exp[i] == ')') || (exp[i] == ']') ||
(exp[i] == '}')) && !StackNotEmpty(myStack))
{ printf("右括号多于左括号！ \n"); return;}
}
5
if(StackNotEmpty(myStack))
printf("左括号多于右括号！ \n");
else
printf("左右括号匹配正确！ \n");
}
6
3.3 队列
一、队列的基本概念
１、队列定义
３、存储结构
４、运算规则
５、实现方式
２、逻辑结构
只能在表的一端进行插入操作，在表的另一端
进行删除操作的线性表。
队尾插
入
队头删
除
与线性表相同，仍为一对一关系。
顺序队列 或 链队列,以 循环顺序队列 更常见。
只能在队首和队尾运算，且访问结点时依照
先进先出 （ FIFO） 的原则。
关键是掌握 入队 和 出队 操作，具体实现依顺
序队或链队的不同而不同。
基本操作, 入队或出队，建空队列，判队空或队满等操作。
7
队列 （ Queue） 是仅在 表尾 进行插入操作，在 表头 进
行删除操作的线性表。它是一种先进先出 （ＦＩＦＯ）
的线性表。
例如：队列 Q= (a1,a2,a3,……….,an-1,an )
在队尾插入元素称为 入队 ；在队首删除元素称为
出队 。
当队列中没有数据元素时称为空队列。
队首 队尾
8
注：队列的 实现方式 是本节重点,关键是掌握 入队 和 出队 操作。
具体实现依 存储结构 （ 链队列 或 顺序队列 ）的不同而不同。
1,离散事件的模拟 （模拟事件发生的先后顺序,
例如 CPU芯片中的指令译码队列） ；
2,操作系统中的作业调度 （一个 CPU执行多个作
业） ；
3,简化程序设计。
答：
问：为什么要设计队列？它有什么独特用途？
9
二、队列抽象数据类型
数据集合,{a0,a1,…,ai,…,an-1｝ ai的数据类型为
DataType
操作集合, (1)QueueInitiate(Q) 初始化队列 Q
(2)QueueNotEmpty(Q) 队列 Q非空否
(3)QueueAppend(Q,x) 入队列
(4)QueueDelete(Q,d) 出队列
(5)QueueGet(Q,d) 取队头数据元素
等
10
三、顺序队列
1,顺序队列 采用顺序存储结构的队列。
2、顺序队列的存储结构
它利用一个一维数组来
存储数据元素，另再设立一
个队头指示器和一个队尾指
示器分别指向当前队头元素
和当前队尾元素。用 C语言
定义为：
typedef struct
{
DataType queue[MaxQueueSize];
int rear;
int front;
}SeqCQueue;
a1
a2
a3
data
a4
８
７
６
５
４
３
２
１
０
front
rear
(队尾 )
(队头 )
11
3、顺序队列的, 假溢出, 问题
(1)假 溢出
顺序队列因多次入队和出队操作后出现的有存储空间但不
能进行入队操作的溢出。
(2)如何解决顺序队列的假溢出问题？
可采取四种方法：
1)采用循环队列 ；
2)按最大可能的进队操作次数设置顺序队列的最大
元素个数；
3)修改出队算法，使每次出队列后都把队列中剩余
数据元素向队头方向移动一个位置；
４ )修改入队算法，增加判断条件，当假 溢出时，把
队列中的数据元素向对头移动，然后方完成入队操
作。
12
四、顺序循环队列的表示和实现
１、顺序循环队列的基本原理
把顺序队列所使用的存储空间构造成一个逻辑上
首尾相连的循环队列。当 rear和 front达到
MaxQueueSize-1后，再前进一个位置就自动到０。
顺序队列
a3
a2
a1front
rear
0
1
2
3
.
.
N-1
a3 a2
a1
0
1
2
3
N-1
rear
front
循环队列
13
2、顺序循环队列的队空和队满判断问题
新问题,在循环队列中，空队特征是 front=rear； 队满时也会有
front=rear； 判决条件将出现二义性！ 解决方案有三：
①使用一个 计数器 记录队列中元素个数（即队列长度）；
判队满,count>0 && rear==front
判队空,count==0
② 加 设标志位,出队 时置０,入队时置１,则可识别当前
front=rear属于何种情况
判队满,tag==1 && rear==front
判队空,tag==0 && rear==front
③ 少用 一个存储单元
判队满,front=＝ (rear+1)%MaxQueueSize
判队空,rear==front
14
例,一循环队列如下图所示，若先删除 4个元素，接着再
插入 4个元素，请问队头和队尾指针分别指向哪个位置?
J2 J3
J1 J4
J5front=1
rear=0
解,由图可知，队头和队尾指针的初态分别为 front=1和 rear=0。
删除 4个元素后 f=5； 再插入 4个元素后,r=(0+4)%6=4
front=5
J6 J5
J7
J8 J9
rear=4
rear=0 front=5
15
３、顺序循环队列的实现
采用对顺序循环队列的分析，其结构体定义为：
typedef struct
{
DataType queue[MaxQueueSize];
int rear; /*队尾指针 */
int front; /*队头指针 */
int count; /*计数器 */
} SeqCQueue;
16
讨论：循环队列的基本操作如何实现？
以建队、入队和出队三种基本操作为例
1）初始化一个顺序循环队列
算法要求：生成一空队列
算法操作,设置队列为 空队列,其特征即：
front=rear=0,count=0
17
具体算法：
void QueueInitiate(SeqCQueue *Q)
/*初始化顺序循环队列 Q*/
{ Q->rear = 0; /*定义初始队尾指针下标值 */
Q->front = 0; /*定义初始队头指针下标值 */
Q->count = 0; /*定义初始计数器值 */
}
18
算法说明：向循环队列的 队尾插入 一个元素
分 析,
(1) 插入前应当先判断队列是否满？
if (Q->count>0 && Q->rear==Q->front)
return 0;
(2）插入动作
Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxQueueSize;
Q->count++;
return 1;
2） 入队操作
队列尺寸
19
int QueueAppend(SeqCQueue *Q,DataType x)
{ if(Q->count > 0 && Q->rear == Q->front)
{ printf("队列已满无法插入 ! \n");
return 0; }
else
{ Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxQueueSize;
Q->count++;
return 1; }
}
入队操作完整算法
20
3）出队操作
算法说明：删除队头元素，返回其值 e
分 析：
（ 1） 在删除前应当判断队列是否空？
if(Q->count == 0) return 0;
（ 2） 删除动作
m = Q->queue[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
Q->count--;
front指针在元素出队后再加
21
int QueueDelete(SeqCQueue *Q,DataType *d)
{ if(Q->count == 0)
{ printf("队列已空无数据元素出队列 ! \n");
return 0; }
else {
*d = Q->queue[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
Q->count--;
return 1; }
}
出队操作完整算法
22
下次讲课内容
?链式队列 (重点入队、出队算法）
?队列的应用 （编程序判断一个字符序列
是否是回文。熟练应用入栈、出栈和入
队列、出队列等算法）
?优先级队列的概念和入队算法
?本章复习
3.2 栈 的应用举例
例 1,括号匹配的检验
假设一个算法表达式中包含圆括号、方括号和花括
号三种类型的括号，编写一个判别表达式中括号是
否正确配对的函数。
设计 思路：用栈暂存左括号
2
void ExpIsCorrect(char exp[],int n)
//判断有 n个字符的字符串 exp左右括号是否配对正确
{ SeqStack myStack; int i; char c;
StackInitiate(&myStack);
for(i=0;i<n;i++)
{if((exp[i]=='(')||(exp[i]== '[')||(exp[i]==
'{')) StackPush(&myStack,exp[i]);
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '(')
StackPop(&myStack,&c);
3
else if(exp[i] == ')' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '(')
{ printf("左右括号配对次序不正确！ \n");
return;}
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '[')
StackPop(&myStack,&c);
else if(exp[i] == ']' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '[')
{ printf("左右括号配对次序不正确！ \n"); return;｝
4
else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c == '{')
StackPop(&myStack,&c);
else if(exp[i] == '}' && StackNotEmpty(myStack)
&& StackTop(myStack,&c) && c != '{')
{printf("左右括号配对次序不正确！ \n");return;}
else if(((exp[i] == ')') || (exp[i] == ']') ||
(exp[i] == '}')) && !StackNotEmpty(myStack))
{ printf("右括号多于左括号！ \n"); return;}
}
5
if(StackNotEmpty(myStack))
printf("左括号多于右括号！ \n");
else
printf("左右括号匹配正确！ \n");
}
6
3.3 队列
一、队列的基本概念
１、队列定义
３、存储结构
４、运算规则
５、实现方式
２、逻辑结构
只能在表的一端进行插入操作，在表的另一端
进行删除操作的线性表。
队尾插
入
队头删
除
与线性表相同，仍为一对一关系。
顺序队列 或 链队列,以 循环顺序队列 更常见。
只能在队首和队尾运算，且访问结点时依照
先进先出 （ FIFO） 的原则。
关键是掌握 入队 和 出队 操作，具体实现依顺
序队或链队的不同而不同。
基本操作, 入队或出队，建空队列，判队空或队满等操作。
7
队列 （ Queue） 是仅在 表尾 进行插入操作，在 表头 进
行删除操作的线性表。它是一种先进先出 （ＦＩＦＯ）
的线性表。
例如：队列 Q= (a1,a2,a3,……….,an-1,an )
在队尾插入元素称为 入队 ；在队首删除元素称为
出队 。
当队列中没有数据元素时称为空队列。
队首 队尾
8
注：队列的 实现方式 是本节重点,关键是掌握 入队 和 出队 操作。
具体实现依 存储结构 （ 链队列 或 顺序队列 ）的不同而不同。
1,离散事件的模拟 （模拟事件发生的先后顺序,
例如 CPU芯片中的指令译码队列） ；
2,操作系统中的作业调度 （一个 CPU执行多个作
业） ；
3,简化程序设计。
答：
问：为什么要设计队列？它有什么独特用途？
9
二、队列抽象数据类型
数据集合,{a0,a1,…,ai,…,an-1｝ ai的数据类型为
DataType
操作集合, (1)QueueInitiate(Q) 初始化队列 Q
(2)QueueNotEmpty(Q) 队列 Q非空否
(3)QueueAppend(Q,x) 入队列
(4)QueueDelete(Q,d) 出队列
(5)QueueGet(Q,d) 取队头数据元素
等
10
三、顺序队列
1,顺序队列 采用顺序存储结构的队列。
2、顺序队列的存储结构
它利用一个一维数组来
存储数据元素，另再设立一
个队头指示器和一个队尾指
示器分别指向当前队头元素
和当前队尾元素。用 C语言
定义为：
typedef struct
{
DataType queue[MaxQueueSize];
int rear;
int front;
}SeqCQueue;
a1
a2
a3
data
a4
８
７
６
５
４
３
２
１
０
front
rear
(队尾 )
(队头 )
11
3、顺序队列的, 假溢出, 问题
(1)假 溢出
顺序队列因多次入队和出队操作后出现的有存储空间但不
能进行入队操作的溢出。
(2)如何解决顺序队列的假溢出问题？
可采取四种方法：
1)采用循环队列 ；
2)按最大可能的进队操作次数设置顺序队列的最大
元素个数；
3)修改出队算法，使每次出队列后都把队列中剩余
数据元素向队头方向移动一个位置；
４ )修改入队算法，增加判断条件，当假 溢出时，把
队列中的数据元素向对头移动，然后方完成入队操
作。
12
四、顺序循环队列的表示和实现
１、顺序循环队列的基本原理
把顺序队列所使用的存储空间构造成一个逻辑上
首尾相连的循环队列。当 rear和 front达到
MaxQueueSize-1后，再前进一个位置就自动到０。
顺序队列
a3
a2
a1front
rear
0
1
2
3
.
.
N-1
a3 a2
a1
0
1
2
3
N-1
rear
front
循环队列
13
2、顺序循环队列的队空和队满判断问题
新问题,在循环队列中，空队特征是 front=rear； 队满时也会有
front=rear； 判决条件将出现二义性！ 解决方案有三：
①使用一个 计数器 记录队列中元素个数（即队列长度）；
判队满,count>0 && rear==front
判队空,count==0
② 加 设标志位,出队 时置０,入队时置１,则可识别当前
front=rear属于何种情况
判队满,tag==1 && rear==front
判队空,tag==0 && rear==front
③ 少用 一个存储单元
判队满,front=＝ (rear+1)%MaxQueueSize
判队空,rear==front
14
例,一循环队列如下图所示，若先删除 4个元素，接着再
插入 4个元素，请问队头和队尾指针分别指向哪个位置?
J2 J3
J1 J4
J5front=1
rear=0
解,由图可知，队头和队尾指针的初态分别为 front=1和 rear=0。
删除 4个元素后 f=5； 再插入 4个元素后,r=(0+4)%6=4
front=5
J6 J5
J7
J8 J9
rear=4
rear=0 front=5
15
３、顺序循环队列的实现
采用对顺序循环队列的分析，其结构体定义为：
typedef struct
{
DataType queue[MaxQueueSize];
int rear; /*队尾指针 */
int front; /*队头指针 */
int count; /*计数器 */
} SeqCQueue;
16
讨论：循环队列的基本操作如何实现？
以建队、入队和出队三种基本操作为例
1）初始化一个顺序循环队列
算法要求：生成一空队列
算法操作,设置队列为 空队列,其特征即：
front=rear=0,count=0
17
具体算法：
void QueueInitiate(SeqCQueue *Q)
/*初始化顺序循环队列 Q*/
{ Q->rear = 0; /*定义初始队尾指针下标值 */
Q->front = 0; /*定义初始队头指针下标值 */
Q->count = 0; /*定义初始计数器值 */
}
18
算法说明：向循环队列的 队尾插入 一个元素
分 析,
(1) 插入前应当先判断队列是否满？
if (Q->count>0 && Q->rear==Q->front)
return 0;
(2）插入动作
Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxQueueSize;
Q->count++;
return 1;
2） 入队操作
队列尺寸
19
int QueueAppend(SeqCQueue *Q,DataType x)
{ if(Q->count > 0 && Q->rear == Q->front)
{ printf("队列已满无法插入 ! \n");
return 0; }
else
{ Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxQueueSize;
Q->count++;
return 1; }
}
入队操作完整算法
20
3）出队操作
算法说明：删除队头元素，返回其值 e
分 析：
（ 1） 在删除前应当判断队列是否空？
if(Q->count == 0) return 0;
（ 2） 删除动作
m = Q->queue[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
Q->count--;
front指针在元素出队后再加
21
int QueueDelete(SeqCQueue *Q,DataType *d)
{ if(Q->count == 0)
{ printf("队列已空无数据元素出队列 ! \n");
return 0; }
else {
*d = Q->queue[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
Q->count--;
return 1; }
}
出队操作完整算法
22
下次讲课内容
?链式队列 (重点入队、出队算法）
?队列的应用 （编程序判断一个字符序列
是否是回文。熟练应用入栈、出栈和入
队列、出队列等算法）
?优先级队列的概念和入队算法
?本章复习
