設(shè)計一個環(huán)形隊列，用front和rear分別作為隊頭和隊尾指針，另外用一個tag表示隊列是空 ( 0 ) 還是不空 ( 1 )，這樣就可以用front==rear作為隊滿的條件。要求設(shè)計隊列的相關(guān)基本運算算法。

前置技能

• 環(huán)形隊列
  隊列中進出時需要大量前移后移操作，除了鏈式隊列，使用環(huán)形隊列挪動下標也是一個不錯的選擇。隊列的數(shù)據(jù)類型定義參考書第45頁。

環(huán)形隊列

具體實現(xiàn)

原理很簡單，實現(xiàn)的時候要注意判斷tag在數(shù)入隊、出隊時，是否要轉(zhuǎn)換真假值。另外清除隊列時只需要把頭尾相對，隊列標空。

#include<iostream>

template<class T>
class queue{
    private:
        int maxsize;
        int front;
        int rear;
        bool tag;
        T *data;
    public:
        queue(int size){
            maxsize = size;
            front = 0;
            rear = 0;
            tag = false;
            data = new T [size];
        }
        ~queue(){
            delete data;
        }
        void clear(){            //清除
            rear = front;
            tag = false;
        }
        bool enqueue (T tmp){    //入隊
            if(full()){
                return false;
            }
            else{
                if(empty()){
                    tag = true;
                }
                data[rear] = tmp;
                rear = (rear+1) % maxsize;
                return true;
            }
        }
        bool dequeue (T &tmp){   //出隊
            if(empty()){
                return false;
            }
            else{
                tmp = data[front];
                front = (front+1) % maxsize;
                if(front == rear){
                    tag = false;
                }
                return true;
            }
        }
        bool getfront (T &tmp){
            if(empty()){
                return false;
            }
            else {
                tmp = data[front];
                return true;
            }
        }
        bool empty(){
            if (rear == front && tag == false){
                return true;
            }
            else{
                return false;
            }
        }
        bool full(){
            if (rear == front && tag == true){
                return true;
            }
            else{
                return false;
            }
        }
};