数据结构(线性结构的应用之二-----队列)
定义
一种可以实现“先进先出”的存储结构
分类
(1)链式队列 — 用链表实现
(2)静态队列 — 用数组实现
静态队列通常都必须是循环队列
循环队列
静态队列为什么必须是循环队列
循环队列需要几个参数来确定
需要两个参数来确定 front,rear
循环队列各个参数的含义
这两个参数在不同场合有不同的含义
建议初学者先记住,然后慢慢体会
(1)队列初始化
font和rear的值都是零
(2)队列非空
font代表的是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个元素
(3)队列空
font和rear的值相等,但不一定是零
循环队列入队为算法讲解
两步完成:
(1)将值存入r所代表的位置
(2)错误的写法rear = rear +1,正确写法:rear = (rear+1)%数组的长度
循环队列出队为算法讲解
font= (font+1)%数组的长度
如何判断循环队列是否为空
如果 front 与 rear 的值相等
如何判断循环队列是否已满
两种方式:
(1)多增加一个标志参数
(2)少用一个元素
如果r和f的值紧挨着,则队列已满
if( (r+1)%数组的长度 == f)
已满
else
不满
队列算法
(1)入队
(2)出队
循环队列的实例
# include <stdio.h>
# include <stdlib.h>
typedef struct Queue { // 创建一个队列的结构体类型
int * pBase;
int front;
int rear;
}QUEUE; // QUEUE 等价于 struct Queue
void init(QUEUE *);
bool en_queue(QUEUE *, int);
void traverse_queue(QUEUE *);
bool out_queue(QUEUE *, int *);
bool full_queue(QUEUE *);
int main(void)
{
QUEUE Q;
int val;
init(&Q);
en_queue(&Q, 1);
en_queue(&Q, 2);
en_queue(&Q, 3);
en_queue(&Q, 4);
en_queue(&Q, 5);
en_queue(&Q, 6);
en_queue(&Q, 7);
traverse_queue(&Q);
if (out_queue(&Q, &val)) {
printf("出栈成功!\n");
printf("出栈的元素是:val = %d", val);
} else {
printf("出栈失败!");
}
return 0;
}
/*
队列初始化,创建一个队列,初始化了一个长度为6的数组,队头和队尾初始化相等
*/
void init(QUEUE *pQ)
{
pQ->pBase = (int *)malloc(sizeof(int) * 6);
pQ->front = 0;
pQ->rear = 0;
}
/*
判断一个队列是否已满
判断条件为队头和队尾加一相等
*/
bool full_queue(QUEUE *pQ)
{
if ( (pQ->rear + 1) % 6 == pQ->front ) // (pQ->rear + 1) % 6 这句话的意思是让队列循环
return true;
else
return false;
}
/*
入队 ,向队列中加入一个元素,只能从尾加入
*/
bool en_queue(QUEUE *pQ, int val)
{
if (full_queue(pQ))
return false;
else {
pQ->pBase[pQ->rear] = val;
pQ->rear = (pQ->rear + 1) % 6;
return true;
}
}
/*
遍历一个队列
*/
void traverse_queue(QUEUE *pQ)
{
int i = pQ->front;
while (i != pQ->rear) { // 如果i等于队尾,则循环结束
printf("%d ", pQ->pBase[i]);
i = (i+1) % 6;
}
printf("\n");
return;
}
/*
判断一个队列是否为空
为空的条件也是队头元素的位置等于队尾元素的位置
*/
bool empty_queue(QUEUE *pQ)
{
if (pQ->front == pQ->rear)
return true;
else
return false;
}
/*
出队
出队只能从队头出,并把出队的元素保存在pVal中。
*/
bool out_queue(QUEUE * pQ, int *pVal)
{
if (empty_queue(pQ))
return false;
else {
*pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front+1) % 6;
return true;
}
}
队列的具体应用
所有和时间有关的操作都与队列的影子