C++ STL deque 双端队列

• STL(4) deque 双端队列
  • 1 deque简介
• Container adapter 容器适配器
• stack
• queue
• priority Queue 优先级队列
  • 声明及头文件

STL(4) deque 双端队列

1 deque简介

双端操作：可以在队列的两端高效地进行插入和删除操作。

动态数组：内部实现为一个动态数组，支持随机访问。

分段连续存储：与 vector 不同，deque 的分段连续存储结构使得在两端插入和删除元素时效率更高。

#include <iostream>
#include <deque>int main() {std::deque<int> d;d.push_back(1); // [1]d.push_front(2); // [2, 1]d.push_back(3); // [2, 1, 3]for (auto it = d.begin(); it != d.end(); ++it) {std::cout << *it << " ";}// 输出: 2 1 3d.pop_front(); // [1, 3]d.pop_back(); // [1]std::cout << "\nSize: " << d.size() << std::endl;// 输出: Size: 1return 0;
}

#include <iostream>
#include <deque>
using namespace std;int main(){deque<char> myDeque;for(char ch='a'; ch<='z'; ++ch){myDeque.push_front(ch);}while (!myDeque.empty()){cout<<myDeque.front()<<" ";myDeque.pop_front();}}

Container adapter 容器适配器

TL 提供了三个容器适配器：queue、priority_queue、stack。这些适配器都
是包装了 vector、list、deque 中某个顺序容器的包装器。注意：适配器没有提供迭
代器，也不能同时插入或删除多个元素。

stack

#include <iostream>
#include <stack>
using namespace std;
int main()
{stack<char> si;cout<<si.size()<<endl;for(int i='a'; i<='z'; i++){si.push(i);}cout<<si.size()<<endl;while(!si.empty()){cout<<si.top()<<" ";si.pop();}cout<<endl<<si.size()<<endl;return 0;
}

queue

#include <iostream>
#include <queue>
using namespace std;
int main()
{queue<char> q;for(char ch='a'; ch<='z'; ch++){q.push(ch);}while(!q.empty()){cout<<q.front()<<" ";q.pop();}return 0;
}

priority Queue 优先级队列

优先级队列（Priority Queue）是一种抽象数据类型，其中的元素按照优先级进行排序。

优先级高的元素先出队列。

优先级队列在许多应用中都非常有用，例如任务调度、Dijkstra算法等。

priority_queue 是一个容器适配器，默认使用 vector 作为底层容器，

并使用 less 作为比较函数，这意味着默认情况下，元素按从大到小的顺序排列（即最大的元素优先级最高）。

声明及头文件

namespace std {template <typename T,typename Container = vector<T>,typename Compare = less<typename Container::value_type>>class priority_queue;
}

#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;// 定义一个结构体 Node，表示队列中的元素
struct Node
{Node(int nri, char *pszName) // 构造函数，初始化 Node 对象{priority = nri; // 初始化优先级strcpy(szName, pszName); // 复制名字到 szName 字符数组}char szName[20]; // 存储名字的字符数组，最多20个字符int priority; // 存储优先级的整数
};// 定义一个比较类 NodeCmp，用于优先队列的比较
class NodeCmp
{
public:bool operator()(const Node &na, const Node &nb) // 重载()运算符，定义比较规则{if (na.priority != nb.priority) // 如果优先级不同return na.priority > nb.priority; // 优先级小的在前elsereturn strcmp(na.szName, nb.szName) < 0; // 如果优先级相同，按名字字典序排序}
};// 定义一个函数 PrintfNode，用于打印 Node 对象的信息
void PrintfNode(const Node &na)
{printf("%s %d\n", na.szName, na.priority); // 打印名字和优先级
}int main()
{// 定义一个优先队列 a，使用 Node 类型，底层容器为 vector，比较器为 NodeCmppriority_queue<Node, vector<Node>, NodeCmp> a;// 向队列中添加5个元素a.push(Node(5, "abc"));a.push(Node(3, "bac"));a.push(Node(1, "cba"));a.push(Node(5, "aaa"));// 队头的2个元素出队并打印PrintfNode(a.top()); // 打印队头元素a.pop(); // 移除队头元素PrintfNode(a.top()); // 打印新的队头元素a.pop(); // 移除新的队头元素printf("--------------------\n"); // 打印分隔线// 再向队列中添加3个元素a.push(Node(2, "bbb"));a.push(Node(2, "ccc"));a.push(Node(3, "aaa"));// 所有元素依次出队并打印while (!a.empty()) // 当队列不为空时{PrintfNode(a.top()); // 打印队头元素a.pop(); // 移除队头元素}return 0; // 返回0，表示程序正常结束
}