STL源码剖析（十一）序列式容器之stack、queue、priority_queue

「爱情、让人受尽委屈。」 2023-08-17 17:42 81阅读 0赞

# STL源码剖析（十一）序列式容器之stack、queue、priority\_queue #

### 文章目录 ###

*  STL源码剖析（十一）序列式容器之stack、queue、priority\_queue
 *   *  一、stack
     *   *  1.1 stack的数据结构
         *  1.2 stack的操作
     *  二、queue
     *   *  2.1 queue的数据结构
         *  2.2 queue的操作
     *  三、priority\_queue
     *   *  3.1 priority\_queue的数据结构
         *  3.2 priority\_queue的操作

STL实现了stack和queue还有priority\_queue ，stack是栈，queue是队列，priority\_queue 是优先级队列

从使用上来说，它们属于容器。从实现上来说，它们属于容器适配器，为什么这么说呢？因为stack和queue还有priority\_queue它们都是借助于其他容器实现的

## 一、stack ##

### 1.1 stack的数据结构 ###

我们知道，栈是一种先进先出的数据结构，下面看一下stack的定义

template <class T, class Sequence = deque<T> >
    class stack {
      ...
    protected:
      Sequence c;
    
      ...
    };

它内部定义了一个序列式容器，从类的模板参数来看，默认使用的是deque

stack是没有迭代器的，因为它只支持固定的顺序访问，所以不支持迭代器随机访问

### 1.2 stack的操作 ###

**入栈**

void push(const value_type& x) { c.push_back(x); }

push是将元素入栈，从实现上看，它是将数据添加到容器的尾部

**出栈**

reference top() { return c.back(); }

top访问栈顶的元素，从实现上看，它是访问容器最后一个元素

void pop() { c.pop_back(); }

pop是将栈顶数据删除，从实现上看，它是删除容器的最后一个元素

从上面看，只要支持`push_back`、`back`、`pop_back`等方法的容器，就可以作为stack的内部容器，因此我们前面学过的`vector`、`list`都行，可以使用下面方法指定

stack<int, vector<int>>
    stack<int, list<int>>

## 二、queue ##

### 2.1 queue的数据结构 ###

队列是一种先进先出的数据结构，其定义如下

template <class T, class Sequence = deque<T> >
    class queue {
      ...
    protected:
      Sequence c;
      ...
    };

它内部定义了一个序列式容器，从类的模板参数来看，默认使用的是deque

queue是没有迭代器的，因为它只支持固定的顺序访问，所以不支持迭代器随机访问

### 2.2 queue的操作 ###

**入队列**

void push(const value_type& x) { c.push_back(x); }

push是将数据入队列，从实现上，它是将数据添加到容器的尾部

**出队列**

reference front() { return c.front(); }

front是访问队列的第一个元素，从实现上，它是访问容器的第一个元素

void pop() { c.pop_front(); }

pop是删除队列首元素，从实现上，它是删除容器的第一个元素

从上面看，queue内部的容器需要实现`push_back`、`pop_front`的操作的双向开口的容器，所以`list`也可以作为queue内部容器，可以如下定义

queue<int, list<int>>

## 三、priority\_queue ##

priority\_queue是优先级队列，优先级队列是一种特殊的队列，它不是按时间顺序的先进先出，而是给每个元素一个优先级，然后按照其优先级来决定出队列的顺序

优先级队列的底部一般是使用堆实现，堆是一种基于顺序存储的完全二叉树，又分大根堆和小根堆

这里对堆的算法不详细说明，主要介绍STL中是通过什么方式实现优先级队列的

### 3.1 priority\_queue的数据结构 ###

template <class T, class Sequence = vector<T>, 
              class Compare = less<typename Sequence::value_type> >
    class  priority_queue {
      ...
    protected:
      Sequence c;
      Compare comp;      
      ...
    };

可以看到priority\_queue中定义的两个成员，一个是c，一个是comp

c是一个序列式容器，上面说过，优先级队列常基于堆实现，堆是一种基于顺序存储的完全二叉树，所以这个容器必须是顺序存储的容器（可以随机访问），从模板参数来看，默认使用的是vector

comp是比较优先级，上面说，优先级队列中的每个元素都有一个优先级，那这个优先级是怎么体现的呢？就是通过comp进行比较，comp是一个仿函数，这里默认使用的是less，其定义如下

template <class T>
    struct less : public binary_function<T, T, bool> {
        bool operator()(const T& x, const T& y) const { return x < y; }
    };

至于仿函数是什么，它是一种行为类似于函数的对象，总实现上，它通过重载operator()操作符来实现

priority\_queue只支持固定的顺序访问，所以它也没有迭代器

### 3.2 priority\_queue的操作 ###

**构造函数**

priority_queue(InputIterator first, InputIterator last) 
      : c(first, last) { make_heap(c.begin(), c.end(), comp); }

首先填充内部容器c，然后通过make\_heap算法来构造一个堆，make\_heap是STL实现的一个算法，它的作用是构建一个堆，这里不展开讨论

**入队列**

void push(const value_type& x) {
        c.push_back(x);
        push_heap(c.begin(), c.end(), comp); //上溯算法
    }

首先将元素添加到容器的尾部，然后调用push\_heap对堆进行重新排序，push\_heap是STL实现的一个算法，它的作用是将最后一个元素放置到堆中恰当的置位

**出队列**

const_reference top() const { return c.front(); }

top是访问队列首元素，从实现上，它是访问容器的第一个元素