当前位置：首页 > news >正文

09--解密栈与队列：数据结构核心原理

news 2025/8/14 10:18:36

1. 栈

1.1. 栈的简介

栈是一种 特殊的线性表，具有数据 先进后出 特点。

注意：

stack本身 不支持迭代器操作
主要原因是因为stack不支持数据的随机访问，必须保证数据先进后出的特点。
stack在CPP库中实现为一种 容器适配器
所谓容器适配器，是为了适应不同的数据存储而修改底层的数据结构从而达到优化效率的目的。
参考：C++ STL容器适配器（详解）

1.2. 栈为什么没有提供迭代器？？？

栈为什么没有提供迭代器？？？

我们看CPP::stack的文档，发现stack并没有提供迭代器，这是因为stack要保证其自身特性是先进后出，后进先出的特性，如果提供了迭代器，就能够打破这一规则，栈也不再是栈。

1.3. 栈简化模拟实现

栈简化模拟实现

C版简化模拟栈：【数据结构】栈
CPP版简化模拟栈：

#pragma once
#include<vector>
#include<iostream>using namespace std;
namespace szg
{template<class T, class Container = vector<T>>class stack{private:Container _st;public:void push_back(const T& num){_st.push_back(num);}void pop_back(){_st.pop_back();}bool empty(){return _st.empty();}size_t size(){return _st.size();}const T& top(){return _st.back();}};
}

实际上，stack在库中给的容器缺省值是deque，是一个 顺序表与链表的结合体。
deque参考文档：stl_deque
deque底层逻辑简介：【CPP】双端队列简介(deque)

1.4. 适配器

适配器

在上面我们模拟实现的栈中，用到了Container，这个适配器。

什么是适配器？所谓适配器就是服务于我们所写的类能够支持其快速底层转换的一种方式。

适配器模式主要应用于，当接口里定义的方法无法满足客户的需求，或者说接口里定义的方法的名称或者方法界面与客户需求有冲突的情况。

两类模式：

对象适配器模式 - 在这种适配器模式中，适配器容纳一个它我包裹的类的实例。在这种情况下，适配器调用被包裹对象的物理实体。

类适配器模式 - 这种适配器模式下，适配器继承自已实现的类（一般多重继承）。

适配器不具备数据速率转换功能。

说到这里，我来简单介绍一种新的容器，专门用来做适配器的容器——deque

2. deque双端队列

deque是一个融合了list和vector相关特性的“混合容器”，既有list的快速插入删除特性，也有vector[]随机访问功能，算是“文武双全”的容器。

应用：作为容器适配器使用。

2.1. deque的特性

容器	vector	list	deque
优点	支持下标随机访问，[]效率高	任意位置插入删除效率高	头插、尾插效率高
缺点	头部/中间插入删除效率低，扩容消耗大	不支持[]随机访问	中间插入删除效率一般且[]效率不够极致

2.2. deque的内部构造

deque的内部控制是依靠迭代器实现的。

cur是指向当前的访问元素
first是指向当前buff的开始元素
end是指向当前buff的末尾元素的下一个地址
node是指向当前buff在中控数组中存放的位置

2.3. deque的插入删除遍历逻辑

deque的插入和删除：

deque的头插尾插效率是挺高的。这是因为尾插一个元素后，迭代器会看看中控数组最后一个buff是否还有空间，如果有则尾插到最后一个buff，如果没有就新开一个buff插入。头插一个元素，他会现在中控数组的头部开一个buff，因为默认是从中控数组中间开始新增的，所以可以支持常数时间开空间，之后同尾插同理。

中间插入插入元素处理比较麻烦

如果中间插入元素后面所有元素都往后挪动一位，效率比较低

如果中间插入元素改变buff的大小，那么上面[]访问规则就不适用，会很麻烦。

deque的元素[]访问计算规则，且[]访问效率一般

一般情况下，buff每个都是相同大小并且没有头插新元素时候，下标访问可以采用

先找是第几个buff，n/buff.size()
在确定是这个buff中的第几个元素，n%buff.size()

但是如果有头插元素，首先应该减去第一个buff元素的个数，然后在进行上面步骤。

n-=buff1.size()

void test_op1()
{srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;v.push_back(e);dq.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();printf("vector:%d\n", end1 - begin1);printf("deque:%d\n", end2 - begin2);
}
//vector:259
//deque:1263void test_op2()
{srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;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();// 拷贝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 = clock();printf("deque sort:%d\n", end1 - begin1);printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
//deque sort : 1345
//deque copy vector sort, copy back deque : 358

2.4. deque作为stack/queue适配器的优先性？

为什么CPP库中选择deque作为stack/queue的适配器呢？

因为stack和queue都只会用到头插尾插头删尾删，恰好deque头尾插删效率都很好。也可以说，deque就是专门为stack/queue适配专门设计的一个容器。

3. 队列queue

queue是队列的含义，其特点是保证了数据先进先出，后进后出的特点，底层可以用vector、list或deque进行适配。

3.1. 队列的简单模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<deque>namespace szg
{template<class T, class Container = std::deque<T>>class queue{private:Container _con;public:size_t size(){return _con.size();}bool empty(){return _con.empty();}T& front(){return _con.front();}T& back(){return _con.back();}void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}};
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
#include<iostream>int main()
{szg::queue<int> q;for (int i = 0; i < 100; i++){q.push(i);}while (!q.empty()){std::cout << q.front() << " ";q.pop();}std::cout << std::endl;//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99return 0;
}

3.2. 队列与栈的异同？

队列与栈的差异重点在于相同序列进入容器，出数据会有所不同。

容器	数据变化
栈	栈的出数据序列会变化，这取决于栈的push,pop顺序
队列	队列的出数据序列不会变化，是恒定的

4. priority_queue优先级队列 -> 堆

4.1. 简单介绍

优先级队列不是队列，是一种容器适配器，底层是大堆。

在优先级队列提供了一些接口允许公开调用：

4.2. 简单使用

// 优先级队列，默认底层是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);while (!ps.empty())
{cout << ps.top() << " ";ps.pop();
}//4 3 2 1

我们发现，优先级队列默认是大堆。

大堆小堆升序降序

优先级队列默认是大堆

小于是大堆
大于是小堆

CPP中STL::sort()

小于是升序
大于是降序

这里区分两个概念：取出结果是有序 与 真正排序 的区别。

在上面优先级队列中，我们发现while+top取出的数据是有序的，这是因为我们每次取得都是堆顶元素。至于怎么弄的，可以参考C数据结构钟堆删除数据时候得操作，首尾交换，然后size--，我觉得应该是相同的操作。

显然上面不是真正的有序，因为优先级队列中是堆。我们可以用sort这个算法函数来进行区分。

我们发现两个greater一个带括号一个不带，这是什么情况呢？

priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());

模板参数与函数参数的需要

要注意优先级队列是一种模板，需要的是类型进行实例化，而sort是函数模板实例化出来的一种函数，需要迭代器区间和具体的比较仿函数对象，而不是仅仅一个仿函数类型就行。

4.3. 仿函数

既然上面用到了仿函数，这里来介绍一下。

仿函数：也称函数对象，仿函数是一种特殊的对象！他的对象可以像函数一样去使用。

下面进行举例：

//仿函数类
struct Less
{
public:bool operator()(const int& x, const int& y){return x < y;}
};void Test()
{Less lessfunc;cout << lessfunc(5,6) << endl; // 结果：1
}

这里需要注意哈，上面的数字5和6作为参数传递给operator()，如果要用引用来接收，必须前面加上const，因为这是引用常量值。

//仿函数类
struct Less
{
public:bool operator()(const int& x, const int& y){return x < y;}
};void Test()
{Less lessfunc;cout << lessfunc(5,6) << endl;//1vector<int> v = { 1,3,4,2 };vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}//1 3 4 2cout << endl;sort(v.begin(), v.end(), lessfunc);it = v.begin();while (it != v.end()){cout << *it << " ";it++;}//1 2 3 4
}

然后上面的仿函数类可以加上模板的语法，就跟我们用的greater<int>差不多了。

//仿函数类
template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};void Test()
{vector<int> v = { 1,3,4,2 };vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;sort(v.begin(), v.end(), Less<int>());it = v.begin();while (it != v.end()){cout << *it << " ";it++;}
}

4.4. 优先级队列模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<typename T>
struct Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:Container _con;public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_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 com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child = child + 1;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}
};

// 指针模板
template<class T>
struct GreaterPDate
{bool operator()(const T& d1, const T& d2){return *d1 > *d2;}
};void test_priority_queue2()
{priority_queue<Date*, vector<Date*>, GreaterPDate<Date*>> pqptr;Date d1(2024, 4, 14);Date d2(2024, 4, 11);Date d3(2024, 5, 15);pqptr.push(&d1);pqptr.push(&d2);pqptr.push(&d3);while (!pqptr.empty()){cout << *(pqptr.top()) << " ";pqptr.pop();}cout << endl;
}

5. 反向迭代器

反向迭代器，顾名思义，反向迭代器的操作与正向迭代器恰好相反(方向)。

5.1. 简单介绍

下面我用库函数来进行一个简单演示。

std::list<int> l = { 1,2,3,4,5,6 };
std::list<int>::reverse_iterator rit = l.rbegin();
while (rit != l.rend())
{std::cout << *rit << " ";++rit;
}//6 5 4 3 2 1
std::cout << std::endl;

5.2. 反向迭代器的设计思路

思路1：我们可以像前面实现const迭代器一样写一个类，显然，这样我们即使写模板也需要针对不同的容器进行写不同的反向迭代器。
思路2：封装iterator，然后重载其部分运算符。

下面来重点介绍第二种思路的实现方式：

这样的好处是，我们只需要设计一个反向迭代器类，就可以根据不同的正向迭代器自由变换其反向迭代器。

5.3. 反向迭代器的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1namespace szg
{template<class Tterator, class Ref, class Ptr>class ReverseIterator{private:Tterator _it;public:typedef ReverseIterator<Tterator, Ref, Ptr> Self;//构造函数ReverseIterator(Tterator it):_it(it){}//解引用Ref operator*(){Tterator temp = _it;temp--;return *temp;}//->函数Ptr operator->(){return &(this->operator*());}//前置++Self& operator++(){--_it;return *this;}//前置--Self& operator--(){++_it;return *this;}//!=函数重载bool operator!=(const Self& s){return _it != s._it;}};
}

#include"List.h"
#include<list>void test()
{szg::list<int> l = { 1, 2, 3, 4, 5, 6 };/*l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_back(6);*/szg::list<int>::reverse_iterator rit = l.rbegin();while (rit != l.rend()){std::cout << *rit << " ";++rit;}//6 5 4 3 2 1std::cout << std::endl;
}int main()
{//std::list<int> l = { 1,2,3,4,5,6 };//std::list<int>::reverse_iterator rit = l.rbegin();//while (rit != l.rend())//{//	std::cout << *rit << " ";//	++rit;//}//6 5 4 3 2 1//std::cout << std::endl;test();return 0;
}