【C++】stack 和 queue

stack的使用

stack相关文档

• 栈的经典特性就是 LIFO，即后进先出，元素只能从栈顶入栈，然后从栈顶出栈

• 只能通过top接口，访问栈顶元素，不支持随机访问，也不支持迭代器
• 遍历栈中的元素，只能通过 top、pop、empty 配合使用，一边访问栈顶，一边出栈

queue的使用

queue相关文档

• 队列的特点是 FIFO，即先进先出，元素从队列一端入队列，从另一端出队列
• 元素入队列的一端是队尾，出队列的一端是队头
• 可以通过 front 访问队头元素，通过 back 访问队尾元素
• 遍历队列元素和栈类似，也是通过 front、pop、empty 配合使用，边访问，边出队列

适配器模式

stack 和 queue 都是一种容器适配器，什么是适配器呢？

我们平时给手机充电用的叫电源适配器，它的作用就是将来自电源插座交流电转换为设备所需的直流电

而容器适配器的作用也是转换，将一种容器转换为我们需要的容器，例如：

• 将 vector 转换为 stack
• 将 list 转换为 queue

容器适配器的本质是一种复用：利用已经实现的容器来实现另一种容器

如何实现容器适配器：将已经实现的容器作为模板参数，通过封装，转换为我们需要的容器

上图的 Container，如果我们在实例化stack时，给的模板参数是 vector，就会用 vector 实现一个stack；list 同理

stack<int, vector<int>> s_vec;
stack<int, list<int>> s_lt;

stack模拟实现

模板参数

和官方库一样，我们这里的模板参数有两个：

• class T：存储的数据的类型
• class Container：用来实现stack的底层容器。官方库给了一个缺省值 deque，这里我们先用 vector 作为缺省值，vector的尾插尾删效率还是不错的

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

成员变量

stack的成员变量只有一个：Container _con，用来实现stack的底层容器

成员函数

因为stack的成员变量是自定义类型，所以构造函数、析构函数等默认成员函数不需要我们手动实现，它们由底层容器提供

stack其他接口的实现：在函数中调用 _con 的接口即可。例如 empty，在函数中调用 _con 的empty

bool empty()
{
        return _con.empty();
}

其他接口的实现同理，这里不再详细说了

代码

以下代码存放于头文件Stack.h中，使用时要在测试文件中展开std

// Stack.h
#pragma once
#include <vector>

namespace ns1
{
        template <class T, class Container = vector<T> >
        class Stack
        {
        public:
                bool empty()
                {
                        return _con.empty();
                }

                size_t size()
                {
                        return _con.size();
                }

                const T& top()
                {
                        return _con.back();
                }

                void push(const T& val)
                {
                        _con.push_back(val);
                }

                void pop()
                {
                        _con.pop_back();
                }
        private:
                Container _con;
        };
}

测试：

还可以用 list 实现stack：

queue模拟实现

模板参数

queue的底层容器的缺省值同样使用的是 deque，这里我们暂且用list

queue的底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

queue不适合用 vector 作为底层容器：queue需要头删数据，而 vector 的头删效率很差，而且并没有提供头删接口

其他的和stack一样，这里不再细说，直接上代码

代码

// Queue.h
#pragma once
#include <list>

namespace ns1
{
        template <class T, class Container = list<T>>
        class Queue
        {
        public:
                bool empty()
                {
                        return _con.empty();
                }

                size_t size()
                {
                        return _con.size();
                }

                const T& front()
                {
                        return _con.front();
                }

                const T& back()
                {
                        return _con.back();
                }

                void push(const T& val)
                {
                        _con.push_back(val);
                }

                void pop()
                {
                        _con.pop_front();
                }
        private:
                Container _con;
        };
}

测试：

双端队列 deque

deque相关文档

介绍

stack和queue的底层容器默认都是 deque，那么deque到底是个什么东西呢？

deque 被称为双端队列，是一种双开口的“连续”空间的数据结构，支持在空间的头部和尾部进行插入删除操作，且效率很高

• 与 vector 相比，deque的头插不用挪动数据，效率很高
• 与 list 相比，deque 一次申请一大块空间，不需要频繁申请空间，deque的空间利用率高

deque的结构

实际上，deque的空间并不是真正连续的，而是由一段一段的小空间组成的，每一段小空间叫做 buffer（缓冲区），并由一个中控数组记录每一个 buffer 的地址，中控数组从中间开始使用

如果是头插，就新申请一块空间，存入数据，并将新开空间的地址头插到中控数组；尾插同理

中控数组满了就扩容，反正里面存的都是指针，扩容的消耗并不大

迭代器

既然deque的底层空间并不是连续的，那它是怎么维护表面上是连续空间和随机访问的呢？——由迭代器来实现

deque的迭代器较为复杂，有四个部分

• cur：记录当前指向的数据位置
• first：记录当前buffer的起始位置
• last：记录当前buffer的终止位置
• node：指向当前buffer在中控数组的位置

像这样的迭代器，deque有两个：start和finish

• start 指向第一个 buffer
• finish 指向最后一个 buffer

遍历操作：

• 当一个迭代器的cur一直向后遍历，直到遇到了last，就说明当前 buffer 遍历完毕
• 然后通过 node 返回中控数组中，得到下一个 buffer 的地址，继续遍历
• 重复上述操作，直到 cur 遇到了finish迭代器的last，说明整个deque已经遍历完毕

deque的缺陷

1. 虽然 deque 的头尾插入删除效率都很不错，但是如果涉及到中间位置的插入删除，效率就不行了，和 vector 一样
2. 遍历的效率不够极致，比不过 vector。因为 deque 的迭代器遍历时需要频繁检测是否到了当前buffer的边界，导致遍历效率较低

我们使用的容器，大部分情况虽然不太会在中间位置修改数据，但是大概率都会有遍历的需求，而 deque 的遍历效率较低，所以 deque 的应用不多

为什么使用 deque 实现 stack 和 queue

1. stack 和 queue 没有遍历需求，只需在空间的头尾进行操作
2. 对于 stack，只需要尾插尾删，deque 扩容时不需要拷贝数据，效率比 vector 高；对于 queue，deque 的头删尾插不仅效率高，而且空间利用率优于 list

优先级队列 priority_queue

priority_queue相关文档

介绍

• 虽说叫优先级队列，但是优先级队列的底层是一个堆，默认是一个大堆
• 在优先级队列中，可以随时插入元素，并且自动调整堆
• 只能检索最大元素，即优先级队列中位于顶部的元素
• 优先级队列也是一个容器适配器，它的底层容器需要支持随机访问
• 优先级队列默认使用 vector 作为底层结构，在此基础上使用堆的调整算法，将 vector 中的元素调整为堆

使用

如何遍历优先级队列：构造一个空的优先级队列，插入乱序元素，依次取出并删除堆顶元素，直到优先级队列为空

模拟实现

模板参数

优先级队列的模板参数有三个

• T：存储的元素的数据类型
• Container：用于存储元素的底层容器，这里默认用vector
• Compare：用于定义元素之间的比较规则，涉及到仿函数，这里先放着，后面讲

优先级队列的底层容器是一个 vector，想要维护一个堆，就需要堆的调整算法。关于如何实现一个堆，这里不是重点，就不详细说了

成员变量

与 stack 和 queue 相同，优先级队列也是容器适配器，成员变量只有一个 Container _con

push

• 在 vector 尾部插入数据后，就需要从当前插入位置向上调整，维护堆的结构

pop

删除堆顶元素，为了维护堆的结构，不可以直接删除

• 需要将堆顶元素与尾部元素交换，然后尾删
• 此时需要从堆顶向下调整

代码

// 优先级队列 大堆
template <class T, class Container = vector<T>>
class Priority_queue
{
public:
        // 向上调整
        void ajust_up(int child)
        {
                int parent = (child - 1) / 2; // 确定父节点
                while (child > 0)
                {
                        if (_con[parent] < _con[child])
                        {
                                // 父节点比子节点小，交换
                                swap(_con[parent], _con[child]);
                                // 更新父子
                                child = parent;
                                parent = (child - 1) / 2;
                        }
                        else
                                break;
                }
        }

        void push(const T& val)
        {
                _con.push_back(val);
                ajust_up(_con.size() - 1); // 从插入元素开始向上调整
        }
        // 向下调整
        void ajust_down(int parent)
        {
                int child = parent * 2 + 1; // 先假定只有左孩子

                while (child < _con.size())
                {
                        if (child + 1 < _con.size() && _con[child] < _con[child + 1])
                                child++; // 右孩子存在，且右孩子比左孩子大，更新孩子节点为右孩子

                        if (_con[parent] < _con[child])
                        {
                                // 父节点比子节点小，交换
                                swap(_con[parent], _con[child]);
                                // 更新父子
                                parent = child;
                                child = parent * 2 + 1;
                        }
                }
        }

        void pop()
        {
                swap(_con[0], _con[_con.size() - 1]);
                _con.pop_back();
                ajust_down(0); // 从堆顶开始向下调整
        }

        bool empty()
        {
                return _con.empty();
        }

        size_t size()
        {
                return _con.size();
        }

        const T& top()
        {
                return _con[0];
        }

private:
        Container _con;
};

测试：

仿函数

是什么

仿函数不是函数，而是一个类。仿函数重载了函数调用运算符operator()，使得类对象可以像函数一样使用

例如，现在有一个 Add 类

class Add
{
public:
        int operator()(const int& a, const int& b)
        {
                return a + b;
        }
};

我们可以这样使用

Add a;
int sum = a(1, 1);
cout << sum << endl;

甚至可以这样：构造一个 Add 匿名对象，然后调用匿名对象的 operator()

int sum = Add()(1, 1);
cout << sum << endl;

应用

仿函数的功能和C语言中的函数指针类似

• 函数指针可以作为参数传给其他函数，例如 qsort，就需要传一个比较大小的函数
• 仿函数也可以做到相同的功能，而且仿函数还可以作为模板参数，也就是我们上面见到的优先级队列的模板参数

通过控制比较大小的逻辑，我们可以控制优先级队列的底层是什么堆

• Compare 的缺省值为 less，所以默认为大堆
• 如果想构建小堆，就要显式传递模板参数 Compare 为 greater<T>。注意：如果显式传递比较逻辑，也一定要显式传递底层容器 Container，因为参数不能跳跃着传递

如下，构建一个小堆

完善优先级队列

我们上面实现的优先级队列是写死的，只是一个大堆，可以利用仿函数完善一下

首先需要写两个比较大小的仿函数

template <class T>
class less
{
public:
        bool operator()(const T& a, const T& b)
        {
                return a < b;
        }
};

template <class T>
class greater
{
public:
        bool operator()(const T& a, const T& b)
        {
                return a > b;
        }
};

然后给优先级队列的模板参数列表加一个比较大小的Compare，默认是 less，也就是大堆

template <class T, class Container = vector<T>, class Compare = less<T>>
class Priority_queue
{
    // ...
};

最后把优先级队列中的比较大小运算符改为仿函数

// 向上调整
void ajust_up(int child)
{
        int parent = (child - 1) / 2; // 确定父节点
        while (child > 0)
        {
                //if (_con[parent] < _con[child])
                if (Compare()(_con[parent], _con[child]))
                {
                        // 父节点比子节点小/大，交换
                        swap(_con[parent], _con[child]);
                        // 更新父子
                        child = parent;
                        parent = (child - 1) / 2;
                }
                else
                        break;
        }
}
// 向下调整
void ajust_down(int parent)
{
        int child = parent * 2 + 1; // 先假定只有左孩子

        while (child < _con.size())
        {
                //if (child + 1 < _con.size() && _con[child] < _con[child + 1])
                if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))
                        child++; // 右孩子存在，且右孩子比左孩子大/小，更新孩子节点为右孩子

                //if (_con[parent] < _con[child])
                if (Compare()(_con[parent], _con[child]))
                {
                        // 父节点比子节点小/大，交换
                        swap(_con[parent], _con[child]);
                        // 更新父子
                        parent = child;
                        child = parent * 2 + 1;
                }
        }
}

测试：

通过适配器模式实现反向迭代器

之前我们在模拟实现 【vector-链接】和【list-链接】时只实现了正向迭代器，并没有实现反向迭代器，那么我们需要重新写一个反向迭代器吗？

通过适配器模式，我们可以复用正向迭代器，实现一个反向迭代器，就像用 vector 实现 stack 一样。

模板参数

同样是使用类模板来实现，模板参数如下：

• Iterator，无论传递什么容器的迭代器，利用适配器都可以构造相应容器的反向迭代器
• Ref，引用类型，可以用来实现迭代器的 const 与 非const 本
• Ptr，指针类型，作用同上

成员变量

反向迭代器其实就是封装的正向迭代器，只有一个成员变量：Iterator _it

行为

以 list 为例：

• 反向迭代器与正向迭代器的行为是相反的：反向迭代器的 ++ 就是正向迭代器的 --；反之亦然
• rbegin() 就是 end()；rend() 就是 begin()

• 根据以上特性，反向迭代器解引用时，应该解引用下一个位置，而不是当前位置。看图就很清晰了

代码

根据反向迭代器的行为，就可以确定代码如何写了

// ReverseIterator.h
#pragma once

namespace ns1
{
        template <class Iterator, class Ref, class Ptr>
        struct ReverseIterator
        {
                typedef ReverseIterator<Iterator, Ref, Ptr> self;
                Iterator _it;

                // 构造
                ReverseIterator(Iterator it)
                        :_it(it)
                {}

                Ref operator*()
                {
                        // 解引用下一个位置
                        Iterator tmp = _it;
                        return *(--tmp);
                }

                Ptr operator->()
                {
                        return &(operator*());
                }

                self& operator++()
                {
                        --_it;
                        return *this;
                }
                
                self& operator--()
                {
                        ++_it;
                        return *this;
                }

                bool operator!=(const self& rit)
                {
                        return _it != rit._it;
                }
        };
}

在 list 的代码中添加反向迭代器：

#include "ReverseIterator.h"

template <class T>
class list
{
        typedef ListNode<T> Node;
public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
        
        reverse_iterator rbegin()
        {
            return end();
        }

        reverse_iterator rend()
        {
                return begin();
        }
        // ...
};

测试：

list 完整代码

// list.h
#include "ReverseIterator.h"

namespace ns1
{
        template <class T>
        struct ListNode
        {
                ListNode(const T& val = T())
                        :_next(nullptr)
                        ,_prev(nullptr)
                        ,_data(val)
                {}
                ListNode* _next;
                ListNode* _prev;
                T _data;
        };

        template <class T, class Ref, class Ptr>
        struct ListIterator
        {
                typedef ListNode<T> Node;

                ListIterator(Node* node)
                        :_node(node)
                {}

                // 引用
                Ref operator*()
                {
                        return _node->_data;
                }
                // 指针
                Ptr operator->()
                {
                        return &(_node->_data);
                }

                // ++it
                ListIterator& operator++()
                {
                        _node = _node->_next;
                        return *this;
                }
                // it++
                ListIterator operator++(int)
                {
                        ListIterator tmp(_node);
                        _node = _node->_next;
                        return tmp;
                }

                // --it
                ListIterator& operator--()
                {
                        _node = _node->_prev;
                        return *this;
                }
                // it--
                ListIterator operator--(int)
                {
                        ListIterator tmp(_node);
                        _node = _node->prev;
                        return tmp;
                }

                bool operator==(const ListIterator& it)
                {
                        return _node == it._node;
                }

                bool operator!=(const ListIterator& it)
                {
                        return _node != it._node;
                }

                Node* _node;
        };

        template <class T>
        class list
        {
                typedef ListNode<T> Node;
        public:
                typedef ListIterator<T, T&, T*> iterator;
                typedef ListIterator<T, const T&, const T*> const_iterator;
                typedef ReverseIterator<iterator, T&, T*> reverse_iterator;

                reverse_iterator rbegin()
                {
                        return end();
                }

                reverse_iterator rend()
                {
                        return begin();
                }

                iterator begin()
                {
                        return _head->_next;
                }
                
                iterator end()
                {
                        return _head;
                }
                // const迭代器
                const_iterator begin() const
                {
                        return _head->_next;
                }
                
                const_iterator end() const
                {
                        return _head;
                }

                // 开头节点
                void empty_init()
                {
                        _head = new Node;
                        _head->_next = _head;
                        _head->_prev = _head;
                        _size = 0;
                }
                // 构造
                list()
                {
                        empty_init();
                }
                ~list()
                {
                        clear();
                        delete _head;
                }

                // 拷贝构造
                list(const list& x)
                {
                        empty_init();
                        for (auto& e : x)
                                push_back(e);
                }

                list& operator=(list tmp) // 传值传参
                {
                        swap(tmp);
                        return *this;
                }

                size_t size() const
                {
                        return _size;
                }

                bool empty()
                {
                        return _size == 0;
                }

                iterator insert(iterator pos, const T& val)
                {
                        Node* cur = pos._node;
                        Node* prev = cur->_prev;
                        Node* newnode = new Node(val);

                        // prev newnode cur
                        prev->_next = newnode;
                        newnode->_prev = prev;
                        newnode->_next = cur;
                        cur->_prev = newnode;
                        ++_size;

                        // 返回新插入第一个元素的迭代器
                        return newnode;
                }

                iterator erase(iterator pos)
                {
                        Node* cur = pos._node;
                        Node* prev = cur->_prev;
                        Node* next = cur->_next;

                        // pre next
                        prev->_next = next;
                        next->_prev = prev;
                        delete cur;

                        --_size;
                        return next;
                }

                void push_back(const T& val)
                {
                        insert(end(), val);
                }
                void push_front(const T& val)
                {
                        insert(begin(), val);
                }
                
                void pop_back()
                {
                        erase(--end());
                }
                void pop_front()
                {
                        erase(begin());
                }

                void swap(list<T>& lt)
                {
                        std::swap(_head, lt._head);
                        std::swap(_size, lt._size);
                }

                void clear()
                {
                        iterator it = begin();
                        while (it != end())
                        {
                                it = erase(it);
                        }
                }
        private:
                Node* _head;
                size_t _size;
        };
}
    }
                void push_front(const T& val)
                {
                        insert(begin(), val);
                }
                
                void pop_back()
                {
                        erase(--end());
                }
                void pop_front()
                {
                        erase(begin());
                }

                void swap(list<T>& lt)
                {
                        std::swap(_head, lt._head);
                        std::swap(_size, lt._size);
                }

                void clear()
                {
                        iterator it = begin();
                        while (it != end())
                        {
                                it = erase(it);
                        }
                }
        private:
                Node* _head;
                size_t _size;
        };
}