免费的logo设计网站,阿里云 wordpress搭建网站,珠海企业营销型网站建设公司,搜索引擎营销名词解释文章目录 C 栈与队列详解#xff1a;基础与进阶应用前言第一章#xff1a;栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章#xff1a;队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.… 文章目录 C 栈与队列详解基础与进阶应用前言第一章栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.1 示例与输出 第三章优先队列的介绍与使用3.1 优先队列的介绍3.2 优先队列的使用3.2.1 示例默认大顶堆3.2.2 示例与输出3.2.3 示例小顶堆 3.3 优先队列的模拟实现3.3.1 示例与输出 第四章容器适配器4.1 什么是容器适配器4.2 deque 的简单介绍4.2.1 deque 的原理介绍4.2.2 deque 的缺陷4.2.3 deque 的常见操作 4.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器4.4 STL 标准库中 stack 和 queue 的模拟实现4.4.1 stack 的模拟实现4.4.2 queue 的模拟实现 第五章总结5.1 核心要点回顾 C 栈与队列详解基础与进阶应用 欢迎讨论在学习过程中如果有任何疑问或想法欢迎在评论区留言一起讨论。 点赞、收藏与分享觉得这篇文章对你有帮助吗记得点赞、收藏并分享给更多的朋友吧你们的支持是我不断进步的动力 分享给更多人如果你觉得这篇文章对你有帮助欢迎分享给更多对 C 感兴趣的朋友一起学习进步 前言
栈与队列是常见的数据结构常被用于不同的算法场景。在本文中我们将详细探讨栈与队列的基本概念、实际应用及其模拟实现。栈和队列在日常开发中的重要性不言而喻通过对这两种数据结构的深入理解将助你更加灵活地应对算法题目和工程开发。 在阅读本篇之前可以先看看stl最基础的部分 【C篇】揭开 C STL list 容器的神秘面纱从底层设计到高效应用的全景解析附源码 【C篇】从零实现 C Vector深度剖析 STL 的核心机制与优化 第一章栈的介绍与使用
1.1 栈的介绍 栈 (Stack) 是一种 后进先出 (LIFO, Last In First Out) 的数据结构。这意味着栈中最后一个被插入的元素会第一个被移出。这种特性使得栈在实现某些算法时非常有用例如函数调用栈、表达式求值以及括号匹配等。 栈提供的基本操作包括
push()将元素压入栈顶。pop()将栈顶元素弹出。top()获取栈顶元素。empty()检查栈是否为空。size()获取栈中元素的数量。 常见的栈使用场景有表达式求值、深度优先搜索DFS以及回溯法。 1.2 栈的使用
1.2.1 最小栈
最小栈 (Min Stack) 是栈的扩展应用除了提供基本的栈操作外还能够在常量时间内返回栈中的最小值。下面展示一个最小栈的具体实现。
#include stack
using namespace std;class MinStack {
public:// 构造函数MinStack() {}// 将元素 x 压入栈中void push(int x) { _elem.push(x); // 元素入栈if (_min.empty() || x _min.top()) { _min.push(x); // 如果 x 小于等于当前最小值则将 x 也压入 _min 栈}}// 移除栈顶元素void pop() {if (_min.top() _elem.top()) {_min.pop(); // 如果当前栈顶元素是最小值将其从 _min 栈中移除}_elem.pop();}// 获取栈顶元素int top() { return _elem.top(); }// 获取当前栈中的最小值int getMin() { return _min.top(); }private:stackint _elem; // 存储栈中的所有元素stackint _min; // 存储栈中的最小值
};1.2.2 示例与输出
int main() {MinStack minStack;minStack.push(-2);minStack.push(0);minStack.push(-3);cout Current Min: minStack.getMin() endl; // 输出 -3minStack.pop();cout Top: minStack.top() endl; // 输出 0cout Current Min: minStack.getMin() endl; // 输出 -2return 0;
}输出结果
Current Min: -3
Top: 0
Current Min: -2在这个例子中我们实现了一个最小栈可以在常量时间内获取栈中的最小值。在压栈和弹栈操作时我们同步更新 _min 栈以维护最小值。 1.3 栈的模拟实现 栈的标准实现使用 std::stack 容器但在某些场景下可以使用 std::vector 来模拟栈的功能。由于栈的所有操作都围绕末端进行因此 vector 的尾插操作与 stack 类似。 #include vector
using namespace std;template typename T
class SimulatedStack {
public:// 向栈中压入元素void push(const T x) {_data.push_back(x);}// 弹出栈顶元素void pop() {_data.pop_back();}// 获取栈顶元素T top() {return _data.back();}// 检查栈是否为空bool empty() const {return _data.empty();}// 获取栈的大小size_t size() const {return _data.size();}private:vectorT _data; // 用于存储栈元素的容器
};这种模拟实现使用了 vector 的尾插操作可以高效地模拟栈的行为。 第二章队列的介绍与使用
2.1 队列的介绍 队列 (Queue) 是一种 先进先出 (FIFO, First In First Out) 的数据结构。这意味着第一个进入队列的元素会第一个被移出。队列通常用于任务调度、广度优先搜索 (BFS) 等场景。 队列的基本操作包括
push()将元素插入队尾。pop()移除队头元素。front()获取队头元素。back()获取队尾元素。empty()检查队列是否为空。size()获取队列中的元素数量。
2.2 队列的使用
以下是队列的基本用法展示包括插入和删除元素。
#include queue
#include iostream
using namespace std;int main() {queueint q;q.push(1); // 向队尾插入元素1q.push(2); // 向队尾插入元素2cout Front: q.front() endl; // 输出队头元素 1cout Back: q.back() endl; // 输出队尾元素 2q.pop(); // 移除队头元素cout After pop, Front: q.front() endl; // 输出新的队头元素 2return 0;
}2.2.1 示例与输出
输出结果
Front: 1
Back: 2
After pop, Front: 2在这个例子中我们展示了队列的 push()、pop()、front() 和 back() 操作。 2.3 队列的模拟实现 在一些场景中标准库中的 std::queue 可能无法满足特定需求我们可以通过其他容器类来模拟实现队列。由于队列需要支持在头部删除和尾部插入的操作使用 std::list 会比 std::vector 更为高效。list 允许在常数时间内进行头部和尾部的插入与删除操作因此非常适合用于队列的实现。 下面是一个基于 list 的队列模拟实现
#include list
using namespace std;template typename T
class SimulatedQueue {
public:// 向队尾插入元素void push(const T x) {_data.push_back(x);}// 移除队头元素void pop() {_data.pop_front();}// 获取队头元素T front() {return _data.front();}// 获取队尾元素T back() {return _data.back();}// 检查队列是否为空bool empty() const {return _data.empty();}// 获取队列的大小size_t size() const {return _data.size();}private:listT _data; // 用于存储队列元素的容器
};2.3.1 示例与输出
int main() {SimulatedQueueint q;q.push(10); // 向队尾插入元素q.push(20);cout 队头: q.front() endl; // 输出队头元素 10cout 队尾: q.back() endl; // 输出队尾元素 20q.pop(); // 移除队头元素cout 新的队头: q.front() endl; // 输出新的队头元素 20return 0;
}输出结果
队头: 10
队尾: 20
新的队头: 20在这个例子中SimulatedQueue 模拟了队列的基本功能包括在队尾插入元素和移除队头元素。 第三章优先队列的介绍与使用
3.1 优先队列的介绍 优先队列 (Priority Queue) 是一种特殊类型的队列其中每个元素都关联有一个优先级。优先队列的特点是元素的弹出顺序不再是按照先进先出而是按照元素的优先级来决定。通常优先队列可以用来模拟堆结构。 在默认情况下C 标准库中的 std::priority_queue 是一个大顶堆即优先队列中的最大元素会优先弹出。我们也可以通过自定义比较函数来实现小顶堆从而使得最小元素优先弹出。
优先队列的常见操作包括
push()向优先队列中插入元素。pop()移除优先级最高的元素。top()获取优先级最高的元素。empty()检查优先队列是否为空。size()获取优先队列中的元素数量。
3.2 优先队列的使用
下面展示了如何使用 std::priority_queue 进行优先队列操作。
3.2.1 示例默认大顶堆
#include iostream
#include queue
#include vector
using namespace std;int main() {priority_queueint pq; // 默认大顶堆pq.push(10);pq.push(5);pq.push(20);cout 优先级最高的元素: pq.top() endl; // 输出 20pq.pop(); // 移除优先级最高的元素cout 新的优先级最高的元素: pq.top() endl; // 输出 10return 0;
}3.2.2 示例与输出
输出结果
优先级最高的元素: 20
新的优先级最高的元素: 10在这个例子中priority_queueint 实现了一个大顶堆插入元素后优先级最高的元素值最大的元素会优先弹出。
3.2.3 示例小顶堆
我们也可以使用 std::greaterT 来改变默认的比较方式从而实现小顶堆。下面是一个小顶堆的例子
#include iostream
#include queue
#include vector
using namespace std;int main() {priority_queueint, vectorint, greaterint pq; // 小顶堆pq.push(10);pq.push(5);pq.push(20);cout 优先级最高的元素最小值: pq.top() endl; // 输出 5pq.pop(); // 移除优先级最高的元素cout 新的优先级最高的元素: pq.top() endl; // 输出 10return 0;
}输出结果
优先级最高的元素最小值: 5
新的优先级最高的元素: 10在这个例子中priority_queueint, vectorint, greaterint 实现了一个小顶堆其中优先级最高的元素是值最小的元素。 3.3 优先队列的模拟实现 优先队列通常是基于堆实现的。在 C 中标准库中的 priority_queue 使用 std::vector 作为底层存储并通过堆算法管理优先级。在需要自定义优先队列行为时可以自己实现一个简单的优先队列利用堆的概念来操作。 下面是一个基于 std::vector 实现的简单优先队列
#pragma once#include iostream
#include vector
using namespace std;// priority_queue---堆
namespace W {// 默认的比较函数为 less实现大顶堆templateclass Tstruct less {bool operator()(const T left, const T right) {return left right;}};// greater 实现小顶堆templateclass Tstruct greater {bool operator()(const T left, const T right) {return left right;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue {public:// 创造空的优先级队列priority_queue() : c() {}// 构造函数支持从迭代器范围初始化templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first, last) {// 将 c 中的元素调整成堆的结构int count c.size();int root ((count - 2) 1);for (; root 0; root--)AdjustDown(root);}// 向队列中插入元素void push(const T data) {c.push_back(data);AdjustUP(c.size() - 1);}// 移除优先级最高的元素void pop() {if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}// 获取优先队列的大小size_t size() const {return c.size();}// 检查优先队列是否为空bool empty() const {return c.empty();}// 返回优先级最高的元素不允许修改const T top() const {return c.front();}private:// 向上调整维护堆的性质void AdjustUP(int child) {// 计算父节点的索引等同于 (child - 1) / 2移位操作符效率更快int parent ((child - 1) 1);while (child) {if (Compare()(c[parent], c[child])) {swap(c[child], c[parent]);child parent;parent ((child - 1) 1);} else {return;}}}// 向下调整维护堆的性质void AdjustDown(int parent) {size_t child parent * 2 1;while (child c.size()) {// 找到父节点较大的孩子if (child 1 c.size() Compare()(c[child], c[child 1])) {child 1;}// 检查双亲是否满足堆的条件if (Compare()(c[parent], c[child])) {swap(c[child], c[parent]);parent child;child parent * 2 1;} else {return;}}}private:Container c; // 底层容器默认为 vector};
} 3.3.1 示例与输出
void TestQueuePriority() {W::priority_queueint q1;// 向大顶堆中插入元素q1.push(5);q1.push(1);q1.push(4);q1.push(2);q1.push(3);q1.push(6);// 输出堆顶元素cout 优先级最高的元素: q1.top() endl; // 输出 6// 弹出两个元素q1.pop();q1.pop();// 再次输出堆顶元素cout 新的优先级最高的元素: q1.top() endl; // 输出 4// 使用 greater 创建小顶堆vectorint v{5, 1, 4, 2, 3, 6};W::priority_queueint, vectorint, W::greaterint q2(v.begin(), v.end());// 输出小顶堆的堆顶元素cout 优先级最高的元素(最小值): q2.top() endl; // 输出 1// 弹出两个元素q2.pop();q2.pop();// 再次输出小顶堆的堆顶元素cout 新的优先级最高的元素(最小值): q2.top() endl; // 输出 3
}输出结果
优先级最高的元素: 6
新的优先级最高的元素: 4
优先级最高的元素(最小值): 1
新的优先级最高的元素(最小值): 3在这个模拟实现中我们使用 std::vector 作为底层容器并且通过堆排序算法来维护优先队列的顺序。通过 less 和 greater 函数对象我们可以分别实现大顶堆和小顶堆。 第四章容器适配器
4.1 什么是容器适配器 容器适配器 (Container Adapter) 是一种设计模式目的是将一种容器包装为另一种接口形式。容器适配器提供了一组特定的成员函数来访问底层的容器。C 标准库中stack、queue 和 priority_queue 都是容器适配器它们对容器的操作进行了限制并定义了特定的访问规则。 容器适配器本质上是对基础容器的封装它们可以使用 vector、deque、list 等作为底层实现而具体使用哪种容器可以根据需求进行调整。容器适配器只暴露了某些特定的操作而底层容器的更多操作则被隐藏。 虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque 常见的容器适配器 stack实现后进先出LIFO原则。 queue实现先进先出FIFO原则。 priority_queue基于优先级进行元素的弹出通常是大顶堆。 4.2 deque 的简单介绍
双端队列 (deque, Double-Ended Queue) 是一种可以在头尾两端进行高效插入和删除操作的序列式容器。与 vector 类似deque 提供了动态数组的功能但它比 vector 更加灵活允许在头尾两端都进行元素的添加和删除。 4.2.1 deque 的原理介绍
双端操作deque 提供了双端操作即允许在容器的两端进行插入和删除操作。其时间复杂度为常数时间 O ( 1 ) O(1) O(1)这使得它比 vector 更适合需要频繁在两端插入或删除元素的场景。非连续存储虽然 deque 表面上看起来像是一个连续的数组但它的底层实现并非真正连续而是由多块小的连续内存块组合而成这就允许 deque 在进行元素插入或删除时不需要像 vector 一样移动大量元素。
下面是一张简化的 deque 的内存布局示意图
--------------------------------
| Block 1 | Block 2 | Block 3 |
--------------------------------每个块表示 deque 底层的一部分内存插入或删除元素时只需要操作相应块中的数据而不需要重新分配整个数组的内存。 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问 的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示 那deque是如何借助其迭代器维护其假想连续的结构呢 了解一下即可 4.2.2 deque 的缺陷
虽然 deque 在插入和删除操作上比 vector 更高效但它也有一些缺点
遍历性能较低由于 deque 的存储结构不是一个连续的内存块所以在遍历 deque 时迭代器需要处理内存块之间的跳转导致遍历性能不如 vector。内存利用率稍低因为 deque 是由多个小内存块组成的所以它的内存利用率相比 vector 稍差。不过与 list 比较deque 的内存效率还是更高。
4.2.3 deque 的常见操作
#include deque
#include iostream
using namespace std;int main() {dequeint d;// 在队列的两端插入元素d.push_back(10);d.push_back(20);d.push_front(5);cout 队头: d.front() endl; // 输出 5cout 队尾: d.back() endl; // 输出 20// 删除队列的两端元素d.pop_front();d.pop_back();cout 新的队头: d.front() endl; // 输出 10return 0;
}输出结果
队头: 5
队尾: 20
新的队头: 10这个示例展示了 deque 如何进行两端的插入和删除操作。可以看到deque 支持同时在队头和队尾进行高效的操作。 4.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器
C 标准库中stack 和 queue 的底层容器默认使用 deque这是因为 deque 在元素插入和删除时的性能优势以及空间利用率较高的特点正好符合 stack 和 queue 对容器的需求。
高效的尾部插入和删除对于 stack只需要支持在容器的尾部插入和删除元素deque 的 push_back() 和 pop_back() 操作可以在常数时间内完成比 vector 在扩容时效率更高。高效的头部插入和删除对于 queue需要在尾部插入元素、在头部删除元素deque 同时支持 push_back() 和 pop_front() 操作效率比 list 高且不需要存储额外的指针信息。
虽然 vector 也可以作为 stack 的底层容器但它在尾部插入元素时需要在扩容时移动大量元素因此效率不如 deque。而 list 虽然也支持两端插入删除操作但由于需要存储额外的指针信息空间利用率不如 deque 高。因此deque 被认为是 stack 和 queue 的默认最佳选择。 4.4 STL 标准库中 stack 和 queue 的模拟实现
4.4.1 stack 的模拟实现
stack 的模拟实现只需要封装一个可以支持末端插入和删除操作的容器默认情况下使用 deque 作为底层容器。
#include dequenamespace W {template typename T, typename Container dequeT
class stack {
public:stack() {}// 向栈中压入元素void push(const T x) {_c.push_back(x);}// 弹出栈顶元素void pop() {_c.pop_back();}// 获取栈顶元素T top() {return _c.back();}// 检查栈是否为空bool empty() const {return _c.empty();}// 获取栈的大小size_t size() const {return _c.size();}private:Container _c; // 底层容器默认使用 deque
};
}4.4.2 queue 的模拟实现
queue 的实现需要支持队尾插入元素、队头删除元素的操作。类似 stackqueue 默认使用 deque 作为底层容器。
#include dequenamespace W {template typename T, typename Container dequeT
class queue {
public:queue() {}// 向队尾插入元素void push(const T x) {_c.push_back(x);}// 移除队头元素void pop() {_c.pop_front();}// 获取队头元素T front() {return _c.front();}// 获取队尾元素T back() {return _c.back();}// 检查队列是否为空bool empty() const {return _c.empty();}// 获取队列的大小size_t size() const {return _c.size();}private:Container _c; // 底层容器默认使用 deque
};
}第五章总结
在本文中我们详细探讨了 栈 (stack) 和 队列 (queue) 的概念、应用及其实现方式。通过对 deque 和 priority _queue 的深入理解我们可以更高效地解决实际编程问题。
5.1 核心要点回顾
栈是一种后进先出的数据结构常用于表达式求值、函数调用栈等。队列是一种先进先出的数据结构广泛应用于任务调度、广度优先搜索等场景。优先队列根据元素的优先级进行排序常用于调度和路径优化算法。deque 作为双端队列支持在头尾两端进行高效的插入和删除操作。容器适配器 stack 和 queue 使用 deque 作为底层容器利用其高效的插入删除操作实现栈和队列的功能。
通过对这些数据结构的深入理解我们能够在编程中更加灵活、准确地选择合适的工具来解决实际问题。 讨论区如果你有任何问题欢迎在评论区留言讨论 支持一下如果你觉得这篇文章对你有帮助请点赞、收藏并分享给更多学习者 以上就是关于【C篇】栈的层叠与队列的流动在 STL 的节奏中聆听算法的静谧旋律的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
