队列(Queue）在整个数据结构中也是非常重要的一部分。之前经历的发现不论是期中考试还是assignment，队列的出镜率是非常高的。链式队列由链表实现，静态队列则由数组实现。这里我简单做一个复习小结。
定义
队列就是一种可以实现“先进先出（FIFO)”的存储结构。
分类
-
链式队列–用链表实现
-
静态队列–用数组实现 （静态队列通常都是循环队列）
循环队列：
（概括了下面7个问题）
-
静态队列为什么必须是循环队列？
-
循环队列需要几个参数来确定？(2个参数缺一不可，不同场合有不同含义)
1）初始化
front和rear都是零
2）队列非空
front代表队列第一个元素
rear代表队列最后一个有效元素的下一个元素
3）队列空
front和rear的值相等，但不一定是0
-
循环队列的各个参数的含义
-
循环队列入队伪算法
1)将值存入r所代表的位置
2）r=(r+1)%数组的长度
//比如r=0;(0+1)%6=0余1，所以结果还是1，巧妙
- 循环队列出队伪算法
f=(f+1)%数组的长度
- 如何循环队列是否为空？
如果front和rear的值相等，则该队列一定为空
- 如何判断循环队列是否为满？
静态队列程序
####代码
#include <stdio.h>
#include <malloc.h>
typedef struct queue
{
int *pbase;
int front;
int rear;
}QUEUE;
void init(QUEUE *pQ)
{
pQ->pbase=(int *)malloc(sizeof(int) *6); //pbase为数组首地址名
pQ->front=0;
pQ->rear=0;
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ))
{
return flase;
}
else
{
pQ->pbase[pQ->rear]=val;
pQ->rear=(pQ->rear+1)%6;//6是数组长度
}
}
bool full_queue(QUEUE *pQ)
{
if ((pQ->rear+1)%6==pQ->front)
reuturn true;
else
return flase;
}
void traverse_queue(QUEUE *pQ)
{
int i=pQ->front;
while(i!=pQ->rear)
{
printf("%d",pq->pbase[i]);
i=(i+1)%6;
}
return;
}
bool emput(QUEUE *pQ)
{
if (pQ->front=pQ->rear)
return true;
else
return flase;
}
bool out_queue(QUEUE *pQ,int *pval)
{
if(emput_queue(pQ))
{
return flase;
}
else
{
*pval=pQ->pbase[pQ->front];
pQ->front=(pQ->front+!)%6;
}
}
int main()
{
QUEUE Q;
init(&Q);
en_queue(&Q,1);
en_QUEUE(&Q,2);
traverse_queue(&Q);
if(out_queue(&Q,&val)
{
printf("success,%d\n",val);
}
else
{
printf("failed\n");
}
return 0;
}
队列应用
所有和时间和有关的操作
