DSA_06:队列

2020-03-29 16:03:15来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

 


原文链接:https://www.cnblogs.com/teternity/p/DSA_06.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:AtCoder Beginner Contest 160(A~D)

下一篇:非常详细的 Linux C/C++ 学习路线总结!已拿腾讯offer