image

引言

中午在食堂打飯，真是一個令人頭疼的事情，去食堂的路上也總是步伐匆匆，為什么啊，這還用說，遲一點(diǎn)去，你就會知道什么叫做人山人海了，在食堂排隊的時候，相比較學(xué)生來說，打飯阿姨畢竟是少數(shù)，在每個窗口都有人的時候，不免我們就得等待，直到前面的一個學(xué)生打完飯離開，后面排隊的人才可以繼續(xù)向前走，直到輪到自己，別提多費(fèi)勁了，但是秩序和規(guī)則卻是我們每個人都應(yīng)該遵守的，也只能抱怨自己來的遲了

這種 “先進(jìn)先出” 的例子就是我們所講的基本數(shù)據(jù)結(jié)構(gòu)之一 ”隊列“

例子補(bǔ)充：用電腦的時候，有時候機(jī)器會處于疑似死機(jī)的狀態(tài)， 鼠標(biāo)點(diǎn)什么似乎都沒有用，雙擊任何快捷方式都不動，就當(dāng)你失去耐心，打算reset的時候，突然它就像酒醒了一樣，把你剛才點(diǎn)擊的所有操作全部按照順序執(zhí)行了一遍，這其實(shí)是因為操作系統(tǒng)中的多個程序隱需要通過一個通道輸出，而按照先后次序排隊等待造成的 ——《大話數(shù)據(jù)結(jié)構(gòu)》

隊列的基本定義

定義：隊列是一種只允許在一段進(jìn)行刪除操作，在另一端進(jìn)行插入操作的線性表

允許插入的一段稱作隊尾 (rear)，允許刪除的的一端稱為隊頭 (front)

隊列的數(shù)據(jù)元素又叫做隊列元素，在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊 ，也正是因為隊列只允許在一段插入，另一端刪除，所以這也就是我們前面例子中體現(xiàn)出來的先進(jìn)先出 (FIFO-first in first out) 的概念

image

補(bǔ)充：除此之外，還有的隊列叫做雙端隊列，也就是可以在表的兩邊進(jìn)行插入和刪除操作的線性表

雙端隊列分類：

1. 輸出受限的雙端隊列：刪除操作限制在表的一段進(jìn)行，而插入操作允許早表的兩端進(jìn)行

2. 插入操作限制在表的一段進(jìn)行，而刪除操作允許在表的兩端進(jìn)行

隊列的抽象數(shù)據(jù)類型

#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <exception>
using namespace std;

// 用于檢查范圍的有效性
class outOfRange:public exception {     
public:    
    const char* what()const throw() {   
        return "ERROR! OUT OF RANGE.\n";
    } 
};  

// 用于檢查長度的有效性
class badSize:public exception {            
public:    
    const char* what()const throw() {
        return "ERROR! BAD SIZE.\n";
    }  
}; 

template <class T>
class Queue {
public:
    //判隊空 
    virtual bool empty() const = 0;
    //清空隊列 
    virtual void clear() = 0;
    //求隊列長度 
    virtual int size() const = 0;
    //入隊 
    virtual void enQueue(const T &x) = 0;
    //出隊 
    virtual T deQueue() = 0;
    //讀隊頭元素 
    virtual T getHead() const = 0;
    //虛析構(gòu)函數(shù) 
    virtual ~Queue(){} 
};
#endif 

循環(huán)隊列

隊列作為一個特殊的線性表，自然也有著順序以及鏈?zhǔn)酱鎯煞N方式，我們先來看看它的順序存儲方式——循環(huán)隊列

在隊列的順序存儲中，我們除了創(chuàng)建一個具有一定空間的數(shù)組空間外，還需要兩個指針，分別指向隊列的前端和微端，下面的代碼中，我們選擇將隊頭指針指向頭元素的前一個位置，隊尾指針指向隊尾元素（當(dāng)然這不是唯一的方式，還可以將頭指針指向頭元素，隊尾指針指向隊尾元素的后一個位置，原理是基本一致的）

為什么要這么做，并且為什么這種存儲我們叫做循環(huán)隊列？

我們一步步分析一下：

我們先按照我們一般的想法畫出隊列元素進(jìn)出隊的過程，例如隊列元素出隊

image

這樣的設(shè)想，也就是根據(jù)我們前面食堂排隊的例子畫出來的，但是我們可以清晰的看到，當(dāng)a0出隊后，a0后的元素全部需要前移，將空位補(bǔ)上，但我們在計算機(jī)中講究性能二字，如何可以提高出隊的性能呢？

循環(huán)隊列就這樣被設(shè)計出來了，我們?nèi)绻辉傧拗脐狀^一定在整個空間的最前面，我們的元素也就不需要集體移動了

image

問題一

這個時候我們就需要考慮這樣的問題了：

① 如何為了解決只有一個元素的時候，隊頭和隊尾重合使得處理變得麻煩？

• 這時我們前面提到的兩個指針就派上用場了（隊頭指針指向頭元素的前一個位置，隊尾指針指向隊尾元素）當(dāng)頭尾指針相等的時候，代表是空隊列

問題二

但是有一個大問題出現(xiàn)了 ！

如果前面有空閑的空間還好說，一旦頭元素前面沒有空間，我們的隊頭指針就指向到了數(shù)組之外，也就會出現(xiàn)數(shù)組越界問題，這該怎么辦呢？

我們可以看到，雖然我們的表頭已經(jīng)沒有了任何空間，但是表的后半部分還有空余空間，這種現(xiàn)象我們稱作假溢出，打個比方，接近上課你緩緩走進(jìn)教室，看到只有前排剩下了兩個位置，你總不會轉(zhuǎn)身就走吧，當(dāng)然可以去前排坐，只有實(shí)在沒座位了，才考慮離開

我們可以做出這樣一種比較可行的方案

• 我們只需要將這個隊列收尾連接起來，當(dāng)后面的空間滿后，接著從前面空出來的空間中進(jìn)隊，同樣的，我們的表頭指針也找到了可以指向的位置
• 具體的連接方法，就是將date[0...maxSize] 的單元0認(rèn)為是maxSize - 1

問題三

我們剛才也提到了，當(dāng)表頭指針和表尾指針相等的時候就解決了空隊列的情況，但是在表滿的情況下，你會發(fā)現(xiàn)，同樣也滿足表頭表尾指針相等，那么又如何解決這個問題呢？（我們給出三種可行的解決方案）

• A：設(shè)置一個標(biāo)志變量flag，當(dāng)front = rear的時，且flag = 0的時候為空，若flag = 1 的時候為隊列滿
• B：設(shè)計一個計數(shù)器count統(tǒng)計當(dāng)前隊列中的元素數(shù)量，count == 0 隊列空，count == maxsSize 隊列滿
• C：保留一個存儲空間用于區(qū)分是否隊列已滿，也就是說，當(dāng)一個還空閑一個單元時候，我們就認(rèn)為表已經(jīng)滿了

我們重點(diǎn)講解 C 中的方法

我們根據(jù)這種方法可以總結(jié)出幾個條件的運(yùn)算式

• 隊列為滿的條件：(rear+1) % MaxSize == front

• 隊列為空的條件：front == rear

• 隊列中元素的個數(shù)：(rear- front + maxSize) % MaxSize

• 入隊：rear = (rear + 1) % maxSize

• 出隊：front = (front + 1) % maxSize

(一) 順序隊列的類型定義

#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_
#include "Queue.h"

template <class T>
class seqQueue:public Queue<T> {
private:
    //指向存放元素的數(shù)組 
    T &data;
    //隊列的大小 
    int maxSize;
    //定義隊頭和隊尾指針 
    int front, rear;
    //擴(kuò)大隊列空間 
    void resize();
public: 
    seqQueue(int initSize = 100);
    ~seqQueue() {delete []data;}
    //清空隊列 
    void clear() {front = rear = -1;}
    //判空
    bool empty() const {return front == rear;} 
    //判滿
    bool full() const {return (rear + 1) % maxSize == front;}
    //隊列長度
    int size() const {(rear- front + maxSize) % maxSize;}
    //入隊
    void enQueue(const T &x);
    //出隊 
    T deQueue();
    //取隊首元素
    T getHead() const; 
}; 

#endif 

(二) 初始化一個空隊列

template <class T>
seqQueue<T>::seqQueue(int initSize) {
    if (initSize <= 0) throw badSize();
    data = new T[initSize];
    maxSize = initSize;
    front = rear = -1; 
}

(三) 入隊

template <class T>
void seqQueue<T>::enQueue(const T &x) {
    //隊滿則擴(kuò)容 
    if ((rear + 1) % maxSize == front) resize();
    //移動隊尾指針 
    rear = (rear + 1) % maxSize;
    //x 入隊 
    data[rear] = x;
}

(四) 出隊

template <class T>
T seqQueue<T>::deQueue() {
    //隊列為空則拋出異常 
    if (empty()) throw outOfRange();
    //移動隊尾指針 
    front = (front + 1) % maxSize;
    //x入隊 
    return data[front];
}

(五) 取隊首元素

template <class T>
T seqQueue<T>::getHead() const {
    if (empty()) throw outOfRange();
    //返回隊首元素，不移動隊首指針 
    return data[(front + 1) % maxSize];
}

(六) 擴(kuò)大隊列空間

template <class T>
void seqQueue<T>::resize() {
    T *p = data;
    data = new T[2 *maxSize];
    for(int i = 1; i < size(); ++i)
        //復(fù)制元素 
        data[i] = p[(front + i) % maxSize];
    //設(shè)置隊首和隊尾指針 
    front = 0; rear = size();
    maxSize *= 2;
    delete p;
}

鏈隊列

用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示隊列我們叫做鏈隊列，用無頭結(jié)點(diǎn)的單鏈表表示隊列，表頭為隊頭，表尾為隊尾，需要兩個指針分別指向隊頭元素和隊尾元素，這種存儲結(jié)構(gòu)的好處之一就是不會出現(xiàn)隊列滿的情況

image

(一) 順序隊列的類型定義

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
#include <iostream>
#include "Queue.h"

template <class T>
class linkQueue:public Queue<T> {
private:
    struct node {
        T data;
        node *next;
        node (const T &x, node *N = NULL) {
            data = x;
            next = N;
        }
        node ():next(NULL){}
        ~node () {} 
    };
    node *front, *rear;
public: 
    linkQueue(){front = rear = NULL;};
    ~linkQueue() {clear();}
    //清空隊列 
    void clear();
    //判空
    bool empty() const {return front == NULL;} 
    //隊列長度
    int size() const;
    //入隊
    void enQueue(const T &x);
    //出隊 
    T deQueue();
    //取隊首元素
    T getHead() const; 
};

#endif 

(二) 清空隊列

template <class T>
void linkQueue<T>::clear() {
    node *p;
    //釋放隊列中所有節(jié)點(diǎn) 
    while(front != NULL) {
        p = front;
        front = front -> next;
        delete p;
    }
    //修改尾指針 
    rear = NULL;
} 

(三) 求隊列長度

template <class T>
int linkQueue<T>::size() const {
    node *p = front;
    int count = 0;
    while(p) {
        count++;
        p = p -> next;
    } 
    return count;
}

(四) 入隊

template <class T>
void linkQueue<T>::enQueue(const T &x) {
    if(rear == NULL) 
        front = rear = new node(x);
    else {
        rear -> next = new node(x);
        rear = rear -> next;
    }
}

(五) 出隊

template <class T>
T linkQueue<T>::deQueue() {
    //隊列為空則拋出異常 
    if (empty()) throw outOfRange();
    node *p = front;
    //保存隊首元素 
    T value = front -> data;
    front = front -> next;
    if (front == NULL)
        rear = NULL;
    delete p;
    return value;
}

(六) 取隊首元素

template <class T>
T linkQueue<T>::getHead() const {
    if (empty()) throw outOfRange();
    return front -> data; 
}

結(jié)尾：

如果文章中有什么不足，或者錯誤的地方，歡迎大家留言分享想法，感謝朋友們的支持！

如果能幫到你的話，那就來關(guān)注我吧！如果您更喜歡微信文章的閱讀方式，可以關(guān)注我的公眾號

在這里的我們素不相識，卻都在為了自己的夢而努力 ?

一個堅持推送原創(chuàng)開發(fā)技術(shù)文章的公眾號：理想二旬不止

image