C++算法
C++ Stack 和 Queue 数据结构详解
本文介绍了 C++ STL 中的容器适配器，包括栈（Stack）、队列（Queue）和优先队列（Priority Queue）。详细讲解了 deque 双端队列的特性及优缺点。通过代码示例演示了 stack 和 queue 的模拟实现，并深入探讨了仿函数（Functor）的概念与应用。最后结合 LeetCode 经典题目（如最小栈、逆波兰表达式求值等）巩固了数据结构在实际场景中的应用。
本文介绍了 C++ STL 中的容器适配器，包括栈（Stack）、队列（Queue）和优先队列（Priority Queue）。详细讲解了 deque 双端队列的特性及优缺点。通过代码示例演示了 stack 和 queue 的模拟实现，并深入探讨了仿函数（Functor）的概念与应用。最后结合 LeetCode 经典题目（如最小栈、逆波兰表达式求值等）巩固了数据结构在实际场景中的应用。
容器适配器（Container Adapter）是 C++ 标准模板库（STL）中的一种设计模式，专门用于提供一种经过简化和限制的接口，使得不同的容器类型可以表现出类似的行为。容器适配器不会创建新的容器，而是基于已有的容器（如 deque、vector 等）进行包装，以改变或限制其接口，从而提供不同的行为和使用方式。
STL 中常见的容器适配器有以下三种：
栈（Stack）
std::stack 类实现。std::deque，也可以用 std::vector 或 std::list 替换。push、pop 和 top 操作。队列（Queue）
std::queue 类实现。std::deque，也可以使用其他序列容器（如 std::list）。push、pop 和 front、back 等接口。优先级队列（Priority Queue）
std::priority_queue 类实现。std::vector，底层使用堆结构进行元素排序。push、pop 和 top 操作，自动按照优先级排序。deque 或 vector 作为底层容器。总体而言，容器适配器是一种设计模式，通过包装现有容器来提供定制化的数据结构接口，使程序设计更加简单和灵活。
我们通过适配器就能将栈和队列进行模拟实现。
stack.h
#pragma once
#include<vector>
#include<list>
#include<deque>
namespace kai {
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() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
private:
Container _con;
};
}
queue.h
#pragma once
#include<vector>
#include<list>
#include<deque>
namespace kai {
template<class T, class Container = deque<T>>
class queue {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const T& front() const { return _con.front(); }
const T& back() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
private:
Container _con;
};
}
test.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
#include"stack.h"
#include"Queue.h"
using namespace std;
int main() {
kai::stack<int,list<int>>st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
cout << endl;
kai::queue<int, list<int>>q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
return 0;
}
当你在实例化这个模板类时，例如 stack<int, std::vector> myStack;，编译器就会根据传入的模板参数 int 和 std::vector 来推导出具体的 T 和 Container 类型。模板实例化在编译阶段完成，确保类型安全。
deque 叫做双端队列，两端都可以进行插入删除的操作。deque 的核心结构是迭代器进行支撑的，里面只有两个迭代器，start 和 finish。
deque 的技能树点的比较满，啥都会，就可以将 list 和 vector 的技能都带上。vector 是一块连续的空间，list 是一个个小块的空间通过指针进行连接起来的。
deque 的缺陷在哪里呢？
deque 的内存布局并不像 vector 一样是连续的内存块，而是分段的。所以栈和队列的适配容器通常是 deque。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> p(nums.begin(),nums.end());
while(--k) {
p.pop();
}
return p.top();
}
};
默认是大的优先级最高。priority_queue 通常实现为一个堆（heap），可以支持快速插入和删除优先级最高的元素。
关键操作：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> maxQueue;
maxQueue.push(10);
maxQueue.push(30);
maxQueue.push(20);
maxQueue.push(5);
while (!maxQueue.empty()) {
std::cout << maxQueue.top() << " ";
maxQueue.pop();
}
return 0;
}
std::priority_queue<int, std::vector<int>, std::greater<int>> minQueue;
int main() {
priority_queue<int,vector<int>,greater<int>> pq;
pq.push(3);
pq.push(2);
pq.push(1);
pq.push(4);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
#pragma once
#include<vector>
namespace kai {
template <class T>
struct less {
bool operator() (const T& x, const T& y)const { return x < y; }
};
template <class T>
struct greater {
bool operator() (const T& x, const T& y)const { return x > y; }
};
template<class T ,class Container=vector<T>,class Compare=less<T>>
class priority_queue {
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last) :_con(first,last) {
for (int i = (_con.size()-1-1)/2; i >=0; i--) {
AdjustDown(i);
}
}
void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while (child > 0) {
if (com(_con[parent],_con[child])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (parent - 1) / 2;
} else {
break;
}
}
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void AdjustDown(int parent) {
Compare com;
size_t child = parent * 2 + 1;
while (child<_con.size()) {
if (child + 1 < _con.size() && com(_con[child],_con[child + 1] )) {
++child;
}
if (com(_con[parent],_con[child] )) {
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();
AdjustDown(0);
}
bool empty() { return _con.empty(); }
const T& top() { return _con[0]; }
size_t size() { return _con.size(); }
private:
Container _con;
};
}
仿函数（Functor）是一种在 C++ 中使用的技术，它使得对象可以像函数一样被调用。仿函数通常通过重载 operator() 操作符来实现。
在 C++ 中，可以通过重载 operator() 操作符来定义一个仿函数，使得一个对象可以像普通函数一样被调用。
#include <iostream>
class Adder {
public:
int operator()(int a, int b) const { return a + b; }
};
int main() {
Adder add;
int result = add(3, 4);
std::cout << "Result: " << result << std::endl;
return 0;
}
operator()。#include <iostream>
#include <vector>
#include <algorithm>
class MultiplyBy {
int factor;
public:
MultiplyBy(int f) : factor(f) {}
int operator()(int value) const { return value * factor; }
};
int main() {
std::vector<int> values = {1, 2, 3, 4, 5};
std::transform(values.begin(), values.end(), values.begin(), MultiplyBy(3));
for (int value : values) {
std::cout << value << " ";
}
return 0;
}
class MinStack {
public:
MinStack() { }
void push(int val) {
_st.push(val);
if(_minst.empty()||val<=_minst.top()) {
_minst.push(val);
}
}
void pop() {
if(_st.top()==_minst.top()) {
_minst.pop();
}
_st.pop();
}
int top() { return _st.top(); }
int getMin() { return _minst.top(); }
private:
stack<int> _st;
stack<int> _minst;
};
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
size_t pushi=0,popi=0;
stack<int>st;
while(pushi<pushV.size()) {
st.push(pushV[pushi++]);
while(!st.empty()&&popV[popi]==st.top()) {
popi++;
st.pop();
}
}
return st.empty();
}
};
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack <int>s;
for(auto &str:tokens) {
if("+"==str||"-"==str||"*"==str||"/"==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 '/': s.push(left/right); break;
}
} else {
s.push(stoi(str));
}
}
return s.top();
}
};
class MyQueue {
private:
stack<int> stackIn;
stack<int> stackOut;
void move() {
while(!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
public:
MyQueue(){}
void push(int x) { stackIn.push(x); }
int pop() {
if(stackOut.empty()) move();
int result=stackOut.top();
stackOut.pop();
return result;
}
int peek() {
if(stackOut.empty()) move();
return stackOut.top();
}
bool empty() { return stackIn.empty()&&stackOut.empty(); }
};
class MyStack {
private:
queue<int> queue1;
queue<int> queue2;
public:
MyStack() {}
void push(int x) {
queue2.push(x);
while(!queue1.empty()) {
queue2.push(queue1.front());
queue1.pop();
}
swap(queue1,queue2);
}
int pop() {
int topment=queue1.front();
queue1.pop();
return topment;
}
int top() { return queue1.front(); }
bool empty() { return queue1.empty(); }
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online