2009-7-30 软件基础（第 3章 堆栈和队列）
3.3 队列的概念及其算法 (Queue)
3.3.1队列的基本概念
3.3.2队列的 顺序 存储结构
3.3.3队列的链接存储结构
3.3.4队列的应用
2009-7-30 软件基础（第 3章 堆栈和队列）
1,定义
–队列,是只允许在一端删除，在另一端插入的线性表,
–队头 (front):允许删除的一端,
–队尾 (rear):允许插入的一端。
a2 … an-1a1a0出队 入队
front rear
3.3.1.队列的定义与操作
2009-7-30 软件基础（第 3章 堆栈和队列）
2,队列的基本操作
初始化
入队列
出队列
取对头元素
判断队列空满
特性,先进先出 (FIFO,First In First Out)
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.2.队列的顺序存储结构
a2 … an-1a1a0出队 入队
front rear
1.顺序队列的 c语言描述：
elemtype queue[maxsize];
int front;
int rear;
简单形式：
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct
{elemtype queue[maxsize];
int front;
int rear;
}squeue;
squeue *q;
结构体形式：
2009-7-30 软件基础（第 3章 堆栈和队列）
front
queue[maxsize]
rear qq->rear
q->front
q->queue[0]
q->queue[1]
q->queue[2]
…
q->queue[maxsize-1]
借助 C语言的算法描述使用的数据类型示意图
2009-7-30 软件基础（第 3章 堆栈和队列）
front
rear
空队 a入队 b入队
队列入队过程
cd入队
4
3
2
1
0
4
3
2
1
0 a
4
3
2
1
0
b
a
4
3
2
1
0rear
front front
rear
front
rear
a
b
d
c
注意：入队时,front不变,rear变
2009-7-30 软件基础（第 3章 堆栈和队列）
g
f
e
d
c
b
a
front
rear
队满
g
f
e
d
c
b
front
rear
a出队
g
f
e
d
front
rear
bc出队
front
rear
defg出队
队列出队过程注意：出队时,front变,rear不变 队空
2009-7-30 软件基础（第 3章 堆栈和队列）
进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
队满时 (rear =maxsize-1 )再进队将溢出出错；
队空时 (rear = front )再出队将溢出出错。
front总是指向队列中第一个元素的前一个位置。
rear总是指向队列中最后元素的位置。
2009-7-30 软件基础（第 3章 堆栈和队列）
队列的状态队空：条件 front=rear
队满：条件 rear=maxsize-1
上溢：队满时还要入队下溢：队空时还要出队提问：顺序队列是否会出现假队满？？？
继而会出现假上溢？？？
2009-7-30 软件基础（第 3章 堆栈和队列）
问题的提出：
初始状态
front
rear
b
a
4
3
2
1
0
d
c
f入队e入队
front
rear 4
3
2
1
0
e
b
a
d
c
a出队
front
4
3
2
1
0
e
b
a
d
c
rear
4
3
2
1
0
frontrear
队满！
上溢错队空 入队 队满！上溢出错！
2009-7-30 软件基础（第 3章 堆栈和队列）
顺序队列的假溢出
rear
rear a
0
a1
a2
a3
rear
rear
rear
maxlen个
front
front
rear a
4
rear a
5
front
6
rear
假溢出
2009-7-30 软件基础（第 3章 堆栈和队列）
如何防止和解决这个问题？？？
这种现象称为 假队满 。
rear=maxsize-1.
front>0
此时入队就会出现 假上溢
2009-7-30 软件基础（第 3章 堆栈和队列）
方法 1,尽可能设置较大的队列容量。
因估计不准而出错，且浪费空间。
方法 2,修改出队列算法，每次出队移动剩余元素。
e
d
c
b
afront
rear
a出队
e
d
c
bfront
rear
缺点,移动浪费时间，时间复杂度,O(n)
这里 front
无用。
初始态 b出队
e
d
cfront
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
方法 3,修改入队列算法，当假溢出时，则把队列中的元素向队头移动 front+1个位置。
a入队
front
rear 4
3
2
1
0
e
d
c 假溢出元素移动
2个位置
4
3
2
1
0
d
c
erear
front
缺点,浪费时间，时间复杂度,O(n)
初态
2009-7-30 软件基础（第 3章 堆栈和队列）
循环队列,设想 队列的存储空间向量是一个头尾相接的循环向量。
front reara0 a1 a … an-1
假定,队列以顺时针方向增长；
front：指向第一个元素的前一个位置；
rear,指向队尾（最后元素）位置。
方法 4,循环队列可以避免以上三种方法的缺点循环队列的进队和出队
rear
1
2
4
3
5
6 7
0
front
空队列
reara
2
4
3
5
6 7
0
front
a进队
1
front
rear
a
2
4
3
5
6 7
0
bc进队
1bc
front
rear 2
4
3
5
6 7
0
a出队
1bc
rear
front
2
4
3
5
6 7
0
bc出队
1
空队列空队列条件：
Front=rear
front
rear
2
4
3
5
6 7
0
1bcd
e
f g
h
i
队列满 (2)
注意,此时 rear=front
队满和队空条件相同队满和队空需靠标志来区分。
以下我们仅讨论队满（ 2）情况队列满 (1)
注意,此时 rear≠front：队满
rear=front,队空队满和队空易于区分。
这样，将少存一个元素。front2
4
3
5
6 7
0 rear
1bcd
e
f g
h
队列满情况：
front
rear 2
4
3
5
6 7
0
初始队
1bc
defg进队
rear
front2
4
3
5
6 7
0
1bcd
e
f g
h进队
1
rear
front2
4
3
5
6 7
0
bc
d
e
f g
h
rear如何从 7到 0?
方法 1,if语句方法 2：求模运算
front如何从 7到 0?
1
rear2
4
3
5
6 7
0
b
front
初始队
2
4
3
5
6 7
0h
b
front
rear
h出队头、尾指针循环问题：
2009-7-30 软件基础（第 3章 堆栈和队列）
存储循环队列的数组被当作首尾相接的表来处理。
队头、队尾指针 加 1时从 maxsize -1直接进到 0，可用 C语言的取模 (余数 )运算实现。
循环队列容量为,maxsize,可存
maxsize-1个元素循环队列的特点：
2009-7-30 软件基础（第 3章 堆栈和队列）
出队时：
队头指针进 1,front = (front + 1)%maxsize;
入队时：
队尾指针进 1,rear = (rear + 1) % maxsize;
队列初始化,front = rear = 0;
队空条件,front == rear;
队满条件,(rear + 1) % maxsize == front
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct
{ elemtype queue[maxsize];
int front,rear;
} qqtype;
循环队列类型说明同顺序队列类型说明
2009-7-30 软件基础（第 3章 堆栈和队列）
循环队列的基本操作
1、置空队列
2、判定队列是否为空
3、取队列头元素
4、将新元素插入队尾
5、队列头元素出队
2009-7-30 软件基础（第 3章 堆栈和队列）
iniqueue(qqtype *sq)
{
sq->front=0;
sq->rear=0;
}
队列的初始化
rear
1
2
4
3
5
6 7
0
front
空队列
2009-7-30 软件基础（第 3章 堆栈和队列）
int addqueue(qqtype *sq,elemtype x)
{
If (sq->front==(sq->rear+1)%maxsize);
{printf(“\nQueue is full”);
return 0;
}
sq->rear=(sq->rear+1)%maxsize;
sq->queue[sq->rear]=x;
return 1;
}
判队满？
队尾指针加 1
并循环x入队
循环队列入队算法：
能否将 sq->rear+1改为,sq->rear++？
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue(qqtype *sq)
{if(sq->front==sq->rear)
{printf("\n Queue is empty!");
return(0);
}
sq->front=(sq->front+1)%maxsize;
return 1；
/*return (sq->queue[sq->front]);*/
}
循环队列出队算法：
判队空？
front循环
2009-7-30 软件基础（第 3章 堆栈和队列）
总结：
入队：判队满，尾变头不变。
出队：判队空，头变尾不变。
要变就变成：加 1后求模运算。
rear=(rear+1)%maxsize
front=(front+1)%maxsize
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.3 队列的链接表示 — 链式队列
队头在链头，队尾在链尾。
链式队列在进队时无队满问题，
但有队空问题。
队空 ∧front
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
struct qnode
{elemtype data;
struct qnode *next;
};
typedef struct qnode Qnode;
Qnode * front,*rear;
链队列结点类型定义
简单类型：
头、尾指针为简单指针型变量
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct qnode
{elemtype data;
struct qnode *next;
} Qnode;
复杂类型：
头、尾为结构体的两指针项
typedef struct
{Qnode * front;
Qnode *rear;
}Qltype;
2009-7-30 软件基础（第 3章 堆栈和队列）
链式队列存储结构的图示队列的链式存储结构
12EF
front
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
10CB
rear
Qnode *front,*rear;
Qltype *q;
q->front,q->rear;
或者：
2009-7-30 软件基础（第 3章 堆栈和队列）
Int initqueue(Qltype *q)
{if ((q->front=(Qnode* )malloc(sizeof(Qnode)))==NULL)
{printf(“\n申请空间失败 !”);
return 0;}
q->rear=q->front;
q->front->next=NULL;
return 1;
}
链队列的初始化
12EF
front
12EF
rear NULL
2009-7-30 软件基础（第 3章 堆栈和队列）
链队列的入队示意
12EF
front
*p
130A
p
NULL130A
*p
1475
p
x NULLx NULL1475
12EF
rear
130A
rear
1475
rear
int addq (Qltype *q,elemtype x)
{Qnode *p;
if ((p=(Qnode* ) malloc(sizeof(Qnode)))==NULL)
{printf (“\n申请空间失败 !”); return 0;}
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
return 1;
}
a1front a2 ∧
rear rear
链队列的入队算法
p
X ∧
2009-7-30 软件基础（第 3章 堆栈和队列）
链队列的出队
y
1475
p
12EF
front
a2 NULL1475
a1 130A
130A
a1
1475
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue (Qltype *q)
{elemtype y;
Qnode *p;
if (q->front->next==NULL) return NULL;
p=q->front->next;
y=p->data;
q->front->next=p->next;
free(p);
return (y);
}
链队列的出队算法
a1front a2 ∧
rear
p a1
y
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.4 队列的应用 ——
在计算机运行期间,经常会出现这样的情况,程序正在执行应用程序,用户可以从键盘上输入数据,这是所谓的多进程处理,
多进程处理方式,
应用程序进程执行时,系统不断地检测键盘的状态,
一旦测得新字符输入,立刻存入缓冲区中,然后继续执行原有的进程,当原有的进程结束时,再处理键盘缓冲区的字符,
1,键盘输入循环缓冲区问题
2009-7-30 软件基础（第 3章 堆栈和队列）
问题描述,程序中存在两个进程进程 1:在屏幕上显示 1~10000.
进程 2:将键盘敲入的字符存入输入缓冲区 (循环队列 ),这些字符并不马上显示出来,直到用户键入,;”号时,或者，屏幕显示完成后，再显示所键入的所有字符,
#include <stdio.h>
#include <conio.h>
#include <dos.h>
typedef struct
{elemtype queue[MAXLEN];
int front;
int rear;
} sequeue;
void iniqueue(sequeue *q)
{q->front=0;
q->rear=0;
}
#define MAXLEN 100
typedef char elemtype;
2009-7-30 软件基础（第 3章 堆栈和队列）
int addqueue(sequeue *q,elemtype x)
{if ((q->rear+1)%MAXLEN==q->front)
{printf("\nqueue full");
return 0;
}
q->rear=(q->rear+1)%MAXLEN;
q->queue[q->rear]=x;
return 1;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue(sequeue *q)
{if (q->front==q->rear)
{printf("\nqueue empty");
return 0;
}
q->front=(q->front+1)%MAXLEN;
return (sq->queue[sq->front]);
}
main()
{
char ch;
sequeue buffer;
int i;
iniqueue(&buffer);
printf(“\n”);
for(i=1;i<=10000;i++)
{ printf(“%d”,i);
if(kbhit())
{
if((ch=getch())==?;?) break;
if(! addqueue(&buffer,ch))break;
}
// delay(500);
}
/*初始化 */
/*检测是否有键盘输入,<conio.h> */
/*检测是否输入 ‘ ； ’ */
/*入队 */
2009-7-30 软件基础（第 3章 堆栈和队列）
printf(“\n”);
while((ch= delqueue(&buffer))!=0)
{
printf(“%c”,ch);
}
}
/*出队 */
/*显示出队元素 */
2009-7-30 软件基础（第 3章 堆栈和队列）
总结：
概念：队列，队头，队尾，队满，队空，上溢，下溢，
假上溢，顺序队列，循环队列，链队列。
算法：初始化，入队，出队，取队元素。
（循环队列，链队列）
应用：键盘输入缓冲区问题作业,p87-88 3-1(理解 ),3-2,3-3,3-7,3-12
3.3 队列的概念及其算法 (Queue)
3.3.1队列的基本概念
3.3.2队列的 顺序 存储结构
3.3.3队列的链接存储结构
3.3.4队列的应用
2009-7-30 软件基础（第 3章 堆栈和队列）
1,定义
–队列,是只允许在一端删除，在另一端插入的线性表,
–队头 (front):允许删除的一端,
–队尾 (rear):允许插入的一端。
a2 … an-1a1a0出队 入队
front rear
3.3.1.队列的定义与操作
2009-7-30 软件基础（第 3章 堆栈和队列）
2,队列的基本操作
初始化
入队列
出队列
取对头元素
判断队列空满
特性,先进先出 (FIFO,First In First Out)
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.2.队列的顺序存储结构
a2 … an-1a1a0出队 入队
front rear
1.顺序队列的 c语言描述：
elemtype queue[maxsize];
int front;
int rear;
简单形式：
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct
{elemtype queue[maxsize];
int front;
int rear;
}squeue;
squeue *q;
结构体形式：
2009-7-30 软件基础（第 3章 堆栈和队列）
front
queue[maxsize]
rear qq->rear
q->front
q->queue[0]
q->queue[1]
q->queue[2]
…
q->queue[maxsize-1]
借助 C语言的算法描述使用的数据类型示意图
2009-7-30 软件基础（第 3章 堆栈和队列）
front
rear
空队 a入队 b入队
队列入队过程
cd入队
4
3
2
1
0
4
3
2
1
0 a
4
3
2
1
0
b
a
4
3
2
1
0rear
front front
rear
front
rear
a
b
d
c
注意：入队时,front不变,rear变
2009-7-30 软件基础（第 3章 堆栈和队列）
g
f
e
d
c
b
a
front
rear
队满
g
f
e
d
c
b
front
rear
a出队
g
f
e
d
front
rear
bc出队
front
rear
defg出队
队列出队过程注意：出队时,front变,rear不变 队空
2009-7-30 软件基础（第 3章 堆栈和队列）
进队时队尾指针先进一 rear = rear + 1，
再将新元素按 rear 指示位置加入。
出队时队头指针先进一 front = front + 1，
再将下标为 front 的元素取出。
队满时 (rear =maxsize-1 )再进队将溢出出错；
队空时 (rear = front )再出队将溢出出错。
front总是指向队列中第一个元素的前一个位置。
rear总是指向队列中最后元素的位置。
2009-7-30 软件基础（第 3章 堆栈和队列）
队列的状态队空：条件 front=rear
队满：条件 rear=maxsize-1
上溢：队满时还要入队下溢：队空时还要出队提问：顺序队列是否会出现假队满？？？
继而会出现假上溢？？？
2009-7-30 软件基础（第 3章 堆栈和队列）
问题的提出：
初始状态
front
rear
b
a
4
3
2
1
0
d
c
f入队e入队
front
rear 4
3
2
1
0
e
b
a
d
c
a出队
front
4
3
2
1
0
e
b
a
d
c
rear
4
3
2
1
0
frontrear
队满！
上溢错队空 入队 队满！上溢出错！
2009-7-30 软件基础（第 3章 堆栈和队列）
顺序队列的假溢出
rear
rear a
0
a1
a2
a3
rear
rear
rear
maxlen个
front
front
rear a
4
rear a
5
front
6
rear
假溢出
2009-7-30 软件基础（第 3章 堆栈和队列）
如何防止和解决这个问题？？？
这种现象称为 假队满 。
rear=maxsize-1.
front>0
此时入队就会出现 假上溢
2009-7-30 软件基础（第 3章 堆栈和队列）
方法 1,尽可能设置较大的队列容量。
因估计不准而出错，且浪费空间。
方法 2,修改出队列算法，每次出队移动剩余元素。
e
d
c
b
afront
rear
a出队
e
d
c
bfront
rear
缺点,移动浪费时间，时间复杂度,O(n)
这里 front
无用。
初始态 b出队
e
d
cfront
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
方法 3,修改入队列算法，当假溢出时，则把队列中的元素向队头移动 front+1个位置。
a入队
front
rear 4
3
2
1
0
e
d
c 假溢出元素移动
2个位置
4
3
2
1
0
d
c
erear
front
缺点,浪费时间，时间复杂度,O(n)
初态
2009-7-30 软件基础（第 3章 堆栈和队列）
循环队列,设想 队列的存储空间向量是一个头尾相接的循环向量。
front reara0 a1 a … an-1
假定,队列以顺时针方向增长；
front：指向第一个元素的前一个位置；
rear,指向队尾（最后元素）位置。
方法 4,循环队列可以避免以上三种方法的缺点循环队列的进队和出队
rear
1
2
4
3
5
6 7
0
front
空队列
reara
2
4
3
5
6 7
0
front
a进队
1
front
rear
a
2
4
3
5
6 7
0
bc进队
1bc
front
rear 2
4
3
5
6 7
0
a出队
1bc
rear
front
2
4
3
5
6 7
0
bc出队
1
空队列空队列条件：
Front=rear
front
rear
2
4
3
5
6 7
0
1bcd
e
f g
h
i
队列满 (2)
注意,此时 rear=front
队满和队空条件相同队满和队空需靠标志来区分。
以下我们仅讨论队满（ 2）情况队列满 (1)
注意,此时 rear≠front：队满
rear=front,队空队满和队空易于区分。
这样，将少存一个元素。front2
4
3
5
6 7
0 rear
1bcd
e
f g
h
队列满情况：
front
rear 2
4
3
5
6 7
0
初始队
1bc
defg进队
rear
front2
4
3
5
6 7
0
1bcd
e
f g
h进队
1
rear
front2
4
3
5
6 7
0
bc
d
e
f g
h
rear如何从 7到 0?
方法 1,if语句方法 2：求模运算
front如何从 7到 0?
1
rear2
4
3
5
6 7
0
b
front
初始队
2
4
3
5
6 7
0h
b
front
rear
h出队头、尾指针循环问题：
2009-7-30 软件基础（第 3章 堆栈和队列）
存储循环队列的数组被当作首尾相接的表来处理。
队头、队尾指针 加 1时从 maxsize -1直接进到 0，可用 C语言的取模 (余数 )运算实现。
循环队列容量为,maxsize,可存
maxsize-1个元素循环队列的特点：
2009-7-30 软件基础（第 3章 堆栈和队列）
出队时：
队头指针进 1,front = (front + 1)%maxsize;
入队时：
队尾指针进 1,rear = (rear + 1) % maxsize;
队列初始化,front = rear = 0;
队空条件,front == rear;
队满条件,(rear + 1) % maxsize == front
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct
{ elemtype queue[maxsize];
int front,rear;
} qqtype;
循环队列类型说明同顺序队列类型说明
2009-7-30 软件基础（第 3章 堆栈和队列）
循环队列的基本操作
1、置空队列
2、判定队列是否为空
3、取队列头元素
4、将新元素插入队尾
5、队列头元素出队
2009-7-30 软件基础（第 3章 堆栈和队列）
iniqueue(qqtype *sq)
{
sq->front=0;
sq->rear=0;
}
队列的初始化
rear
1
2
4
3
5
6 7
0
front
空队列
2009-7-30 软件基础（第 3章 堆栈和队列）
int addqueue(qqtype *sq,elemtype x)
{
If (sq->front==(sq->rear+1)%maxsize);
{printf(“\nQueue is full”);
return 0;
}
sq->rear=(sq->rear+1)%maxsize;
sq->queue[sq->rear]=x;
return 1;
}
判队满？
队尾指针加 1
并循环x入队
循环队列入队算法：
能否将 sq->rear+1改为,sq->rear++？
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue(qqtype *sq)
{if(sq->front==sq->rear)
{printf("\n Queue is empty!");
return(0);
}
sq->front=(sq->front+1)%maxsize;
return 1；
/*return (sq->queue[sq->front]);*/
}
循环队列出队算法：
判队空？
front循环
2009-7-30 软件基础（第 3章 堆栈和队列）
总结：
入队：判队满，尾变头不变。
出队：判队空，头变尾不变。
要变就变成：加 1后求模运算。
rear=(rear+1)%maxsize
front=(front+1)%maxsize
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.3 队列的链接表示 — 链式队列
队头在链头，队尾在链尾。
链式队列在进队时无队满问题，
但有队空问题。
队空 ∧front
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
struct qnode
{elemtype data;
struct qnode *next;
};
typedef struct qnode Qnode;
Qnode * front,*rear;
链队列结点类型定义
简单类型：
头、尾指针为简单指针型变量
2009-7-30 软件基础（第 3章 堆栈和队列）
typedef struct qnode
{elemtype data;
struct qnode *next;
} Qnode;
复杂类型：
头、尾为结构体的两指针项
typedef struct
{Qnode * front;
Qnode *rear;
}Qltype;
2009-7-30 软件基础（第 3章 堆栈和队列）
链式队列存储结构的图示队列的链式存储结构
12EF
front
130A
12EF
a1 1475
130A
a2 10CB
1475
a3 ^
10CB
10CB
rear
Qnode *front,*rear;
Qltype *q;
q->front,q->rear;
或者：
2009-7-30 软件基础（第 3章 堆栈和队列）
Int initqueue(Qltype *q)
{if ((q->front=(Qnode* )malloc(sizeof(Qnode)))==NULL)
{printf(“\n申请空间失败 !”);
return 0;}
q->rear=q->front;
q->front->next=NULL;
return 1;
}
链队列的初始化
12EF
front
12EF
rear NULL
2009-7-30 软件基础（第 3章 堆栈和队列）
链队列的入队示意
12EF
front
*p
130A
p
NULL130A
*p
1475
p
x NULLx NULL1475
12EF
rear
130A
rear
1475
rear
int addq (Qltype *q,elemtype x)
{Qnode *p;
if ((p=(Qnode* ) malloc(sizeof(Qnode)))==NULL)
{printf (“\n申请空间失败 !”); return 0;}
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
return 1;
}
a1front a2 ∧
rear rear
链队列的入队算法
p
X ∧
2009-7-30 软件基础（第 3章 堆栈和队列）
链队列的出队
y
1475
p
12EF
front
a2 NULL1475
a1 130A
130A
a1
1475
rear
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue (Qltype *q)
{elemtype y;
Qnode *p;
if (q->front->next==NULL) return NULL;
p=q->front->next;
y=p->data;
q->front->next=p->next;
free(p);
return (y);
}
链队列的出队算法
a1front a2 ∧
rear
p a1
y
2009-7-30 软件基础（第 3章 堆栈和队列）
3.3.4 队列的应用 ——
在计算机运行期间,经常会出现这样的情况,程序正在执行应用程序,用户可以从键盘上输入数据,这是所谓的多进程处理,
多进程处理方式,
应用程序进程执行时,系统不断地检测键盘的状态,
一旦测得新字符输入,立刻存入缓冲区中,然后继续执行原有的进程,当原有的进程结束时,再处理键盘缓冲区的字符,
1,键盘输入循环缓冲区问题
2009-7-30 软件基础（第 3章 堆栈和队列）
问题描述,程序中存在两个进程进程 1:在屏幕上显示 1~10000.
进程 2:将键盘敲入的字符存入输入缓冲区 (循环队列 ),这些字符并不马上显示出来,直到用户键入,;”号时,或者，屏幕显示完成后，再显示所键入的所有字符,
#include <stdio.h>
#include <conio.h>
#include <dos.h>
typedef struct
{elemtype queue[MAXLEN];
int front;
int rear;
} sequeue;
void iniqueue(sequeue *q)
{q->front=0;
q->rear=0;
}
#define MAXLEN 100
typedef char elemtype;
2009-7-30 软件基础（第 3章 堆栈和队列）
int addqueue(sequeue *q,elemtype x)
{if ((q->rear+1)%MAXLEN==q->front)
{printf("\nqueue full");
return 0;
}
q->rear=(q->rear+1)%MAXLEN;
q->queue[q->rear]=x;
return 1;
}
2009-7-30 软件基础（第 3章 堆栈和队列）
elemtype delqueue(sequeue *q)
{if (q->front==q->rear)
{printf("\nqueue empty");
return 0;
}
q->front=(q->front+1)%MAXLEN;
return (sq->queue[sq->front]);
}
main()
{
char ch;
sequeue buffer;
int i;
iniqueue(&buffer);
printf(“\n”);
for(i=1;i<=10000;i++)
{ printf(“%d”,i);
if(kbhit())
{
if((ch=getch())==?;?) break;
if(! addqueue(&buffer,ch))break;
}
// delay(500);
}
/*初始化 */
/*检测是否有键盘输入,<conio.h> */
/*检测是否输入 ‘ ； ’ */
/*入队 */
2009-7-30 软件基础（第 3章 堆栈和队列）
printf(“\n”);
while((ch= delqueue(&buffer))!=0)
{
printf(“%c”,ch);
}
}
/*出队 */
/*显示出队元素 */
2009-7-30 软件基础（第 3章 堆栈和队列）
总结：
概念：队列，队头，队尾，队满，队空，上溢，下溢，
假上溢，顺序队列，循环队列，链队列。
算法：初始化，入队，出队，取队元素。
（循环队列，链队列）
应用：键盘输入缓冲区问题作业,p87-88 3-1(理解 ),3-2,3-3,3-7,3-12
