第4篇 C++ 数据结构--队列的实现

和ArrayList/Stack/LinkList一样，队列是一种线性结构，遵循特定的执行顺序。顺序为先进先出（FIFO）。队列的一个很好的例子是资源的任何使用者队列，其中首先服务于队列中的第一个元素。

Queue和ArrayList之间的区别在于删除。 ArrayList可以任意在任何位置插入或删除元素，而在队列Queue中，只能在队列头部执行删除操作，也就是退队操作(deque)，并且只能在末尾添加元素，也就是入队操作(enque)。因此我们这里列出队列的主要操作

enque:在队列末端插入元素
deque:在队列首端移除元素
rear:返回队列末端的元素
front:返回队列首端的元素
is_full:队列是否满载
is_empty:队列是否空载

这是一个非常形象的例子

队列的使用场合

Queue的此属性使其在以下情况下也很有用。

当不必立即处理的任务但必须以广度优先搜索之类的先进先出顺序处理事物时，使用队列。
一个繁重的任务，需要分割成多个子任务，多个子任务可以放到队列中，让线程通过Queue的deque操作获取任务委派。
在多个线程/进程之间共享资源或者异步传输数据时，示例包括IO缓冲区，管道，文件IO等。

接口设计

类接口我们已经定义好了，并且列出了主要队列可能经常用到函数接口,类接口就是一个代码细节实现的“纲领”。

#ifndef __QUEUE_HH__
#define __QUEUE_HH__
#include "./LinkedList.hh"

template <class T>
class Queue : protected LinkedList<T>
{
private:
    //内部元素队列指针
    size_t d_maxsize;

public:
    //默认构造函数
    Queue();

    //自定义构造函数
    Queue(size_t);

    //析构函数
    ~Queue();

    //拷贝构造函数
    Queue(const Queue &);

    //移动构造函数
    Queue(Queue &&);

    //踢队操作
    T deque();

    //入队操作
    void enque(const T &);

    //设置最大个数
    void set_maxsize(size_t);

    //获取最大个数
    size_t maxsize() const;

    //查看队列首端元素
    T front() const;

    //返回队列的头指针
    Node<T> *head();

    //查看队列末端元素
    T rear() const;

    //队列是否非空
    bool is_empty() const;

    //队列是否已满
    bool is_full() const;

    //返回队列已有数量
    size_t size() const;

    //打印链表
    template <class R>
    friend std::ostream &operator<<(std::ostream &, Queue<R> &);
};
#endif

代码实现的问题

我们知道队列的实质是一个“线性表”，那么它可以由动态数组(ArrayList)或者链表(LinkList)，并且在插入/删除操作上加以修改符号队列的FIFO的行为特征，我们从之前Stack实现的文章中，已经知道LinkList类实现是非常高效的,同理我们Queue类实现只需继承我们LinkList类即可。

#include "../headers/Queue.hh"
#include "./LinkedList.cpp"
#include <iostream>

//默认构造函数
template <class T>
Queue<T>::Queue() : d_maxsize(15)
{
    LinkedList<T>::d_head = nullptr;
    LinkedList<T>::d_size = 0;
    LinkedList<T>::d_last = nullptr;
}

//自定义构造函数
template <class T>
Queue<T>::Queue(size_t n) : d_maxsize(15)
{
    LinkedList<T>::d_head = nullptr;
    LinkedList<T>::d_last = nullptr;
    LinkedList<T>::d_size = 0;
}

//析构函数
template <class T>
Queue<T>::~Queue()
{
    LinkedList<T>::clear();
}

//踢队操作
template <class T>
T Queue<T>::deque()
{
    if (LinkedList<T>::d_size)
    {
        return LinkedList<T>::pop_front();
    }
}

//入队操作
template <class T>
void Queue<T>::enque(const T &val)
{
    if (LinkedList<T>::d_size <= d_maxsize)
    {
        LinkedList<T>::push_back(val);
    }
}

//查看队列首端元素
template <class T>
T Queue<T>::front() const
{
    if (LinkedList<T>::d_size)
    {
        return LinkedList<T>::front();
    }
}

template <class T>
void Queue<T>::set_maxsize(size_t val)
{
    if (val > 0)
    {
        d_maxsize = val;
    }
}

//返回头节点
template <class T>
Node<T> *Queue<T>::head()
{
    if (LinkedList<T>::d_head)
    {
        return LinkedList<T>::d_head;
    }
}

//查看队列末端元素
template <class T>
T Queue<T>::rear() const
{
    if (LinkedList<T>::d_size)
    {
        return LinkedList<T>::last();
    }
}

//队列是否非空
template <class T>
bool Queue<T>::is_empty() const
{
    if (LinkedList<T>::d_size == 0 || LinkedList<T>::d_head == nullptr)
    {
        return true;
    }
    return false;
}

//队列是否已满
template <class T>
bool Queue<T>::is_full() const
{
    if (LinkedList<T>::d_size >= d_maxsize)
    {
        return true;
    }
    return false;
}

//返回队列已有数量
template <class T>
size_t Queue<T>::size() const
{
    return LinkedList<T>::d_size;
}

template <class T>
size_t Queue<T>::maxsize() const
{
    return d_maxsize;
}

template <class R>
std::ostream &operator<<(std::ostream &os, Queue<R> &q)
{
    Node<R> *nod = q.head();
    while (nod != nullptr)
    {
        os << nod->elem() << ",";
        nod = nod->next();
    }
    os << std::endl;
    return os;
}

请读者在实现数据结构甚至是算法时，优先以性能开销为考量标准，其次是空间开销.如果能同时做到性能和空间开销最低，当然最好！但经验告诉我，那是美好的遐想。因此请一切优先考虑性能吧。那么，请看如下

ss18.png

第4篇 C++ 数据结构--队列的实现