目录
栈
栈（stack）的声明：
#include <stack>
// 声明一个整数类型的栈
std::stack<int> myStack;
// 在栈中压入元素
myStack.push(10);
myStack.push(20);
// 弹出栈顶元素
myStack.pop();
// 访问栈顶元素
int topElement = myStack.top();
push()： 将元素推入栈顶
#include <stack>
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
pop()： 弹出栈顶元素
myStack.pop();
top()： 访问栈顶元素，但不弹出
int topElement = myStack.top();
empty()： 检查栈是否为空
if (myStack.empty()) {
// 栈为空
}
size()： 返回栈中元素的数量
size_t stackSize = myStack.size();
emplace()： 在栈顶构造一个元素
myStack.emplace(30);
== 和 !=： 用于比较两个栈是否相等或不相等
std::stack<int> stackA;
std::stack<int> stackB;
// ...
if (stackA == stackB) {
// 栈A和栈B相等
}
if (stackA != stackB) {
// 栈A和栈B不相等
}
妙用
逆波兰表达式计算： 使用栈来计算逆波兰表达式。运算符遇到时，弹出栈顶的操作数进行计算，并将结果重新压入栈。
// 逆波兰表达式：3 4 + 5 *
std::stack<int> st;
st.push(3);
st.push(4);
st.push(st.top() + 5); // 3 + 4
st.pop();
int result = st.top() * 5; // (3 + 4) * 5
括号匹配检查： 使用栈来检查表达式中的括号是否匹配。遍历表达式，遇到左括号压入栈，遇到右括号时检查栈顶是否是对应的左括号。
std::stack<char> st;
std::string expression = "((a + b) * (c - d))";
for (char c : expression) {
if (c == '(') {
st.push(c);
} else if (c == ')') {
if (st.empty() || st.top() != '(') {
// 括号不匹配
break;
}
st.pop();
}
}
bool isBalanced = st.empty();
函数调用堆栈： 编程语言中的函数调用使用堆栈来保存局部变量和返回地址。当函数调用时，创建一个新的栈帧，函数执行完毕后，将栈帧弹出。
void func1() {
int x = 10;
// ...
}
void func2() {
int y = 20;
// ...
}
int main() {
func1();
func2();
return 0;
}
队列
队列（queue）的声明：
#include <queue>
// 声明一个整数类型的队列
std::queue<int> myQueue;
// 在队列尾部插入元素
myQueue.push(30);
myQueue.push(40);
// 从队列头部弹出元素
myQueue.pop();
// 访问队列头部元素
int frontElement = myQueue.front();
push()： 将元素推入队列尾部
#include <queue>
std::queue<int> myQueue;
myQueue.push(10);
myQueue.push(20);
pop()： 从队列头部弹出元素
myQueue.pop();
front()： 访问队列头部元素
int frontElement = myQueue.front();
back()： 访问队列尾部元素
int backElement = myQueue.back();
empty()： 检查队列是否为空
if (myQueue.empty()) {
// 队列为空
}
队列妙用
广度优先搜索（BFS）： 在图或树的遍历中，使用队列来实现广度优先搜索，确保按照层次遍历节点。
void BFS(Node* root) {
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
// 处理当前节点
// ...
// 将当前节点的邻居节点入队
for (Node* neighbor : current->neighbors) {
q.push(neighbor);
}
// 出队
q.pop();
}
}
任务调度： 在操作系统或并发编程中，使用队列来管理任务队列，确保按照先进先出的原则执行任务。
#include <queue>
#include <thread>
#include <iostream>
std::queue<std::function<void()>> taskQueue;
std::mutex taskQueueMutex;
void workerThread() {
while (true) {
std::function<void()> task;
{
std::lock_guard<std::mutex> lock(taskQueueMutex);
if (!taskQueue.empty()) {
task = taskQueue.front();
taskQueue.pop();
}
}
if (task) {
task();
} else {
// Sleep or yield to avoid busy-waiting
std::this_thread::yield();
}
}
}
缓存管理： 使用队列来管理缓存中的数据，确保最先进入缓存的数据最先被替换。
#include <queue>
#include <iostream>
std::queue<int> cache;
void addToCache(int data) {
cache.push(data);
// 如果缓存大小超过限制，移除队首元素
if (cache.size() > MAX_CACHE_SIZE) {
cache.pop();
}
}
打印任务队列： 模拟打印任务的队列，确保先提交的打印任务先得到执行。
#include <queue>
#include <iostream>
std::queue<std::string> printQueue;
void submitPrintJob(const std::string& document) {
printQueue.push(document);
}
void printNextJob() {
if (!printQueue.empty()) {
std::string document = printQueue.front();
std::cout << "Printing: " << document << std::endl;
printQueue.pop();
}
}
总结
栈（Stack）和队列（Queue）是两种基本的数据结构，分别以后进先出（Last-In-First-Out，LIFO）和先进先出（First-In-First-Out，FIFO）的原则组织数据。在面试中，它们常被用于解决各种问题。
