题目：

若希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分队头指针front和队尾指针rear相同时队列状态是空还是满。试编写与此结构相对应的入队和出队算法。

front ==rear && tag ==0,队空；

front ==rear && tag ==1,队满；

初始化：
#define MaxSize 50;
typedef struct{
    ElemType data[MaxSize];
    int front,rear,tag;
}SqQueue;

入队：
bool EnQueue(SqQueue &Q,ElemType x){
    if(Q.tag == 1 && Q.front == Q.rear) return false; //队满不允许插入元素；
    
    //初始时，front=rear=-1，增加元素时，rear先加1再赋值；
    Q.rear = (Q.rear +1)%MaxSize; //需要插入元素的位置；
    Q.data[Q.rear] = x;
	//如果队满；
	Q.tag =1;
    return true;
}

出队：
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.tag ==0 && Q.front ==Q.rear) return false; //队空，不再删除元素；
    
    //假设front初始时为-1，则删除元素时，front先加1再删除元素；
    Q.front = (Q.front+1)%MaxSize;
    x = Q.data[Q.front];
    //如果队空；
    Q.tag =0;
    return true;
}

我们首先需要了解的是：循环队列的实现有三种方式
浪费一个元素的存储空间：front指向队首的实际位置，rear指向实际位置的下一个位置，front==rear时为空，(rear+1) % m == front时为满
使用标记tag，front指向队首实际位置，rear指向队尾实际位置的下一个位置，入队时tag=1，出队时tag=0，当front == rear && tag == 0时队空，当front == rear && tag == 1时队满
使用front,rear, length作为判断队空队满的标志，这样就不用浪费一个元素的存储空间了，和tag的作用是一样的，front指向队首实际位置，rear指向队尾实际位置
这里我只实现一下第二种：
首先我们定义一个具有基本操作方法的Queue类，在这个类中我们设置了一个bool型的变量tag，通过判断tag的值来判断队列是否为空、是否为满。具体是：rear==front&&!tag为空，rear==front&&tag为满。

queue.h如下：
#ifndef QUEUE_H
#define QUEUE_H

#include<iostream>
using namespace std;

template<class T>
class Queue {
private:
    int maxSize;                           //存放队列数组的大小
    int front;                             //表示队头所在位置的下标
    int rear;                              //表示队尾所在位置的下标
    int *queue;                            //存放类型为T的队列元素的数组
    bool tag;                              //0为空，1为不空
public:
    Queue(int size);
    ~Queue() {
    delete[] queue;
    }
    void Clear();                          //清空队列
    bool EnQueue(const T item);            //item入队，插入队尾
    bool DeQueue(T & item);                //返回队头元素，并删除该元素
    bool GetFront(T & item);               //返回队头元素但不删除
    void disPlay();                        //输出队列
};

template<class T>
Queue<T>::Queue(int size) {
    maxSize = size;
    tag = 0;
    queue = new T[maxSize];
    front = rear = 0;
}

template<class T>
void Queue<T>::Clear() {
    front = rear;
    tag = 0;
}

template<class T>
bool Queue<T>::EnQueue(const T item) {
    if (rear==front&&tag) {
        cout << "队列已满，溢出！" << endl;
        return false;
    }
    queue[rear] = item;
    rear = (rear + 1) % maxSize;
    tag = 1;
    return true;
}

template<class T>
bool Queue<T>::DeQueue(T & item) {
    if (rear==front&&!tag) {
        cout << "队列为空，溢出！" << endl;
        return false;
    }
    item = queue[front];
    front = (front + 1) % maxSize;
    tag = 0;
    return true;
}

template<class T>
bool Queue<T>::GetFront(T & item) {
    if (rear==front&&!tag) {
        cout << "队列为空，溢出！" << endl;
        return false;
    }
    item = queue[front];
    return true;
}

template<class T>
void Queue<T>::disPlay() {
    if (rear==front&&!tag) {
        cout << "队列为空！" << endl;
        return;
    }
    if (front == rear&&tag!=0) {
        for (int i = 0; i < maxSize; i++) {
            cout << queue[i] << " ";
        }
    }
    for (int i = front;; i = (i + 1) % maxSize) {
        if (i == rear)
            break;
        cout << queue[i] << " ";
    }
    cout << endl;
}
#endif // !QUEUE_H

	

☝☝☝ 软件工程考研独家平台
撰稿 | 康康哥
编辑 | 丽丽姐
本文由懂计算机、软件工程的博士师哥原创
双日练：NO.20200922
循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是 ( )。
A．队空：end1 == end2；队满：end1 == (end2+1)mod M
B．队空：end1 == end2；队满：end2 == (end1+1)mod (M-1)
C．队空：end2 == (end1+1)mod M；队满：end1 == (end2+1)mod M
D.  队空：end1 == (end2+1)mod M；队满：end2 == (end1+1)mod (M-1)
本题考查：循环队列判断队空队满。
循环队列判断队满：Q.front== (Q.rear + 1) % MAXSIZE；
判断队空： Q.front== Q.rear；
将end1替换front，end2替换rear，因此得：
队空：end1 == end2；
队满：end1 == (end2+1)modM。
因此选A。
软工博士带你飞
考软工 · 看CS优化狮

标循环队列判断队满和队空的条件
队满：front=(rear+1)%size ;

队空：front = rear&&



图片上的信息来自王红梅教授版数据结构第二版