环形队列

beyes

代码：

#include <stdio.h>

#define MAXQUEUE    10    /*队列最大容量*/

int    queue [MAXQUEUE];    /*队列数组*/
int    front = -1;        /*队列的队头*/
int    rear = -1;        /*队列的队尾*/

/*数据的存入*/
int enqueue (int value)
{
    if (rear + 1 == front || (rear == (MAXQUEUE - 1) && front <= 0)) /*队列全满?*/
        return (-1);
    rear++;
   
    if (rear == MAXQUEUE)
        rear = 0;

    queue[rear] = value;
}       

/*取出队列数据*/
int dequeue()
{
    if (front == rear)    /*检查队列是否为空*/
        return (-1);
    front++;
    if (front == MAXQUEUE)
        front = 0;    /*从头开始*/

    return (queue [front]);
}

void main()
{
    int input [100];
    int output [100];
    int select;
    int i_count = 0;
    int o_count = 0;
    int loop = 1;
    int i, temp;

    while (loop) {
        /*选项内容*/
        printf ("[1]输入 [2]取出 [3]列出全部内容 ==> ");
        scanf ("%d", &select);
   
        switch (select) {
            case 1:
                printf ("请输入存入队列的值(%d) ==> ", i_count + 1);
                scanf ("%d", &temp);
                if (enqueue(temp) == -1)
                    printf ("队列全满.\n");
                else
                    input [i_count++] = temp;
                break;

            case 2:
                if ((temp = dequeue()) == -1)
                    printf ("队列是空的.\n");
                else {
                    printf ("取出队列元素: %d\n", temp);
                    output [o_count++] = temp;
                }
                break;

            case 3:
                loop = 0;
                break;
       
            }
    }

    printf ("输入队列的元素: ");
    for (i = 0; i < i_count; i++)
        printf ("[%d]", input[i]);

    printf ("\n取出队列的元素: ");
    for (i = 0; i < o_count; i++)
        printf ("[%d]", output[i]);

    printf ("\n剩下队列的元素: ");
        while ((temp = dequeue()) != -1)
            printf ("[%d]", temp);

    printf ("\n");
}

运行与输出：

[1]输入 [2]取出 [3]列出全部内容 ==> 1
请输入存入队列的值(1) ==> 32
[1]输入 [2]取出 [3]列出全部内容 ==> 1
请输入存入队列的值(2) ==> 88
[1]输入 [2]取出 [3]列出全部内容 ==> 1
请输入存入队列的值(3) ==> 78
[1]输入 [2]取出 [3]列出全部内容 ==> 1
请输入存入队列的值(4) ==> 3
[1]输入 [2]取出 [3]列出全部内容 ==> 1
请输入存入队列的值(5) ==> 8
[1]输入 [2]取出 [3]列出全部内容 ==> 2
取出队列元素: 32
[1]输入 [2]取出 [3]列出全部内容 ==> 2
取出队列元素: 88
[1]输入 [2]取出 [3]列出全部内容 ==> 3
输入队列的元素: [32][88][78][3][8]
取出队列的元素: [32][88]
剩下队列的元素: [78][3][8]

说明：
检查队列是否全满有两种情况：
1、rear 和 front 都在移动，且 rear + 1 = front  时，队列全满。

2、rear 一直在移动填充数据，而 front 却还没移动，所以当 rear 到达 MAXQUEUE - 1 时，队列亦表示全满。

所以这两种情况表示为：

rear + 1 == front || (rear == (MAXQUEUE - 1) && front <= 0)