C++中stack和queue

前言

在 C++ 中，stack（栈）和 queue（队列）是两种常用的容器适配器，分别用于管理数据的后进先出（LIFO）和先进先出（FIFO）访问模式。本文将详细介绍这两种数据结构的基本概念、常见操作及其在 C++ 中的实现，并探讨与其相关的设计模式。

1. stack的介绍和实现

1.1 Stack 的基本概念

Stack 是一种后进先出（LIFO, Last In First Out）的数据结构。这意味着最新添加的元素最先被移除。常见的操作包括：

函数说明接口说明

stack() 构造空的栈

empty() 检测stack是否为空

size() 返回stack中元素的个数

top() 返回栈顶元素的引用

push() 将元素val压入stack中

pop() 将stack中尾部的元素弹出

1.2 Stack 的模拟实现

以下是一个基于 C++ 模板的栈实现，默认情况下使用 deque 作为底层容器。通过模板参数，用户可以指定其他支持相同操作的容器类型（如 vector）。

template <class T, class Container = deque<T>>	// 缺省值
class MyStack
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()			// 不支持 第二个参数是vectot<T>的原因是它没有pop_front(),但仍可以变向的实现
	{
		// 这样就可以支持vector了，但效率就很低了
		// _con.erase(bebin());
		_con.pop_back();
	}

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

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

	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;
};

1.3 自定义 Stack 的使用

#include "stack_queue.h"

int main()
{
	// 栈:
	cout << "STACK :" << endl;
	bit::MyStack <int, list<int >> st1;
	bit::MyStack <int, deque<int >> st2;

	st1.push(1);
	st1.push(2);
	st1.push(3);

	st2.push(4);
	st2.push(5);
	st2.push(6);

	while (!st1.empty())
	{
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl;

	while (!st2.empty())
	{
		cout << st2.top() << " ";
		st2.pop();
	}
	cout << endl;

输出：

STACK :
3 2 1
6 5 4

OJ上的使用：

最小栈

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

栈的压入、弹出序列

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        if (pushV.size() != popV.size()) return false;

        stack<int> stk;
        int popIndex = 0;

        for (int i = 0; i < pushV.size(); ++i) {
            stk.push(pushV[i]);

            while (!stk.empty() && stk.top() == popV[popIndex]) {
                stk.pop();
                ++popIndex;
            }
        }

        return stk.empty();
    }
};

逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for (size_t i = 0; i < tokens.size(); ++i) {
            string& str = tokens[i];
            // str为数字
            if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
                s.push(atoi(str.c_str()));
            } else {
                // str为操作符
                int right = s.top();
                s.pop();
                int left = s.top();
                s.pop();
                switch (str[0]) {
                case '+':
                    s.push(left + right);
                    break;
                case '-':
                    s.push(left - right);
                    break;
                case '*':
                    s.push(left * right);
                    break;
                case '/':
                    // 题目说明了不存在除数为0的情况
                    s.push(left / right);
                    break;
                }
            }
        }
        return s.top();
    }
};

用两个栈实现队列

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> A; // 栈 A，用于存储新加入的元素
    stack<int> B; // 栈 B，用于反转 A 中的元素以实现队列的 FIFO 特性

public:
    // 初始化数据结构 
    MyQueue() {}

    // 将元素 x 推到队列的末尾 
    void push(int x) {
        A.push(x); // 直接将元素压入栈 A
    }

    // 从队列前端移除元素并返回该元素 
    int pop() {
        int peek = this->peek(); // 获取队列前端的元素
        B.pop(); // 从栈 B 中移除该元素
        return peek; // 返回被移除的元素
    }

    // 获取队列前端的元素
    int peek() {
        // 如果栈 B 非空，直接返回栈 B 的栈顶元素
        if (!B.empty())
            return B.top();
        // 如果栈 A 也为空，返回 -1 表示队列为空
        if (A.empty())
            return -1;
        // 将栈 A 中的所有元素移动到栈 B 中，以反转元素顺序
        while (!A.empty()) {
            B.push(A.top());
            A.pop();
        }
        // 返回栈 B 的栈顶元素，即队列前端的元素
        return B.top();
    }

    // 返回队列是否为空
    bool empty() {
        // 如果栈 A 和栈 B 都为空，表示队列为空
        return A.empty() && B.empty();
    }
};

2. queue的介绍和实现

2.1 Queue 的基本概念

Queue 是一种先进先出（FIFO, First In First Out）的数据结构。这意味着最先添加的元素最先被移除。常见的操作包括：

函数声明接口说明

queue() 构造空的队列

empty() 检测队列是否为空，是返回true，否则返回false

size() 返回队列中有效元素的个数

front() 返回队头元素的引用

back() 返回队尾元素的引用

push() 在队尾将元素val入队列

pop() 将队头元素出队列

2.2 Queue 的模拟实现

以下是一个基于 C++ 模板的队列实现，默认情况下使用 deque 作为底层容器。通过模板参数，用户可以指定其他支持相同操作的容器类型（如 list）。

// 队列的实现：
template <class T, class Container = deque<T>>	// 缺省值
class MyQueue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

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

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

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

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

private:
	Container _con;
};

2.3 自定义 Queue 的使用

#include "stack_queue.h"

int main()
{
	// 队列:
	cout << "QUEUE :" << endl;
	bit::MyQueue <int, list<int >> q1;
	bit::MyQueue <int, deque<int >> q2;

	q1.push(1);
	q1.push(2);
	q1.push(3);

	q2.push(4);
	q2.push(5);
	q2.push(6);

	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}

	cout << endl;

	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	
	return 0;
}

输出：

QUEUE :
1 2 3
4 5 6

OJ上的使用：

用两个队列实现栈

#include <queue>
using namespace std;

class MyStack {
public:
    queue<int> queue1; // 主队列，用于存储栈中的元素
    queue<int> queue2; // 辅助队列，用于帮助元素的重新排列

    // 初始化数据结构 
    MyStack() {}

    // 将元素 x 压入栈 
    void push(int x) {
        // 将新元素压入辅助队列
        queue2.push(x);
        // 将主队列中的所有元素移到辅助队列中
        while (!queue1.empty()) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        // 交换主队列和辅助队列
        swap(queue1, queue2);
    }

    // 移除并返回栈顶元素
    int pop() {
        int r = queue1.front(); // 获取栈顶元素
        queue1.pop(); // 移除栈顶元素
        return r; // 返回栈顶元素
    }

    // 获取栈顶元素
    int top() {
        return queue1.front(); // 返回栈顶元素
    }

    // 判断栈是否为空 
    bool empty() {
        return queue1.empty(); // 返回主队列是否为空
    }
};

3. 设计模式

设计模式

常见的设计模式共有 23 种。

适配器模式 -- 封装转换

适配器模式是一种结构型设计模式，它允许接口不兼容的对象协同工作。栈和队列的实现正是通过适配器模式来封装不同的底层容器（如 deque、vector 等），提供统一的接口。

迭代器模式 -- 统一访问方式（数据结构访问都可以用）

迭代器模式是一种行为型设计模式，它提供一种方法顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示。在栈和队列的实现中，虽然没有直接使用迭代器模式，但它们的底层容器（如 deque）本身支持迭代器，这使得我们可以通过迭代器访问容器中的元素。

4. priority_queue的介绍和实现

通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

4.1 priority_queue的使用

使用 priority_queue 的关键点

默认大顶堆：priority_queue<int>，使用默认的 less<int> 比较函数，因此它是一个大顶堆。

小顶堆：priority_queue<int, vector<int>, greater<int>>，通过传递 greater<int> 作为比较函数，使其成为小顶堆。

需要指定容器类型：当指定比较函数（如 greater<int> 或 less<int>）时，也必须显式指定底层容器类型（通常是 vector<int>）。

4.1.1 C++ 标准库中

代码：

// 库中优先队列的使用
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
	// 优先队列（堆）
	/*
	priority_queue<int> q1;
	for (auto e : v)
		q1.push(e);
	*/

	// priority_queue<int> q1(v.begin(), v.end());

	int a[] = { 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int, vector<int>, greater<int>> q1(a, a + sizeof(a) / sizeof(int));//小堆

	priority_queue<int, vector<int>, less<int>> q2(a, a + sizeof(a) / sizeof(int));//大堆

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();// 删除堆顶元素
	}
	cout << endl;
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();// 删除堆顶元素
	}
	return 0;
}

输出：

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

4.1.2 自定义优先队列

PriorityQueue.h

#pragma once
#include <vector>
#include <algorithm> // for std::swap

using namespace std;

namespace bit
{
    template<class T>
    struct myless
    {
        bool operator()(const T& x, const T& y) const
        {
            return x < y;
        }
    };

    template<class T>
    struct mygreater
    {
        bool operator()(const T& x, const T& y) const
        {
            return x > y;
        }
    };

    template<class T, class Container = vector<T>, class Compare = mygreater<T>>
    class priority_queue
    {
    public:

        priority_queue() = default;

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                _con.push_back(*first);
                ++first;
            }
            // 建堆
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
            {
                adjust_down(i);
            }
        }

        void adjust_up(int child)
        {
            Compare comfunc;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (comfunc(_con[child], _con[parent]))
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }

        void adjust_down(int parent)
        {
            Compare comfunc;
            int size = _con.size();
            int child = 2 * parent + 1;
            while (child < size)
            {
                if (child + 1 < size && comfunc(_con[child + 1], _con[child]))
                {
                    child++;
                }
                if (comfunc(_con[child], _con[parent]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }

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

        void pop()
        {
            if (!_con.empty())
            {
                swap(_con.front(), _con.back());
                _con.pop_back();
                if (!_con.empty())
                {
                    adjust_down(0);
                }
            }
        }

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

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

    private:
        Container _con;
    };
}

test.cpp

#include "PriorityQueue.h"

#include <iostream>
#include <queue>

using namespace std;

class Date
{
public:
	// 默认构造函数，使用初始化列表初始化年、月、日
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year), _month(month), _day(day)
	{}

	// 重载小于运算符
	bool operator<(const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	// 重载大于运算符
	bool operator>(const Date& d) const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}

	// 重载等于运算符
	bool operator==(const Date& d) const
	{
		return _year == d._year && _month == d._month && _day == d._day;
	}

	// 重载不等于运算符
	bool operator!=(const Date& d) const
	{
		return !(*this == d);
	}

	// 输出日期
	friend std::ostream& operator<<(std::ostream& os, const Date& d)
	{
		os << d._year << "-" << d._month << "-" << d._day;
		return os;
	}

private:
	int _year;
	int _month;
	int _day;
};

// 库中的priority_queue使用
void TestPriorityQueue1()
{
	Date date1(2023, 6, 9);
	Date date2(2024, 1, 1);
	Date date3(2018, 9, 10);

	priority_queue<Date> q;// 默认大堆
	q.push(date1);
	q.push(date2);
	q.push(date3);

	while (!q.empty())
	{
		cout << q.top() << endl;
		q.pop();
	}

}

class PDateLess
{
public:
	bool operator()(Date* p1, Date* p2)
	{
		return *p1 < *p2;
	}
};

void TestPriorityQueue2()
{
	bit::priority_queue<Date*, vector<Date*>, PDateLess> q;
	q.push(new Date(2023, 6, 9));
	q.push(new Date(2024, 1, 1));
	q.push(new Date(2018, 9, 10));

	while (!q.empty())
	{
		cout << *q.top() << endl;
		q.pop();
	}

}

int main()
{
	// 大堆，需要用户在自定义类型中提供比较的重载
	// priority_queue<Date*, vector<Date*>, PDateLess> q1;

	TestPriorityQueue1();
	cout << "-----------------------" << endl;
	TestPriorityQueue2();

	return 0;
}

输出：

2024-1-1
2023-6-9
2018-9-10
-----------------------
2018-9-10
2023-6-9
2024-1-1

5. STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

6.1 deque的简单介绍

deque（双端队列）是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。与 vector 比较，deque 在头部插入时效率更高，因为不需要搬移元素；与 list 比较，deque 的空间利用率更高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

6.2 deque 的缺陷

deque 有一个致命缺陷：不适合遍历，因为在遍历时，deque 的迭代器要频繁地检测是否移动到某段小空间的边界，导致效率低下。而在序列式场景中，可能需要经常遍历。因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多。而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。

以下通过对大量数据排序来证明遍历 queue 导致的效率很低

遍历 `queue` 的性能比较

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	// vector与deque的性能对比（相同的结构，相同的访问）
	srand(time(0));
	deque<int> dq1;
	deque<int> dq2;

	int N = 1000000;

	for (int i = 0;i < N;++i)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	//拷贝到vector
	vector<int> v(dq1.begin(), dq1.end());
	sort(v.begin(), v.end());
	//拷贝回deque
	dq2.assign(v.begin(), v.end());	// 迭代区间赋值
	int end2 = clock();

	cout << "deque sort: " << end1 - begin1 << endl;
	cout << "deque copy vector sort, copy back deque: " << end2 - begin2 << endl;
	return 0;
}

输出：

deque sort: 1456
deque copy vector sort, copy back deque: 198

对于大规模数据的访问，显然 deque 效率落入下风。

总结

尽管 deque 在某些方面具有优势，但由于其遍历性能较低和内存管理复杂等缺陷，在需要频繁遍历或要求高效随机访问的场景中，vector 和 list 通常是更好的选择。因此，在实际应用中，deque 的使用相对较少，主要用于特定场景，如 stack 和 queue 的底层数据结构。

6.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器?

stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；queue 是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue 的底层容器，比如 list。

选择 deque 作为 stack 和 queue 的底层默认容器主要是由于 deque 的特性能够很好地满足这两种数据结构的需求。以下是详细的原因：

1. 只需要在固定的一端或两端进行操作

stack 和 queue 主要在固定的一端或两端进行操作：

stack：后进先出（LIFO），主要在末端进行插入和删除操作。

queue：先进先出（FIFO），在前端删除，在末端插入。

由于 deque（双端队列）支持在两端进行高效的插入和删除操作，因此非常适合用于实现 stack 和 queue。

2. 扩展效率

deque vs vector：

当 deque 扩展时，不需要像 vector 那样搬移整个数组。deque 是分段存储的，扩展时只需增加新的块，而不是搬移整个容器中的元素。

这使得 deque 在元素增长时具有更高的效率，因为 deque 避免了大量的内存复制。

3. 内存使用效率

deque vs list：

list 是链表结构，虽然在插入和删除时也很高效，但它的节点需要额外的内存来存储指针，并且每次操作都需要动态分配内存，导致内存利用率较低。

deque 是基于分段的动态数组，内存利用率更高，因为每个块的内存分配是连续的，且不需要额外的指针开销。

4. CPU 缓存命中率

连续内存块带来的优势：

deque 的每个块都是连续的内存，尽管整个 deque 是分段存储的。

这种设计相比于链表，具有更高的 CPU 缓存命中率，因为访问同一个块中的元素时，能更好地利用 CPU 缓存。

6.2 双端队列的模拟实现

1. 主类 `Deque`

这是 deque 的主类，用于实现双端队列的基本操作和管理。

template <typename T>
class Deque {
public:
    class Iterator;

    Deque();  // 构造函数
    void push_back(const T& value);  // 在尾部插入元素
    void push_front(const T& value);  // 在头部插入元素
    void pop_back();  // 删除尾部元素
    void pop_front();  // 删除头部元素
    Iterator begin() const;  // 返回双端队列的开始迭代器
    Iterator end() const;  // 返回双端队列的结束迭代器
    bool isEmpty() const;  // 判断双端队列是否为空

private:
    T** map;  // 指向块的指针数组
    size_t map_size;  // 中控数组的大小
    Iterator start;  // 开始迭代器
    Iterator finish;  // 结束迭代器

    void allocateBlock(bool atFront = false);  // 分配新的块
};

2. 迭代器类 `Iterator`

这是 deque 的迭代器类，用于实现遍历双端队列中的元素。

template <typename T>
class Iterator {
public:
    T* cur;  // 当前元素的指针
    T* first;  // 当前块的起始位置的指针
    T* last;  // 当前块的结束位置的指针
    T** node;  // 指向中控数组中当前块的指针

    Iterator();  // 默认构造函数
    Iterator(T* cur, T* first, T* last, T** node);  // 带参数的构造函数
    T& operator*() const;  // 解引用操作符
    Iterator& operator++();  // 前置自增操作符
    Iterator operator++(int);  // 后置自增操作符
    Iterator& operator--();  // 前置自减操作符
    Iterator operator--(int);  // 后置自减操作符
    bool operator==(const Iterator& other) const;  // 相等比较操作符
    bool operator!=(const Iterator& other) const;  // 不等比较操作符
};

因为 Iterator 类的操作会更新指针成员 cur、start 等，确保它们始终指向有效的内存区域，因此不会出现释放内存导致悬空指针的情况。在 Deque 类中，Iterator 对象的生命周期受到 Deque 对象的控制，在 Deque 的生命周期内，Iterator 对象的指针成员都是有效的。

3. 构造函数和常规操作

// 前向声明 Iterator 类
class Iterator;     
// 默认构造
Deque() : map(nullptr), map_size(0)     
{
    allocateBlock();
    start.node = finish.node = map;
    start.cur = finish.cur = *start.node + BLOCK_SIZE / 2;
    start.first = finish.first = *start.node;
    start.last = finish.last = *start.node + BLOCK_SIZE;
}
// 尾插
void push_back(const T& value) 
{
    if (finish.cur == finish.last)
    {
        allocateBlock();
        ++finish.node;
        finish.first = *finish.node;
        finish.last = finish.first + BLOCK_SIZE;
        finish.cur = finish.first;
    }
    *finish.cur = value;
    ++finish.cur;
}
// 头插
void push_front(const T& value) 
{
    if (start.cur == start.first) 
    {
        allocateBlock(true);
        --start.node;
        start.first = *start.node;
        start.last = start.first + BLOCK_SIZE;
        start.cur = start.last;
    }
    --start.cur;
    *start.cur = value;
}
// 尾删
void pop_back() {
    if (isEmpty()) {
        throw std::out_of_range("Deque is empty");  // 异常处理
    }
    if (finish.cur == finish.first) {
        --finish.node;
        finish.first = *finish.node;
        finish.last = finish.first + BLOCK_SIZE;
        finish.cur = finish.last;
    }
    --finish.cur;
}
// 头删
void pop_front()
{
    if (isEmpty()) 
    {
        throw std::out_of_range("Deque is empty");  // 异常处理
    }
    if (start.cur == start.last) 
    {
        ++start.node;
        start.first = *start.node;
        start.last = start.first + BLOCK_SIZE;
        start.cur = start.first;
    }
    ++start.cur;
}

Iterator begin() const 
{
    return start;
}

Iterator end() const 
{
    return finish;
}

bool isEmpty() const 
{
    return start == finish;
}

后面我们包装在主类dqeue中，便于管理

4. 内部实现和辅助函数

void allocateBlock(bool atFront = false)    // 分配新的块
{  
    T** new_map = new T * [map_size + 1];   // 中控数组的空间大小+1，存放增加的块
    for (size_t i = 0; i < map_size; ++i) 
    {
        new_map[i + (atFront ? 1 : 0)] = map[i];    // 如果 atFront 为 false，则 map 中的内容保持原位置
    }
    new_map[atFront ? 0 : map_size] = new T[BLOCK_SIZE];// 为新的块分配空间
    delete[] map;                // 释放旧的 map 内存。
    map = new_map;               // map 指向新的指针数组 new_map。
    ++map_size;
    if (atFront)                 // 如果在前端分配新的块，调整 start 和 finish 迭代器的 node 指针，确保它们指向正确的位置。
    {                            //这一步是必要的，因为在 map 前端插入新的块后，这将导致原本的所有块指针都需要向后移动一位。
        ++start.node;
        ++finish.node;
    }
}

6.3 完整代码及演示：

deque.h

#pragma once

#include <iostream>
#include <stdexcept>    // 提供了标准化的方式来报告和处理错误
#include <vector>

const size_t BLOCK_SIZE = 8;    // 块的大小

template <typename T>
class Deque {
public:
    // 前向声明 Iterator 类
    class Iterator;     
    // 默认构造
    Deque() : map(nullptr), map_size(0)     
    {
        allocateBlock();
        start.node = finish.node = map;
        start.cur = finish.cur = *start.node + BLOCK_SIZE / 2;
        start.first = finish.first = *start.node;
        start.last = finish.last = *start.node + BLOCK_SIZE;
    }
    // 尾插
    void push_back(const T& value) 
    {
        if (finish.cur == finish.last)
        {
            allocateBlock();
            ++finish.node;
            finish.first = *finish.node;
            finish.last = finish.first + BLOCK_SIZE;
            finish.cur = finish.first;
        }
        *finish.cur = value;
        ++finish.cur;
    }
    // 头插
    void push_front(const T& value) 
    {
        if (start.cur == start.first) 
        {
            allocateBlock(true);
            --start.node;
            start.first = *start.node;
            start.last = start.first + BLOCK_SIZE;
            start.cur = start.last;
        }
        --start.cur;
        *start.cur = value;
    }
    // 尾删
    void pop_back() {
        if (isEmpty()) {
            throw std::out_of_range("Deque is empty");  // 异常处理
        }
        if (finish.cur == finish.first) {
            --finish.node;
            finish.first = *finish.node;
            finish.last = finish.first + BLOCK_SIZE;
            finish.cur = finish.last;
        }
        --finish.cur;
    }
    // 头删
    void pop_front()
    {
        if (isEmpty()) 
        {
            throw std::out_of_range("Deque is empty");  // 异常处理
        }
        if (start.cur == start.last) 
        {
            ++start.node;
            start.first = *start.node;
            start.last = start.first + BLOCK_SIZE;
            start.cur = start.first;
        }
        ++start.cur;
    }

    Iterator begin() const 
    {
        return start;
    }

    Iterator end() const 
    {
        return finish;
    }

    bool isEmpty() const 
    {
        return start == finish;
    }

    class Iterator {
    public:
        T* cur;     // 当前元素的指针
        T* first;   // 当前块的起始位置的指针
        T* last;    // 当前块的结束位置的指针
        T** node;   // 指向中控数组中当前块的指针
        // 默认构造函数
        Iterator()                                      
            : cur(nullptr), first(nullptr), last(nullptr), node(nullptr) 
        {}
        // 带参数的构造函数
        Iterator(T* cur, T* first, T* last, T** node)   
            : cur(cur), first(first), last(last), node(node) 
        {}

        T& operator*() const                // 解引用操作符
        {
            return *cur;
        }

        Iterator& operator++()              // 前置自增操作符
        {
            ++cur;
            if (cur == last) 
            {
                ++node;
                first = *node;
                last = first + BLOCK_SIZE;
                cur = first;
            }
            return *this;
        }

        Iterator operator++(int)            // 后置自增操作符
        {          
            Iterator temp = *this;
            ++(*this);
            return temp;
        }


        Iterator& operator--()              // 前置自减操作符
        {   
            if (cur == first) 
            {
                --node;
                first = *node;
                last = first + BLOCK_SIZE;
                cur = last;
            }
            --cur;
            return *this;
        }

        Iterator operator--(int)            // 后置自减操作符
        {  
            Iterator temp = *this;
            --(*this);
            return temp;
        }

        bool operator==(const Iterator& other) const // 相等比较操作符
        {
            return cur == other.cur;
        }

        bool operator!=(const Iterator& other) const // 不等比较操作符
        {
            return !(*this == other);
        }
    };

private:
    T** map;  // 指向块的指针数组
    size_t map_size;  // 中控数组的大小
    Iterator start;  // 开始迭代器
    Iterator finish;  // 结束迭代器

    void allocateBlock(bool atFront = false)    // 分配新的块
    {  
        T** new_map = new T * [map_size + 1];   // 中控数组的空间大小+1，存放增加的块
        for (size_t i = 0; i < map_size; ++i) 
        {
            new_map[i + (atFront ? 1 : 0)] = map[i];    // 如果 atFront 为 false，则 map 中的内容保持原位置
        }
        new_map[atFront ? 0 : map_size] = new T[BLOCK_SIZE];// 为新的块分配空间
        delete[] map;                // 释放旧的 map 内存。
        map = new_map;               // map 指向新的指针数组 new_map。
        ++map_size;
        if (atFront)                 // 如果在前端分配新的块，调整 start 和 finish 迭代器的 node 指针，确保它们指向正确的位置。
        {                            //这一步是必要的，因为在 map 前端插入新的块后，这将导致原本的所有块指针都需要向后移动一位。
            ++start.node;
            ++finish.node;
        }
    }
};

test.cpp

#include "deque.h"

using namespace std;

int main() {
	Deque<int> dq;
	dq.push_back(1);
	dq.push_back(2);
	dq.push_back(3);
	dq.push_front(0);
	dq.push_front(-1);

	for (Deque<int>::Iterator it = dq.begin(); it != dq.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	dq.pop_back();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front();
	dq.pop_front(); //	抛异常
	

	for (Deque<int>::Iterator it = dq.begin(); it != dq.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	return 0;
}

输出

-1 0 1 2 3
1 2

以上便是对C++ 中 stack 和 queue 的底层数据结构和优先队列priority_queue的简单实现。我们下期再见

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

前言

1. stack的介绍和实现

1.1 Stack 的基本概念

1.2 Stack 的模拟实现

1.3 自定义 Stack 的使用

输出：

OJ上的使用：

2. queue的介绍和实现

2.1 Queue 的基本概念

2.2 Queue 的模拟实现

2.3 自定义 Queue 的使用

输出：

OJ上的使用：

3. 设计模式

设计模式

适配器模式 -- 封装转换

迭代器模式 -- 统一访问方式 （数据结构访问都可以用）

4. priority_queue的介绍和实现

4.1 priority_queue的使用

使用 priority_queue 的关键点

4.1.1 C++ 标准库中

代码 ：

输出：

4.1.2 自定义优先队列

PriorityQueue.h

test.cpp

输出：

5. STL标准库中stack和queue的底层结构

6.1 deque的简单介绍

6.2 deque 的缺陷

遍历 queue 的性能比较

输出：

总结

6.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器?

1. 只需要在固定的一端或两端进行操作

2. 扩展效率

3. 内存使用效率

4. CPU 缓存命中率

6.2 双端队列的模拟实现

1. 主类 Deque

2. 迭代器类 Iterator

3. 构造函数和常规操作

4. 内部实现和辅助函数

6.3 完整代码及演示：

deque.h

test.cpp

输出

相关推荐

最近更新

热门阅读

迭代器模式 -- 统一访问方式（数据结构访问都可以用）

使用 `priority_queue` 的关键点

代码：

遍历 `queue` 的性能比较

1. 主类 `Deque`

2. 迭代器类 `Iterator`