基于循环链表的队列的基本操作

描述

用带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针）。实现该队列的入队出队以及判断队列是否为空操作。

输入

多组数据，每组数据有两行。第一行为两个整数n和m，n表示入队序列A的长度（n个数依次连续入队，中间没有出队的情况），m表示出队序列B的元素数量（m个数依次连续出队，中间没有入队的情况）。第二行为序列A（空格分隔的n个整数）。当n和m都等于0时，输入结束。

输出

对应每组数据输出一行。每行包括m+1个整数，前m个数代表出队序列B的各个整数，最后一个整数表示队列是否为空，队列为空输出0，不为空输出1。整数之间用空格分隔。

输入样例 1

5 3
1 3 5 3 6
4 4
-1 2 3 4
0 0

输出样例 1

1 3 5 1
-1 2 3 4 0

AC 代码

#include <iostream>

#define MAX 100

using namespace std;
    
typedef struct              // 可以认为队列本质上就是一个数组，front和rear是两个特殊的索引
{
    int *base;
    int front;
    int rear;       
}queue;

void initQueue(queue &q)    // 循环链表初始化即为两个索引都置为 0
{
    q.base = new int [MAX];
    q.front = q.rear = 0;
}

void enQueue(queue &q, int e)
{
    if ((q.rear + 1) % MAX == q.front)
    {
        cout << "队列已满，不允许入队！" << endl;
        return ;
    }
    else 
    {
        q.base[q.rear] = e;             // 插入数据
        q.rear = (q.rear + 1) % MAX;    // 进行尾索引的更新，注意由于可能为负数，因此使用取余法的绝对值
    }
}

void deQueue(queue &q)
{
    cout << q.base[q.front] << " ";
    q.front = (q.front + 1) % MAX;
}

bool isEmpty(queue q)
{
    return (q.front == q.rear) ? 1 : 0;
}

int main()
{
    int n, m;
    while (true)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;
        queue q;
        initQueue(q);
        
        while (n --)
        {
            int x;
            cin >> x;
            enQueue(q, x);
        }
        while (m --)
            deQueue(q);            
        
        cout << !isEmpty(q) << endl;
        
    }
    
    return 0;
}