STL之queue实现详解

悠悠 2022-05-29 03:21 206阅读 0赞

# 队列 #

承接上节栈的讲解，因为实现的list和dqueue这种双进双出的底层容器，那么对于queue这种适配器，实现起来就非常简单了。queue具有先进先出的数据结构。仅仅支持新增元素、移除元素、从最底端加入元素、取最顶端元素。这些方法而已。只要细心分析了`deque`，这个适配器就很容易了。  
![这里写图片描述][Image 1]

# STL-queue #

实现起来非常简单，那么直接给出源代码，解释其中比较重要的地方。  
队列不提供迭代器，不实现遍历操作哦。

template <class T, class Sequence = deque<T> >
    class queue {
      friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
      friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
    public:
      typedef typename Sequence::value_type value_type;
      typedef typename Sequence::size_type size_type;
      typedef typename Sequence::reference reference;
      typedef typename Sequence::const_reference const_reference;
    protected:
      Sequence c;
    public:
      bool empty() const { return c.empty(); }
      size_type size() const { return c.size(); }
      reference front() { return c.front(); }
      const_reference front() const { return c.front(); }
      reference back() { return c.back(); }
      const_reference back() const { return c.back(); }
      void push(const value_type& x) { c.push_back(x); }
      void pop() { c.pop_front(); }
    };
    
    template <class T, class Sequence>
    bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
      return x.c == y.c;
    }
    
    template <class T, class Sequence>
    bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
      return x.c < y.c;
    }

实现起来很简单，没有什么说的，明白就好。

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++ queue(STL queue)

只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。许多程序都使用了 queue 容器。queue 容器可

桃扇骨/ 2023年06月11日 03:15/ 0 赞/ 37 阅读

相关 C++基础：STL之队列queue

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

心已赠人/ 2022年12月18日 02:57/ 0 赞/ 254 阅读

相关 STL_stack/STL_queue

1、stack stack 模板类的定义在<stack>头文件中。 stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不

电玩女神/ 2022年07月17日 04:07/ 0 赞/ 192 阅读

相关 STL之vector实现详解

array、list、tree、stack、queue、hash table、set、map这些全部都是数据结构，根据数据在容器之中的排列特性，这些数据结构分为序列式和关联式两

雨点打透心脏的1/2处/ 2022年06月01日 04:43/ 0 赞/ 232 阅读

相关 STL之list实现详解

STL中的list容器底层数据结构用的是双向链表。这样数据在存储和删除的时候都可以做到时间复杂度是O(1)。但是由于其存储空间并不是连续的，所以导致在里面查找数据会很不容易。

﹏ヽ暗。殇╰゛Y/ 2022年05月30日 11:41/ 0 赞/ 313 阅读

相关 STL之priority_queue实现详解

优先队列优先队列可以从尾部插入元素，然后从头部取出优先级（通过一个数值表示）最高的对象。这种支持插入，然后每次仅仅取出一个对象数据结构，完全天然和堆一一对应，所以通过堆

分手后的思念是犯贱/ 2022年05月29日 05:21/ 0 赞/ 210 阅读

相关 STL之queue实现详解

队列承接上节栈的讲解，因为实现的list和dqueue这种双进双出的底层容器，那么对于queue这种适配器，实现起来就非常简单了。queue具有先进先出的数据结构。仅仅

悠悠/ 2022年05月29日 03:21/ 0 赞/ 207 阅读

相关 STL之stack实现详解

STL栈介绍 stack是先进先出，没有迭代器，只允许push和pop操作以及读取和修改栈顶top元素的操作。由于stack利用了底层容器实现工作，所以称之为配接器而已。

港控/mmm°/ 2022年05月29日 00:10/ 0 赞/ 194 阅读

相关 STL之deque实现详解

何为deque deque是双向开口的连续线性空间（动态将多个连续空间通过指针数组接合在一起），随时可以增加一段新的空间，所以数据想vector里面的分配，复制，释放操作

川长思鸟来/ 2022年05月29日 00:10/ 0 赞/ 216 阅读

相关 STL-queue

queue只能访问queue容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。（先进先出） 1.初始化需要头文件 queueque;

拼搏现实的明天。/ 2022年05月03日 11:58/ 0 赞/ 184 阅读