队列知识总结
本帖最后由 Julia999 于 2019-8-3 11:46 编辑队列
定义：
一种可以实现‘先进先出’的存储结构（只允许在一端进行插入操作，在另一端进行删除操作的线性表）
分类：
链式队列---用链表实现
静态队列---用数组实现
静态队列通常必须是循环队列
循环队列：
1.静态队列为什么一定是循环队列
2.循环队列需要几个参数来确定及其含义
2个参数 front 和rear
3.循环队列各个参数的含义
2个参数在不同场合有不同的定义
1）队列初始化：front和rear的值都是0
2）队列非空：
front代表的是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但不一定都是0
4.循环队列的入队伪算法 （如果刚开始的时候front和rear在相同的位置，那么说明这是一个空队列，那么如果需要将元素入队，那么就将元素放在front所在的位置，然后rear向后移动一个元素位置）
1.将值存入r所代表的位置
2.r=r+1;//这样写肯定是错误的
正确的写法是:r=(r+1)%数组的长度
5.循环队列的出队伪算法
f=(f+1)%数组的长度
6.如何判断循环队列是否为空
如果front和rear的值相等，该队列一定为空
7.如何判断循环队列是否已满
预备知识：
front和rear的值之间没有什么规定的谁比谁大的关系
两种方式：【通常用第二种方式】
1.多增加一个标识参数
2.少用一个元素（如果r和f紧挨着，那么队列已满）
if((r+1)%数组的长度==f)
已满
else
不满
队列算法
入队
出队
队列的具体应用：
所有和时间有关的操作都与队列都有队列的影子
#include<stdio.h>
#include<mallloc.h>
typedef struct Queue
{
int *pBase;
int front;
int rear;
}QUEUE;
void init(QUEUE *pQ)
{
*pQ->pBase(int *)malloc(sizeof(int)*6); //指向了一个24字节的数组
pQ->front=0;
pQ->rear=0;
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ)) //入队失败
return false;
else
{
pQ->pBase=val;
pQ->rear=(pQ->rear+1)%6;
return true;
}
}
bool full_queue(QUEUE *pQ)
{
if((pQ->rear+1)%6==pQ->front)
return true;
else
return false;
}
void traverse_queue(QUEUE *pQ)
{
int i=pQ->front;
while(i!=pQ->rear)
{
printf("%d ",pQ->pBase);
i=(i+1)%6;//i不断往后移
}
printf("\n");
}
bool out_queue(QUEUE *pQ,int *pVal)//出队
{
if(empty_queue(pQ))
{
return false;
}
else
{
*pVal=pQ->pBase;
pQ->front=(pQ->front+1）%6;
return true;
}
}
bool empty_queue(QUEUE *pQ)
{
if(pQ->front==pQ->rear)
return true;
else
return false;
}
int main()
{
Queue Q;
inti(&Q);
int val;
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
en_queue(&Q,4);
en_queue(&Q,5);
en_queue(&Q,6);
traverse_queue(&Q);
if(out_queue(&Q,&val))
printf("出队成功，队列出队的元素是：%d\n",val);
else
printf("出队失败！");
return 0;
}
链队列
我们将队头指针指向链队列的头结点，而队尾指针指向终端结点（头结点不是必要的，但是为了方便操作，我们加上了）
空对列的时候，front和rear都指向头结点
创建一个队列需要完成两个任务：
1.在内存中创建一个头结点
2.将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列
页:
[1]