DSA_06：隊列

隊列，同棧一樣是一個非常基礎、常用的數據結構。

隊列的基本操作：後進先出。

隊列有以下類型：

　　1. 順序隊列

　　2. 鏈式隊列

　　3. 迴圈隊列：隊滿條件：(tail + 1) % n == head，隊空條件：head == tail，tail 位置不存儲數據

　　4. 阻塞隊列

　　5. 併發隊列

　　6. 優先隊列

迴圈隊列是是順序隊列，為了優化順序隊列，極好避免空間浪費，僅 tail 位置不存放數據。

阻塞隊列和併發隊列這裡不進行講解。

常用的隊列是鏈式隊列。

優先隊列是基於二叉堆實現的，一種順序結構，這在後續會詳細講解。

顯然，隊列會比棧更加複雜一些，但是相比更高級的數據結構而言，自然簡單許多。

為了滿足後進先出規則，相比於棧只需要一個 top 指針而言，隊列需要兩個指針：隊頭指針 head，隊尾指針 tail。

同樣，本文模擬一個 C++ STL queue。介面及註釋已經寫於源碼。

註：為了區別棧的介面，源碼中將 push、pop 介面替換為 enQueue、deQueue。

隊列基礎插入模型：

源碼：

#include <iostream>
#include <iomanip>


/* 鏈式隊列 */
template<typename _Ty>
class Queue
{
    // 定義節點結構
    struct Node
    {
        _Ty data;
        Node* next = nullptr;
        explicit Node(const _Ty& _data) :data(_data) {}
    };

public:
    Queue() = default;
    ~Queue();

    // 隊列是否為空
    bool empty() const { return n_size == 0; }    // or return head/tail == nullptr

    // 返回隊列長度
    size_t size() const { return n_size; }

    // 返回隊頭數據引用
    _Ty& front() const;
    // 返回隊尾數據引用
    _Ty& back() const;

    // 壓隊列
    void enQueue(const _Ty& _data);
    // 出隊列
    void deQueue();

private:
    Node* head = nullptr;
    Node* tail = nullptr;
    size_t n_size = 0;
};
template<typename _Ty>
Queue<_Ty>::~Queue()
{
    Node* temp = head;
    while (temp != nullptr)
    {
        head = head->next;
        delete temp;
        temp = head;
    }
    tail = nullptr;
    n_size = 0;
}
template<typename _Ty>
_Ty& Queue<_Ty>::front() const
{
    if (head == nullptr) throw std::exception("Queue is empty.");
    else return head->data;
}
template<typename _Ty>
_Ty& Queue<_Ty>::back() const
{
    if (tail == nullptr) throw std::exception("Queue is empty.");
    else return tail->data;
}
template<typename _Ty>
void Queue<_Ty>::enQueue(const _Ty& _data)
{
    Node* temp = new Node(_data);
    if (tail == nullptr)
    {
        head = tail = temp;
    }
    else
    {
        tail->next = temp;
        tail = temp;
    }
    temp = nullptr;
    ++n_size;
}
template<typename _Ty>
void Queue<_Ty>::deQueue()
{
    if (head == nullptr) return;
    Node* temp = head;
    head = head->next;
    delete temp;
    --n_size;
}


int main()
{
    std::cout.setf(std::ios_base::boolalpha);

    Queue<int> qu;

    std::cout << "Empty?: " << qu.empty() << std::endl;

    std::cout << "Push datas..." << std::endl;
    for (int i = 0; i < 5; ++i) qu.enQueue(i + 1);

    std::cout << "Now empty?: " << qu.empty() << std::endl;
    std::cout << "Now size: " << qu.size() << std::endl;
    std::cout << "Now front: " << qu.front() << std::endl;
    std::cout << "Now back: " << qu.back() << std::endl;

    std::cout << "deQueue..." << std::endl;
    qu.deQueue();

    std::cout << "Now empty?: " << qu.empty() << std::endl;
    std::cout << "Now size: " << qu.size() << std::endl;
    std::cout << "Now front: " << qu.front() << std::endl;
    std::cout << "Now back: " << qu.back() << std::endl;

    return 0;
}