队列

作者: 王虾片 | 来源:发表于2018-12-29 10:44 被阅读0次

    概述

    顾名思义,队列其实就类似于我们现实生活中的排队。在计算机科学中,队列是一种特殊的抽象数据类型(ADT)或集合,保存在这个集合中的实体按线性的逻辑次序排列。对队列中元素的操作,仅限于在队尾和队首进行,其中包括在队尾添加元素(入队,enqueue)以及移除队首的元素(出队,dequeue),这就使队列成为一种先进先出(FIFO,First-In-First-Out)的数据结构。

    就像大家都知道的前两天刚发生的 ofo 总部排队退押金时间,也可以看作是一个队列。

    上千位用户聚集到 ofo 总部门口排队退押金

    在这里插句题外话,最近太多关于该不该向小黄车要押金的争论了,不管谁对谁错,毕竟小黄车也是曾经给我们带来过便利的,希望小黄车这次能够挺过去!

    言归正传,在先进先出的数据结构中,第一个被添加到队列中的元素也会被第一个移除,这相当于在添加新元素之后,必须在删除新元素之前删除之前添加的所有元素。队列是线性数据结构的一个例子,或者更抽象地说是顺序集合。

    队列提供计算机科学、传输和运筹学方面的服务,在这些服务中,各种实体(如数据、对象、人员或事件)被保存在队列中以供稍后处理,此时,队列实际上是作为缓冲区来使用。

    ADT 接口

    作为一种抽象数据类型,与栈类似,队列结构也有自己的操作接口。如下表所示。

    操作 功能
    size() 报告队列的规模(元素总数)
    empty() 判断队列是否为空
    enqueue(e) 将 e 插入队尾
    dequeue() 删除队首对象
    front() 引用队首对象

    实现

    队列常见的实现方式有两种,一种是基于链表的普通队列,另一种是基于数组的循环队列。

    基于链表的普通队列

    在此前的一篇文章中,我介绍了链表的实现方式,没有读过的朋友可以看看,手把手教你实现一个链表。在这一节中,我们将在这篇文章的基础上来实现队列。按照上文中描述的队列的操作接口,可实现 Queue 模板类如下:

    #pragma once
    #include "LinkedList.h"
    
    template <typename T> class Queue {
    private:
        LinkedList<T> list;
    public:
        int size() {
            return list.size();
        }
    
        bool empty() {
            return list.empty();
        }
    
        void enqueue(T const& e) { //入队,从尾部插入
            list.insertAsLast(e);
        }
    
        T dequeue() { //出队,从首部删除
            return list.remove(list.first());
        }
    
        T& front() { //队首
            return list.first()->data;
        }
    };
    
    image

    这种基于链表的实现方式比较简单,也容易理解。而且它还继承了链表的最大的优点,那就是在内存允许的情况下,可以无限地往里面添加元素,也就是进行入队操作。

    基于数组的循环队列

    大家都知道,数组是一种顺序存储结构。如果单纯地用数组模拟队列,那么随着出队入队的操作,很容易导致「假溢出」。

    系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为「假溢出」。

    但是如果在逻辑上,我们将其想象成一个环,那么除非数组空间被占满,否则可以一直往里添加元素,这样就不会造成空间的浪费,有效地避免了「假溢出」。

    循环队列出入队示意图

    下面是 C++ 代码实现:

    #pragma once
    
    #define MAX_SIZE 10 //最大容量
    template <typename T> class CircularQueue {
    private:
        int _size = 0; //队列当前规模
        int _front = 0; //队首指针
        int _rear = 0; //队尾指针
        T* _elem; //数据区
    public:
        CircularQueue() {
            _elem = new T[MAX_SIZE];
        }
    
        int size() {
            return _size;
        }
    
        bool empty() {
            /*队空或队满时,队首指针和队尾指针都会相遇,此时应该根据队列的规模 size 来判断
              若 size=0,则队空,若 size=max_size,则队满*/
            return _front == _rear && _size == 0; 
        }
    
        bool enqueue(T const& e) { //入队
            if (_size == MAX_SIZE) return false; //若队已满,则返回false
            _elem[_rear] = e;
            _rear = (_rear + 1) % MAX_SIZE;
            _size++;
            return true;
        }
    
        T dequeue() { //出队
            if (empty()) return 0;
            T e = _elem[_front];
            _front = (_front + 1) % MAX_SIZE;
            _size--;
            return e;
        }
    
        T& front() {
            return _elem[_front];
        }
    };
    

    当队首指针 _front=MAX_SIZE-1 后,再前进一个位置就自动到 0,所以在元素出队之后,我们利用了求余操作来更新队首指针。同理,更新队尾指针时也是这样。使用循环队列时,用户必须提前预知队列的最大容量,且一旦最大容量固定下来,就不可更改。

    以上就是向大家介绍的队列的全部内容了。本篇文章中的代码已上传至 GitHub,点击这里即可获得。这是 2018 年的最后一篇推送了,祝大家新年快乐!2019 年再见哦!

    欢迎关注我的微信公众号,扫描下方二维码或微信搜索:AProgrammer,就可以找到我,我会持续为你分享 IT 技术。

    相关文章

      网友评论

          本文标题:队列

          本文链接:https://www.haomeiwen.com/subject/gurulqtx.html