📝个人主页🌹：Eternity._

⏩收录专栏⏪：C++ “ 登神长阶 ”

🤡往期回顾🤡：模拟实现list与迭代器

🌹🌹期待您的关注 🌹🌹

❀stack和queue

📕1. stack和queue的基本概念🎩stack的基本概念🎈queue的基本概念

📙2. stack与queue的常用操作⛰️stack的常用操作🌄queue的常用操作

📚3. 容器适配器📒4. deque的简单介绍💧deque的原理介绍🌊deque的缺陷

📜5. stack和queue的模拟实现🍂stack的模拟实现🍁queue的模拟实现

📖6. priority_queue🌞priority_queue的基本概念🌙priority_queue的常用操作⭐priority_queue的模拟实现

🔥7. 总结

---

前言： 在编程的世界里，数据结构是构建高效、可靠程序的基础。它们就像是我们编程工具箱中的精密工具，帮助我们解决各种复杂的问题。而在C++的STL中，栈（Stack）和队列（Queue）是两种非常重要的数据结构，它们以不同的方式管理和操作数据，为我们的程序提供了极大的灵活性

为了真正掌握它们，我们需要深入学习它们在STL中的实现方式，理解它们背后的原理和机制，以及学习如何在实际编程中有效地使用它们，让我们一起踏上学习STL栈与队列的旅程吧！

---

📕1. stack和queue的基本概念

🎩stack的基本概念

栈（Stack）是一种后进先出（LIFO）的数据结构

它的操作特性使其在处理递归调用、函数调用栈以及撤销操作等问题时表现出色。通过栈，我们可以轻松地实现如括号匹配、表达式求值等算法。

---

🎈queue的基本概念

队列（Queue）则是一种先进先出（FIFO）的数据结构

它在处理需要按顺序处理的任务时非常有用。无论是操作系统中的任务调度，还是网络中的数据包传输，队列都扮演着不可或缺的角色。

---

📙2. stack与queue的常用操作

⛰️stack的常用操作

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

<code>void test_stack()

{

stack<int, vector<int>> st; // 构造栈

st.push(1); // 将元素val压入stack中

st.push(2);

st.push(3);

st.push(4);

printf("栈中有效元素个数为：%d", st.size()); // 返回stack中元素的个数

while (!st.empty()) // 检测stack是否为空

{

printf("%d ", st.top()); // 返回栈顶元素的引用

st.pop(); // 将stack中尾部的元素弹出

}

}

相较于之前的栈的常用函数学习还是很简单的，在了解完基本用法后，这里推荐几个相关题目

---

🌄queue的常用操作

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

void test_queue()

{

queue<int, list<int>> q; // 构造队列

q.push(1); // 在队尾将元素val入队列

q.push(2);

q.push(3);

q.push(4);

printf("队列中有效元素个数为：%d", q.size()); // 返回stack中元素的个数

while (!q.empty()) // 检测queue是否为空

{

printf("%d ", q.front()); // 返回队头元素

q.pop(); // 将队头元素出队列

}

}

相较于之前的栈的常用函数学习还是很简单的，在了解完基本用法后，这里推荐几个相关题目，不多说直接上题目巩固

最小栈

栈的压入、弹出序列

逆波兰表达式求值

用栈实现队列

用队列实现栈

---

📚3. 容器适配器

容器适配器是一种机制，它接受一种已有的容器类型，通过封装和改造，使其行为看起来像另一种类型。这允许我们使用特定的数据访问和操作模式（如栈、队列或优先队列）来管理容器中的数据，而无需修改原始容器的实现。

C++标准库定义了三种序列容器适配器：

容器适配器	概念
stack（栈）	栈是一种后进先出（LIFO）的数据结构，具有push（压栈）、pop（弹栈）、top（查看栈顶元素）等基本操作。在STL中，stack可以建立在vector、list、deque等容器之上。
queue（队列）	队列是一种先进先出（FIFO）的数据结构，具有push（入队）、pop（出队）、front（查看队首元素）、back（查看队尾元素）等基本操作。queue在STL中也是一个容器适配器。
priority_queue（优先队列）	优先队列是一种特殊的队列，其中元素的出队顺序不是按照它们进入队列的顺序，而是根据它们的优先级。priority_queue提供了push（插入元素）、pop（删除最高优先级元素）、top（查看最高优先级元素）等操作。

---

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

有了容器适配器后，我们在模拟实现时，就不需要自己再从底层出发，而是可以直接调用已经存在的容器

---

📒4. deque的简单介绍

💧deque的原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构

双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高

注意：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组

我们查表发现deque基本上包含了vector与list的用法，那我们之前为什么还要费尽心思去学习呢？直接学习deque不好吗？

---

🌊deque的缺陷

与vector比较

deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较

其底层是连续空间，空间利用率比较高，不需要存储额外字段。但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，

在序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

因此我们还是要单独学习list和vector的

---

📜5. stack和queue的模拟实现

在模拟实现这俩个容器的时候，我们只要实现它的常用函数，在模拟实现时，我们只需要复用就可以了

🍂stack的模拟实现

<code>template<class T, class Container = deque<T>>

class stack

{

public:

void push(const T& x)

{

_con.push_back(x);

}

void pop()

{

_con.pop_back();

}

const T& top()

{

return _con.back();

}

bool empty()

{

return _con.empty();

}

size_t size()

{

_con.size();

}

private:

Container _con;

};

---

🍁queue的模拟实现

template<class T, class Container = deque<T>>

class queue

{

public:

void push(const T& x)

{

_con.push_back(x);

}

void pop()

{

_con.pop_front();

}

bool empty()

{

return _con.empty();

}

const T& front()

{

return _con.front();

}

size_t size()

{

_con.size();

}

private:

Container _con;

};

关于stack与queue的模拟实现就是复用之前学过的函数，没什么好说的，让我们进入重头戏

---

📖6. priority_queue

🌞priority_queue的基本概念

关于优先级队列，我们就可以把它想象成堆那样的结构

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成

堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue

注意：默认情况下priority_queue是大堆

---

🌙priority_queue的常用操作

函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

<code>void test_priority_queue()

{

std::priority_queue<int> q; // 构造优先级队列

q.push(1); // 在优先级队列中插入元素x

q.push(43);

q.push(233);

q.push(43);

q.push(4);

q.push(73);

q.push(2);

while (!q.empty()) // 检测优先级队列是否为空

{

printf("%d ", q.top()); // 返回堆顶元素

q.pop(); // 删除堆顶元素

}

}

---

⭐priority_queue的模拟实现

// 仿函数，数据的比较方法

template<class T>

class Less

{

public:

bool operator()(const T& x, const T& y)

{

return x < y;

}

};

template<class T>

class Greater

{

public:

bool operator()(const T& x, const T& y)

{

return x > y;

}

};

template<class T, class Container = vector<T>, class Compare = Less<T>>

class priority_queue

{

public:

priority_queue() // 无参构造

{ }

template<class InputIterator>

priority_queue(InputIterator first, InputIterator last) // 迭代器构造

:_con(first,last)

{

// 向下调整建堆

for (int i = (_con.size() - 2) / 2; i >= 0; i--)

{

AdjustDown(i);

}

}

void AdjustUp(int child) // 向上调整

{

int parent = (child - 1) / 2;

Compare com;

while (child > 0)

{

if (com(_con[child], _con[parent]))

{

swap(_con[child], _con[parent]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

void AdjustDown(int parent) // 向下调整

{

int child = parent * 2 + 1;

Compare com;

while (com(child , _con.size()))

{

if ((child + 1 < _con.size()) &&

com(_con[child + 1], _con[child]))

{

child++;

}

if (com(_con[child] , _con[parent]))

{

swap(_con[child], _con[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

void push(const T& x)

{

_con.push_back(x);

AdjustUp(_con.size() - 1); // 在插入新元素时，我们要调整容器里面的元素

}

size_t size()

{

return _con.size();

}

const T& top()

{

return _con[0];

}

void pop()

{

swap(_con[0], _con[_con.size() - 1]);

_con.pop_back();

AdjustDown(0); // 删除时，依旧要调整元素

}

bool empty()

{

return _con.empty();

}

private:

Container _con;

};

关于priority_queue的模拟实现，依然是以复用为主，只不过多了一些堆要使用的调整函数，而且我们在查priority_queue这个容器时，不难发现其实它是有三个模板参数的，它的第三个模板参数就是，数据的排列方式，也就是决定大小堆的，这就涉及到了仿函数，关于仿函数，下节我们在讲！

---

🔥7. 总结

在深入探讨了STL（Standard Template Library）中的栈（stack）与队列（queue）之后，我们不难发现这两大数据结构在程序设计中扮演着至关重要的角色。栈与队列的引入，不仅极大地丰富了C++程序员的工具箱，也为解决各种实际问题提供了更为高效、优雅的方法

学习栈与队列并不仅仅是为了掌握它们的基本操作和应用场景。更重要的是，我们要学会如何根据问题的特点选择合适的数据结构，以及如何有效地利用数据结构来解决实际问题。在这个过程中，我们需要不断思考、探索和实践，才能不断提升自己的编程能力和问题解决能力。让我们继续前行，不断探索编程的奥秘，享受编程的乐趣！

谢谢大家支持本篇到这里就结束了，端午安康，祝大家天天开心！