数据结构图文解析之：队列详解与C++模板实现

2022-09-25 16:07:05

0. 数据结构图文解析系列

数据结构系列文章
数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现
数据结构图文解析之：栈的简介及C++模板实现
数据结构图文解析之：队列详解与C++模板实现
数据结构图文解析之：树的简介及二叉排序树C++模板实现.
数据结构图文解析之：AVL树详解及C++模板实现
数据结构图文解析之：二叉堆详解及C++模板实现
数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现

1. 队列简介

1.1 队列的特点

队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：

队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。
在队尾添加元素，在队头添加元素。

1.2 队列的相关概念

队列的相关概念：

队头与队尾：允许元素插入的一端称为队尾，允许元素删除的一端称为队头。
入队：队列的插入操作。
出队：队列的删除操作。

例如我们有一个存储整型元素的队列，我们依次入队：{1，2，3}

添加元素时，元素只能从队尾一端进入队列，也即是2只能跟在1后面，3只能跟在2后面。

如果队列中的元素要出队：

元素只能从队首出队列，出队列的顺序为：1、2、3，与入队时的顺序一致，这就是所谓的“先进先出”。

1.3 队列的操作

队列通常提供的操作：

入队：通常命名为push()
出队：通常命名为pop()
求队列中元素个数
判断队列是否为空
获取队首元素

1.4 队列的存储结构

队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构。

本文中，我们以数组、链表为底层数据结构构建队列。

2.基于数组的循环队列实现

以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作：

可能有人说，把队首标志往后移动不就不用移动元素了吗？的确，但那样会造成数组空间的“流失”。

我们希望队列的插入与删除操作都是O(1)的时间复杂度，同时不会造成数组空间的浪费，我们应该使用循环队列。

所谓的循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

那么我们如何判断队列是空队列还是已满呢？

栈空：队首标志=队尾标志时，表示栈空，即红绿两个标志在图中重叠时为栈空。
栈满 : 队尾+1 = 队首时，表示栈空。图三最下面的队列即为一个满队列。尽管还有一个空位，我们不存储元素。

2.1 循环队列的抽象数据类型

template <typename T>

class LoopQueue

{

public:

    LoopQueue(int c = 10);

    ~LoopQueue();

public:

    bool isEmpty();        //队列的判空

    int size();            //队列的大小

    bool push(T t);        //入队列

    bool pop();            //出队列

    T front();            //队首元素

private:

    int capacity;

    int begin;

    int end;

    T*  queue;

};

begin：队首标志
end：队尾标志
capacity：数组容量
queue：数组

2.2 队列的具体实现

队列的操作非常简单，这里不再多说

template<typename T>

LoopQueue<T>::LoopQueue(int c = 10)

: capacity(c), begin(0), end(0), queue(nullptr)

{

    queue = new T[capacity];

};

template<typename T>

LoopQueue<T>::~LoopQueue()

{

    delete[]queue;

}

template <typename T>

bool LoopQueue<T>::isEmpty()

{

    if (begin == end)

        return true;

    return false;

};

template<typename T>

int LoopQueue<T>::size()

{

    return (end-begin+capacity)%capacity; //计算队列长度

};

template<typename T>

bool LoopQueue<T>::push(T t)

{

    if (end + 1 % capacity == begin) //判断队列是否已满

    {

        return false;

    }

    queue[end] = t;

    end = (end + 1) % capacity;

    return true;

};

template <typename T>

bool LoopQueue<T>::pop()

{

    if (end == begin) //判断队列是否为空

    {

        return false;

    }

    begin = (begin + 1) % capacity;

    return true;

};

template <typename T>

T LoopQueue<T>::front()

{

    if (end == begin)

    {

        return false;

    }

    return queue[begin];

};

2.3 循环队列代码测试

int main()

{

    LoopQueue<string> queue(6);

    queue.push("one");

    queue.push("two");

    queue.push("three");

    queue.push("four");

    queue.push("five");

    cout << "队列长度" << queue.size() << endl;

    while (!queue.isEmpty())

    {

        cout << queue.front() << endl;

        queue.pop();

    }

    getchar();

    return 0;

}

测试结果：

队列长度5

one

two

three

four

five

3. 链队列

链队列是基于链表实现的队列，它不存在数组的O（n）的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首，哪头做队尾。

显然我们应该以链表头部为队首，链表尾部为队尾。存储一个指向队尾的指针，方便从链表尾插入元素；使用带头节点的链表，方便从链表头删除元素。

3.1 链表节点

template<typename T>

struct Node

{

    Node(T t) :value(t), next(nullptr){}

    Node() = default;

    T value;

    Node<T> * next;

};

vaule : 链表节点的值
next : 指针，指向下一个节点

3.2 队列的抽象数据类型

链队列提供的接口与循环队列一致

template<typename T>

class LinkQueue

{

public:

    LinkQueue();

    ~LinkQueue();

    bool isEmpty();

    int size();

    bool pop();

    void push(T t);

    T front();

private:

    Node<T>* phead;

    Node<T>* pend;

    int count;

};

3.3 队列的具体实现

template<typename T>

LinkQueue<T>::LinkQueue()

    :phead(nullptr),pend(nullptr),count(0)

{

    phead = new Node<T>();

    pend = phead;

    count = 0;

};

template <typename T>

LinkQueue<T>::~LinkQueue()

{

    while (phead->next != nullptr)

    {

        Node<T> * pnode = phead;

        phead = phead->next;

    }

};

template <typename T>

bool LinkQueue<T>:: isEmpty()

{

    return count==0;

};

template <typename T>

int LinkQueue<T>::size()

{

    return count;

};

//在队尾插入

template <typename T>

void LinkQueue<T>::push(T t)

{

    Node<T>* pnode = new Node<T>(t);

    pend->next = pnode;

    pend = pnode;

    count++;

};

//在队首弹出

template <typename T>

bool LinkQueue<T>::pop()

{

    if (count == 0)

        return false;

    Node<T>* pnode = phead->next;

    phead->next = phead->next->next;

    delete pnode;

    count--;

    return true;

};

//获取队首元素

template<typename T>

T LinkQueue<T>::front()

{

    return phead->next->value;

};

3.4 队列的代码测试

int _tmain(int argc, _TCHAR* argv[])

{

    LinkQueue<string> lqueue;

    lqueue.push("one");

    lqueue.push("two");

    lqueue.push("three");

    lqueue.push("four");

    lqueue.push("five");

    cout << "队列的大小" << lqueue.size() << endl;

    while (!lqueue.isEmpty())

    {

        cout << lqueue.front() << endl;

        lqueue.pop();

    }

    getchar();

    return 0;

}

运行结果：

队列的大小5

one

two

three

four

five

4. 队列的完整代码

循环队列：https://github.com/huanzheWu/Data-Structure/blob/master/LoopQueue/LoopQueue/LoopQueue.h

链队列：https://github.com/huanzheWu/Data-Structure/blob/master/LinkQueue/LinkQueue/LinkQueue.h

原创文章，转载请注明出处：http://www.cnblogs.com/QG-whz/p/5171123.html#_label3_0

码农公寓