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;
}