题目：
 若希望循环队列中的元素都能得到利用，则需设置一个标志域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

标循环队列判断队满和队空的条件
 
队满：front=(rear+1)%size ;
 队空：front = rear&&
 
 图片上的信息来自王红梅教授版数据结构第二版

在引用循环队列前，我们需要了解队列是如何线性实现的。 
  
 简单地讲，便是当队列为空时，front = rear = 0,每当插入元素尾指针+1，删除元素是头指针-1。但是，我们会发现一个问题，如上面的第四个图，0，1，2三个空间并没有使用。因此，为了占用该空间，我们使用了循环队列来实现。 
 循环队列原理图： 
  
 我们可以发现，当循环队列属于上图的d1情况时，是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的，可以通过牺牲一个存储空间来实现。 
 如上图d2所示， 
 队头指针在队尾指针的下一位置时，队满。 Q.front == (Q.rear + 1) % MAXSIZE 因为队头指针可能又重新从0位置开始，而此时队尾指针是MAXSIZE - 1，所以需要求余。 
 当队头和队尾指针在同一位置时，队空。 Q.front == Q.rear;
 
以下是实现的代码：
 
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 100  //最大队列长度
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *base;  //队列空间
    int front;   //队头指针
    int rear;       //队尾指针，若队尾不为空，则指向队尾元素的下一个位置
}SqQueue;

//初始化循环队列
Status initQueue(SqQueue &Q) {
    Q.base = (ElemType *) malloc(MAXSIZE * sizeof(ElemType));  //申请空间
    Q.front = Q.rear = 0;       //队空
    return OK;
}

//入队
Status enQueue(SqQueue &Q, ElemType e) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; //队满，无法添加
    Q.base[Q.rear] = e;  //插入元素
    Q.rear =  (Q.rear + 1) % MAXSIZE; //队尾指针+1
    return OK;
}

//出队
Status deQueue(SqQueue &Q, ElemType &e) {
    if (Q.front == Q.rear) return ERROR; //队空，无法删除
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;  //队头指针+1
    return OK;
}

//返回队列长度
Status length(SqQueue &Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; 
}