珠海北京网站建设,廊坊外贸网站建设,惠州定制网站制作推荐,做程序的软件目录 栈
栈#xff08;stack#xff09;的声明#xff1a;
push()#xff1a; 将元素推入栈顶
pop()#xff1a; 弹出栈顶元素
top()#xff1a; 访问栈顶元素#xff0c;但不弹出
empty()#xff1a; 检查栈是否为空
size()#xff1a; 返回栈中元素的数量
…目录 栈
栈stack的声明
push() 将元素推入栈顶
pop() 弹出栈顶元素
top() 访问栈顶元素但不弹出
empty() 检查栈是否为空
size() 返回栈中元素的数量
emplace() 在栈顶构造一个元素 和 ! 用于比较两个栈是否相等或不相等
队列
队列queue的声明
push() 将元素推入队列尾部
pop() 从队列头部弹出元素
front() 访问队列头部元素
back() 访问队列尾部元素
empty() 检查队列是否为空
总结 栈
栈stack的声明
#include stack// 声明一个整数类型的栈
std::stackint myStack;// 在栈中压入元素
myStack.push(10);
myStack.push(20);// 弹出栈顶元素
myStack.pop();// 访问栈顶元素
int topElement myStack.top();push() 将元素推入栈顶
#include stackstd::stackint 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::stackint stackA;
std::stackint stackB;// ...if (stackA stackB) {// 栈A和栈B相等
}if (stackA ! stackB) {// 栈A和栈B不相等
}妙用
逆波兰表达式计算 使用栈来计算逆波兰表达式。运算符遇到时弹出栈顶的操作数进行计算并将结果重新压入栈。
// 逆波兰表达式3 4 5 *
std::stackint 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::stackchar 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::queueint myQueue;// 在队列尾部插入元素
myQueue.push(30);
myQueue.push(40);// 从队列头部弹出元素
myQueue.pop();// 访问队列头部元素
int frontElement myQueue.front();push() 将元素推入队列尾部
#include queuestd::queueint 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::queueNode* 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 iostreamstd::queuestd::functionvoid() taskQueue;
std::mutex taskQueueMutex;void workerThread() {while (true) {std::functionvoid() task;{std::lock_guardstd::mutex lock(taskQueueMutex);if (!taskQueue.empty()) {task taskQueue.front();taskQueue.pop();}}if (task) {task();} else {// Sleep or yield to avoid busy-waitingstd::this_thread::yield();}}
}缓存管理 使用队列来管理缓存中的数据确保最先进入缓存的数据最先被替换。
#include queue
#include iostreamstd::queueint cache;void addToCache(int data) {cache.push(data);// 如果缓存大小超过限制移除队首元素if (cache.size() MAX_CACHE_SIZE) {cache.pop();}
}打印任务队列 模拟打印任务的队列确保先提交的打印任务先得到执行。 #include queue
#include iostreamstd::queuestd::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-OutLIFO和先进先出First-In-First-OutFIFO的原则组织数据。在面试中它们常被用于解决各种问题。
