(转)循环队列(C语言版)

循环队列(C语言版)

循环队列(C语言版)
　　 作者：刘勉刚 E-mail：[e-mail]
　　线性结构的主要操作就是插入和删除，我们前面讲过的顺序线性表、单链表、双链表都没有限制插入和删除操作的位置。如果我们限定插入和删除操作在线性表的同一端进行那么这种结构就是栈；如果限定插入在一端而删除在另一端，这种结构就是对列；栈的特点是先进后出(FILO)而对列是先进先出(FIFO)。进行插入的一端叫队尾，删除的一端叫队头。
　　队列的实现可以用顺序线性表也可以用链表。在实际使用中有一种更常用的队列叫循环队列。循环队列是把队列的头和尾在逻辑上连接起来，构成一个环。循环队列中首尾相连，分不清头和尾，此时需要两个指示器分别指向头部和尾部。插入就在尾部指示器的指示位置处插入，删除就在头部指示器的指示位置删除。
　　循环队列在插入时也要判断其是否已满，删除时要判断其是否已空。为空的条件比较简单当头部指示器和尾部指示器指向同一个位置时表示循环队列为空；因为尾部指示器指示的是最后一个元素的下一个位置，所以循环队列已满时头部指示器和尾部指示器也指向同一个位置，为了区分这两种状况有两种方法，一种增加一个标识变量来区分，另一种损失循环队列中的一个元素，即头和尾之间的位置不用，此时循环队列为满的条件变成头部指示器加1等于尾部指示器；为空的条件成为头部指示器和尾部指示器指向同一位置。
　　 循环队列的首尾相连是通过取余操作来实现的，把头和尾的位置都除以队列最大长度然后取余。当到达尾部及最后一个位置时再加1就成了队列的长度刚好可以整除余0即又回到了队头。
　　 循环队列的主要操作：
　　 (1)创建循环队列
　　 (2)初始化循环队列
　　 (3)判断循环队列是否为空
　　 (4)判断循环队列是否为满
　　 (5)入队
　　 (6)出队
　　Microsoft Visual Studio .NET 2003下的程序:

      #include

　　#define MAXSIZE 100
　　typedef struct
　　{
　　int elem[MAXSIZE];
　　int front,rear;
　　}Quque; //定义队头

　　int initQue(Quque **q) //初始化
　　{
　　(*q)->front=0;
　　(*q)->rear=0;
　　}

　　int isFull(Quque *q)
　　{
　　if(q->front==(q->rear+1)%MAXSIZE) //判满 刘勉刚
　　return 1;
　　else
　　return 0;
　　}
　　int insertQue(Quque **q,int elem)
　　{
　　if(isFull(*q)) return -1;
　　(*q)->elem[(*q)->rear]=elem;
　　(*q)->rear=((*q)->rear+1)%MAXSIZE; //插入
　　return 0;
　　}
　　int isEmpty(Quque *q)
　　{
　　if(q->front==q->rear) //判空
　　return 1;
　　else
　　return 0;
　　}
　　int deleteQue(Quque ** q,int *pelem)
　　{
　　if(isEmpty(*q))
　　return 0;
　　*pelem=(*q)->elem[(*q)->front];
　　(*q)->front =((*q)->front +1)%MAXSIZE;
　　return 0;
　　}

　　int main(void)
　　{
　　int i=0,elem;
　　Quque *q=(Quque *)malloc(sizeof(Quque));
　　initQue(&q);
　　for(;i<10;i++)
　　{
　　insertQue(&q,i);
　　}
　　for(i=0;i<10;i++)
　　{
　　deleteQue(&q,&elem);
　　printf("%d\n",elem);
　　}
　　system("pause");
　　return 0;
　　}