通过设置标志位tag判断队空队满的顺序存储的循环队列

我们首先需要了解的是:循环队列的实现有三种方式

  1. 浪费一个元素的存储空间:front指向队首的实际位置,rear指向实际位置的下一个位置,front==rear时为空,(rear+1) % m == front时为满
  2. 使用标记tag,front指向队首实际位置,rear指向队尾实际位置的下一个位置,入队时tag=1,出队时tag=0,当front == rear && tag == 0时队空,当front == rear && tag == 1时队满
  3. 使用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
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

你可能感兴趣的