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

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

数据结构系列文章

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

数据结构图文解析之:栈的简介及C++模板实现

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

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

数据结构图文解析之:AVL树详解及C++模板实现

数据结构图文解析之:二叉堆详解及C++模板实现

数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

1. 队列简介

1.1 队列的特点

队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

  1. 队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构。
  2. 在队尾添加元素,在队头添加元素。

1.2 队列的相关概念

队列的相关概念:

  1. 队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头。
  2. 入队:队列的插入操作。
  3. 出队:队列的删除操作。

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

添加元素时,元素只能从队尾一端进入队列,也即是2只能跟在1后面,3只能跟在2后面。 如果队列中的元素要出队:

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

1.3 队列的操作

队列通常提供的操作:

  1. 入队: 通常命名为push()
  2. 出队: 通常命名为pop()
  3. 求队列中元素个数
  4. 判断队列是否为空
  5. 获取队首元素

1.4 队列的存储结构

队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。 本文中,我们以数组、链表为底层数据结构构建队列。

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

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

可能有人说,把队首标志往后移动不就不用移动元素了吗?的确,但那样会造成数组空间的“流失”。 我们希望队列的插入与删除操作都是O(1)的时间复杂度,同时不会造成数组空间的浪费,我们应该使用循环队列。 所谓的循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。

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

  1. 栈空: 队首标志=队尾标志时,表示栈空,即红绿两个标志在图中重叠时为栈空。
  2. 栈满 : 队尾+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;
};
  1. begin:队首标志
  2. end:队尾标志
  3. capacity:数组容量
  4. 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;
};
  1. vaule : 链表节点的值
  2. 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 高并发综合

这篇文章是研一刚入学时写的,今天整理草稿时才被我挖出来。当时混混沌沌的面试,记下来了一些并发的面试问题,很多还没有回答。到现在也学习了不少并发的知识,回过头来看...

1573
来自专栏数据结构与算法

AGC015 D A or...or B Problem(智商题)

设A,B二进制分解后第一个不同的位为i,那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位)

1153
来自专栏李鹏的专栏

Java 虚拟机的内存结构

我们都知道虚拟机的内存划分了多个区域,并不是一张大饼。那么为什么要划分为多块区域呢,直接搞一块区域,所有用到内存的地方都往这块区域里扔不就行了,岂不痛快。

2201
来自专栏帅小子的日常

redis的基本数据类型

2797
来自专栏JAVA高级架构

Java 高并发综合

这篇文章是研一刚入学时写的,今天整理草稿时才被我挖出来。当时混混沌沌的面试,记下来了一些并发的面试问题,很多还没有回答。到现在也学习了不少并发的知识,回过头来看...

3356
来自专栏开发与安全

从汇编角度来理解linux下多层函数调用堆栈运行状态

我们用下面的C代码来研究函数调用的过程。 int bar(int c, int d) {     int e = c + d;     return e; } ...

2240
来自专栏猿人谷

腾讯2013年实习生笔试题目(附答案)

下面是我在参加2013年腾讯实习生招聘的笔试题目,当然啦,我个人不可能是完全的记住所有题目,部分是摘自网络的。同时,下面也有一些题目我不会的,希望大家一起商量解...

3378
来自专栏JavaEdge

Redis数据类型StringListsSetsHashes

Redis中最基本的类型。 Redis中的String 类型是二进制安全的,也就是说在Redis中String类型可以包含各种数据,比如一张JPEG图片或者是...

1142
来自专栏CDA数据分析师

学完Python基础知识后,你真的会python吗?

前言 最近觉得 Python 太“简单了”,于是在师父川爷面前放肆了一把:“我觉得 Python 是世界上最简单的语言!”。于是川爷嘴角闪过了一丝轻蔑的微笑(内...

32710
来自专栏腾讯Bugly的专栏

Android JNI出坑指南

笔者结合自身经验、网上资料对 JNI 的坑进行总结,如果有不正确或遗漏之处欢迎指出。

6577

扫码关注云+社区