C/C++ 循环队列实现（完整代码）

Bertha 。 2022-01-16 07:31 277阅读 0赞

循环队列比单链表实现队列会稍微要难理解一点，但是弄懂了其中的原理，就不会感觉到困难啦～～～

循环队列的结构体:用count来记录元素的个数容易判断队列是否是空或者满。

typedef struct queue{
        int count;    //记录元素个数
        int front;    //队首
        int rear;     //队尾
        int data[MAX_SIZE];   //记录元素的值
    }Queue;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70][]

队首、队尾在数组中的位置，循环链表主要是想表现不浪费空间，如果我们用数组但是不循环的话，出队后front会往上一动一个单位，那么下面的空间就无法利用到了，这是做循环链表的一个优势。

当我们入队出队会遇到下图的情况，队首在队尾的上面，那么我们怎么继续出队或者入队呢？

> 出队：队列出队front要+1，那么当front大于我们数组的长度的时候要怎么样取像图中值为23这个位置的数组下标呢？
> 
>            注：MAX\_SIZE = 5
> 
>            公式： ptr->front = (ptr->front + 1) % MAX\_SIZE; 当ptr->front = 4,然后 ptr->front + 1 = 5时，(ptr->front + 1) %            
> 
>             MAX\_SIZE = 0，那么我们就可以取到23这个值的下标了。
> 
> 入队：与出队类似。 ptr->rear = (ptr->rear + 1) % MAX\_SIZE;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70 1][]

/*  完整代码  */
    #include <iostream>
    
    using namespace std;
    #define MAX_SIZE 5
    
    typedef struct queue{
        int count;
        int front;
        int rear;
        int data[MAX_SIZE];
    }Queue;
    
    void Init(Queue* ptr) { //初始化队列
        ptr->count = 0;
        ptr->front = 0;
        ptr->rear = -1;
    }
    
    bool QueueFull(Queue* ptr) {  //判断队列是否满 
        return ptr->count >= MAX_SIZE;
    }
    
    bool QueueEmpty(Queue* ptr) {   //判断队列是否为空
        return ptr->count <= 0;
    }
    
    void Append (Queue* ptr, int item) {    //入队
        if (QueueFull(ptr)) {
            cerr << "队列满了!" << endl;
            return;
        }else {
            ptr->count ++;
            ptr->rear = (ptr->rear + 1) % MAX_SIZE;
            ptr->data[ptr->rear] = item;
        }
    }
    
    void Pop(Queue* ptr) {  //出队
        if (QueueEmpty(ptr)) {
            cerr << "队列为空!" << endl;
            return;
        }else {
            ptr->count --;
            ptr->front = (ptr->front + 1) % MAX_SIZE;
        }
    }
    
    int QueueSize (Queue* ptr) {    //返回队列长度
        return ptr->count;
    }
    
    void Show(Queue* ptr) { //遍历队列
        if(QueueEmpty(ptr)) {
            cout << "队列为空!" << endl;
            return;
        }else {
            cout << "队列遍历: ";
            int i = ptr->front;
            while (i != ptr->rear) {
                cout << ptr->data[i] << " ";
                i ++;
                i = i % MAX_SIZE;
            }
            cout << ptr->data[ptr->rear] << " ";
        }
        cout << endl;
    } 
    
    
    int main() {
        Queue* dummy = (Queue *)malloc(sizeof(Queue));  //申请结点空间
        Init(dummy);
    
        Append(dummy, 11);
        Append(dummy, 5);
        Append(dummy, 23);
        Append(dummy, 18);
        Pop(dummy);
        Show(dummy);
        
    
        Append(dummy, 33);
        Pop(dummy);
        Show(dummy);
        
        
        Append(dummy, 77);
        Show(dummy);
    
    
    
        return 0;
    }
    
    运行结果：
    
    队列遍历: 5 23 18 
    队列遍历: 23 18 33 
    队列遍历: 23 18 33 77

> 温馨提示：转载请联系作者，有问题可以留言。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70]: /images/20220114/0170f04dc92e4ce0bbd4019dbff27bc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTI2NDcx_size_16_color_FFFFFF_t_70 1]: /images/20220114/c59ef0832a3e472fae57c6958a8f66cd.png