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 种。

适配器模式 -- 封装转换

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

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

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

4. priority_queue的介绍和实现 

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

4.1 priority_queue的使用

使用 priority_queue关键点

  1. 默认大顶堆priority_queue<int>,使用默认的 less<int> 比较函数,因此它是一个大顶堆。
  2. 小顶堆priority_queue<int, vector<int>, greater<int>>,通过传递 greater<int> 作为比较函数,使其成为小顶堆。
  3. 需要指定容器类型:当指定比较函数(如 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 的迭代器要频繁地检测是否移动到某段小空间的边界,导致效率低下。而在序列式场景中,可能需要经常遍历。因此在实际中,需要线性结构时,大多数情况下优先考虑 vectorlistdeque 的应用并不多。而目前能看到的一个应用就是,STL 用其作为 stackqueue 的底层数据结构。

以下通过对大量数据排序来证明遍历 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 在某些方面具有优势,但由于其遍历性能较低和内存管理复杂等缺陷,在需要频繁遍历或要求高效随机访问的场景中,vectorlist 通常是更好的选择。因此,在实际应用中,deque 的使用相对较少,主要用于特定场景,如 stackqueue 的底层数据结构。

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

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

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

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

stackqueue 主要在固定的一端或两端进行操作:

  • stack:后进先出(LIFO),主要在末端进行插入和删除操作。
  • queue:先进先出(FIFO),在前端删除,在末端插入。

由于 deque(双端队列)支持在两端进行高效的插入和删除操作,因此非常适合用于实现 stackqueue

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 类的操作会更新指针成员 curstart 等,确保它们始终指向有效的内存区域,因此不会出现释放内存导致悬空指针的情况。在 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++ 中 stackqueue 的底层数据结构和优先队列priority_queue的简单实现。我们下期再见

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/703464.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C#开源软件:OneNote组件oneMore轻松打造自己的公众号编辑器

OneMore是一款为Microsoft OneNote设计的插件&#xff0c;它提供了许多扩展功能来增强OneNote的使用体验。 插件功能概述&#xff1a; OneMore插件拥有多达一百多个扩展功能&#xff0c;这些功能覆盖了笔记编辑、搜索、导出等多个方面&#xff0c;为用户提供了更加便捷和高效的…

【项目实战】--云备份系统

1、云备份认识 自动将本地计算机上指定文件夹中需要备份的文件上传备份到服务器中。并且能够随时通过浏览器进行查看并且下载&#xff0c;其中下载过程支持断点续传功能&#xff0c;而服务器也会对上传为文件进行热点管理&#xff0c;将非热点文件进行压缩存储&#xff0c;节省…

openGauss 6.0.0 一主二备集群安装及使用zcbus实现Oracle到openGauss的数据同步

一、前言 openGauss 6.0.0-RC1是openGauss 2024年3月发布的创新版本&#xff0c;该版本生命周期为0.5年。根据openGauss官网介绍&#xff0c;6.0.0-RC1与之前的版本特性功能保持兼容,另外&#xff0c;在和之前版本兼容的基础上增加了很多新功能&#xff0c;比如分区表性能优化…

Java集合自测题

文章目录 一、说说 List , Set , Map 三者的区别&#xff1f;二、List , Set , Map 在 Java 中分别由哪些对应的实现类&#xff1f;底层的数据结构&#xff1f;三、有哪些集合是线程不安全的&#xff1f;怎么解决呢&#xff1f;四、HashMap 查询&#xff0c;删除的时间复杂度五…

autosleep框架设计与实现

在低功耗系统中&#xff0c;autosleep是一个较小的模块&#xff0c;是低功耗主流程的入口。在Linux内核中&#xff0c;autosleep是休眠流程的触发点和入口点&#xff0c;PM Core的休眠流程入口pm_suspend()就是被autosleep的睡眠工作队列调用而进入休眠的。 该功能的支持受宏…

MyBatis 参数上的处理的细节内容

1. MyBatis 参数上的处理的细节内容 文章目录 1. MyBatis 参数上的处理的细节内容2. MyBatis 参数上的处理3. 准备工作4. 单个(一个)参数4.1 单个(一个)简单类型作为参数4.2 单个(一个) Map集合 作为参数4.3 单个(一个) 实体类POJO作为参数 5. 多个参数5.1 Param注解(命名参数)…

计算机相关专业的探讨

目录 一、计算机相关专业是否仍是“万金油”选择 二、计算机行业的未来发展态势 三、从专业与个人的匹配度判断选择计算机相关专业 四、对于高考生的建议 一、计算机相关专业是否仍是“万金油”选择 计算机相关专业在过去很长一段时间内确实被视为“万金油”专业&#xff0…

算法训练营day06--242.有效的字母异位词+349. 两个数组的交集+202. 快乐数+1. 两数之和

一、242.有效的字母异位词 题目链接&#xff1a;https://leetcode.cn/problems/valid-anagram/description/ 文章讲解&#xff1a;https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html 视频讲解&#xff1a;http…

电视剧推荐

1、《春色寄情人》 2、《唐朝诡事录》 3、《南来北往》 4、《与凤行》 5、《利剑玫瑰》 6、《承欢记》

【教程】使用立创EDA打开JSON格式的PCB及原理图

这里写目录标题 一、将PCB和原理图放同一文件夹二、打开嘉立创EDA并导入.zip文件三、选择.zip文件并选择 “导入文件并提取库” 一、将PCB和原理图放同一文件夹 并打包成.zip文件 二、打开嘉立创EDA并导入.zip文件 嘉立创 我这里用的网页端&#xff0c;客户端下载页面拉到…

html的网页制作代码分享

<!-- prj_8_2.html --> <!DOCTYPE html> <html lang "EN"><head><meta charset"utf-8" /><title>页面布局设计</title><style type "text/css">*{padding: 0px;margin:0px;}#header{back…

Spring中IOC容器

IoC IOC容器 IoC是一种设计思想&#xff0c;面向对象编程 Spring通过IoC管理所有Java对象的实例化和初始化&#xff0c;控制对象之间依赖关系 将IoC容器管理的Java对象称为Spring Bean&#xff0c;与new创建的对象没有区别 控制反转&#xff08;IoC Inversion of Controle&a…

世优科技AI数字人多模态交互系统“世优波塔”正式发布

2024年6月6日&#xff0c;世优科技“波塔发布会”在北京举办&#xff0c;本次发布会上&#xff0c;世优科技以全新的“波塔”产品诠释了更高效、更智能、更全面的AI数字人产品及软硬件全场景解决方案&#xff0c;实现了世优品牌、产品和价值的全面跃迁。来自行业协会、数字产业…

大众点评全国丽人POI采集225万家-2024年5月底

大众点评全国丽人POI采集225万家-2024年5月底 店铺POI点位示例&#xff1a; 店铺id Hav6zIYtzhyyopIZ 店铺名称 防屏蔽 十分制服务评分 8.9 十分制环境评分 8.9 十分制划算评分 8.9 人均价格 210 评价数量 19935 店铺地址 建北一支路观音桥步行街红鼎国际A座9-9 店铺…

英伟达GPU对比分析:A100、A800、H100与H800

在当今技术迅速发展的时代&#xff0c;英伟达的GPU产品线提供了多种高性能选项&#xff0c;以满足不同类型的工作负载需求。本文将对英伟达的四种GPU型号——A100、A800、H100和H800进行深入对比分析&#xff0c;探讨它们在性能、架构、应用场景等方面的差异&#xff0c;以帮助…

LIN 入门(1)

1、概述 LIN 是什么 LIN 是 Local Interconnect Network 的缩写&#xff0c;是基于 UART/SCI(Universal Asynchronous Receiver-Transmitter / Serial Communication Interface&#xff0c;通用异步收发器/串行通信接口)的低成本串行通信协议。可用于汽车、家电、办 公设备等…

代码随想录-二叉树 | 111 二叉树的最小深度

代码随想录-二叉树 | 111 二叉树的最小深度 LeetCode 111 二叉树的最小深度解题思路代码难点总结 LeetCode 111 二叉树的最小深度 题目链接 代码随想录 题目描述 给定一个二叉树&#xff0c;找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说…

讯飞星火模型-语音转文字实现

目录 项目结构 准备音频 接口Demo 准备代码&#xff08;完整修改后&#xff09; 测试提取中文文字代码 结果 下载链接&#xff1a; 这是上周打算试试&#xff0c;提取视频文字之后&#xff0c;制作视频字幕&#xff0c;从而想用大模型来实现&#xff0c;基本的demo可以在…

图像的混合与渐进变换

1.实验目的 平常我们看到的美图秀秀等两个图片混合是怎么生成的呢&#xff0c;今天我们看看图像处理关于这部分怎么做的&#xff1f; 2.实验条件 pycharm python编译器 3.实验代码 # File: 图像混合与渐进变换.py # Author: chen_song # Time: 2024/6/11 下午6:08 "…

CorelDRAW® Graphics Suite 全新 2024 专业图形设计软件

CorelDRAW Graphics Suite 是配备齐全的专业设计工具包&#xff0c;可以非常高的效率提供令人惊艳的矢量插图、布局、照片编辑和排版项目。价格实惠的订阅获得令人难以置信的持续价值&#xff0c;即时、有保障地获得独家的新功能和内容、一流的性能&#xff0c;以及对最新技术的…