我要评论前言
在 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. deque的简单介绍
deque（双端队列）是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 o(1)。
与 vector 比较，deque 在头部插入时效率更高，因为不需要搬移元素；与 list 比较，deque 的空间利用率更高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落 在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
那deque是如何借助其迭代器维护其假想连续的结构呢？
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 的底层数据结构。
为什么选择 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 缓存。
7. 双端队列的模拟实现
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;
}
}8. 完整代码及演示
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的简单实现。
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论