|
/本程序中对循环队列包含队列初始化、入队、出队、遍历、判断循环队列是否为空或者已满等基本常用操作/
/好啦~现在来讲循环队列出现的原因：：因为队列入队和出队front和rear都是向后移动的，那么我们前面的元素一旦出队之后，这些空间都不能得到合理的利用了，那么这对于计算机来说，是一个极大的空间资源的浪费，于是就有了循环队列的出现啦/
#include<stdio.h>
#include<stdlib.h>
typedef struct queue
{
int* base;
int front;
int rear;
}queue;
void initqueue(queue*);//队列的初始化
bool enqueue(queue*,int);//入队
bool outqueue(queue*, int*);//出队
void traverse(queue*);//遍历
bool emptyqueue(queue*);//判断队列是否为空
bool fullqueue(queue*);//判断队列是否已满
int main(void)
{
queue q;
int val;
initqueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5);
enqueue(&q, 6);
enqueue(&q, 7);
enqueue(&q, 8);
enqueue(&q, 9);
traverse(&q);
printf("\n");
outqueue(&q, &val);
outqueue(&q, &val);
outqueue(&q, &val);
traverse(&q);
system(“pause”);
return 0;
}
void initqueue(queuepQ)
{
pQ->base = (int)malloc(sizeof(int) * 6);//存放六个整数的数据元素
//相当于是一个数组的首地址
pQ->front = 0;
pQ->rear = 0;
//刚开始将front和rear都指向尾0
}
bool fullqueue(queuepQ)
{
/如果front所指向的位置的下一个位置就是rear时，那么代表循环队列已满了，即循环队列中还有一个空位的时候，队列就满了。因为如果我们将循环队列所有的位置都存储了元素，那么栈满的条件就是frontrear，这和栈空的条件是一样的；所以当我们直到frontrear时，是不能判断出栈空还是栈满的，这时我们可以将循环队列的最后一个位置上不存储元素，当循环队列中恰好有一个空位的时候，队列就满了，这对于队列来讲是不浪费空间的哦（同时我们也可以做一个标志性的判断的变量flag，当flag0的时候，frontrear时，栈满；当flag1且rearfront时，栈空）/
if (pQ->front == (pQ->rear + 1) % 6)
{/那么为什么rear的下一个位置要用pQ->rear + 1) % 6呢？？因为本程序中所用的存储结构时循环队列，可能该元素的下一个位置就是该循环队列的第一个位置了，即又回到了开头的位置/
return true;
}
else
{
return false;
}
}
bool enqueue(queuepQ,int val)
{
if (fullqueue(pQ))
{/注意在队列还没有满的时候才能入队/
return false;
}
else
{
pQ->base[pQ->rear] = val;
pQ->rear = (pQ->rear + 1) % 6;
return true;
/注意在入队后，要将pQ->rear 移动的下一个位置(pQ->rear + 1) % 6，至于为什么要%6上面已经讲 的很清楚了
}
}
bool emptyqueue(queuepQ)
{
if (pQ->rear == pQ->front)
{/刚开始对队列初始化的时候，pQ->rear == pQ->front=0，但是我们之后对循环队列进行插入和删除数据之后，该pQ->rear 和 pQ->front可能不为0，但是一定是相等的，即指向同一个位置/
return true;
}
else
{
return false;
}
}
bool outqueue(queuepQ, intval)
{/注意在出队列的时候一定是在循环队列还不为空的时候下出队列的/
if (emptyqueue(pQ))
{
return false;
}
else
{
val = pQ->base[pQ->front];
pQ->front = (pQ->front + 1) % 6;
return true;
/注意出队是将 pQ->front移动到下一个位置，即(pQ->front + 1) % 6，至于为什么要%6上面已经讲 的很清楚了/
}
}
void traverse(queuepQ)
{/注意在进行遍历操作时，是不能改变队列的front和rear的位置的/
int i = pQ->front;
while (i!=pQ->rear)
{
printf("%d\t", pQ->base[i]);
i++;//注意i一定要++，否则会称为死循环
}
}
|