代码随想录算法训练营day10（栈与队列）：
学习内容：
std::queue 和 std::stack 是 C++ 标准库中提供的队列和栈的容器适配器，它们分别基于队列和栈的概念，提供了一组简单的操作接口。
std::queue
std::queue 是一个先进先出（FIFO）的队列容器适配器。它提供了队列的基本操作，包括入队（push）、出队（pop）、访问队首元素（front）、访问队尾元素（back）等。std::queue 并不直接提供迭代器来访问队列中的元素，因为它是一个队列，不支持随机访问。
以下是 std::queue 的常用操作：
push(val)：将元素 val 入队。
pop()：将队首元素出队。
front()：访问队首元素。
back()：访问队尾元素。
empty()：检查队列是否为空。
size()：返回队列中的元素个数。
std::stack
std::stack 是一个后进先出（LIFO）的栈容器适配器。它提供了栈的基本操作，包括压入（push）、弹出（pop）、访问栈顶元素（top）等。与 std::queue 类似，std::stack 也不直接提供迭代器来访问栈中的元素。
以下是 std::stack 的常用操作：
push(val)：将元素 val 压入栈顶。
pop()：将栈顶元素弹出。
top()：访问栈顶元素。
empty()：检查栈是否为空。
size()：返回栈中的元素个数。
示例用法：
#include <iostream>
#include <queue>
#include <stack>
int main() {
// 使用 std::queue
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty()) {
std::cout << q.front() << " "; // 访问队首元素
q.pop(); // 出队
}
std::cout << std::endl;
// 使用 std::stack
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << " "; // 访问栈顶元素
s.pop(); // 弹出栈顶元素
}
std::cout << std::endl;
return 0;
}
学习产出：
因为队列是双开口，需要两个单开口的栈来模拟：
class MyQueue {
private:
stack<int>stk1;
stack<int>stk2;
public:
MyQueue() {
}
void push(int x) {
stk1.push(x);
}
int pop() {
if(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
int a=stk2.top();
stk2.pop();
return a;
}
int peek() {
if(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
int a=stk2.top();
return a;
}
bool empty() {
if(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
return stk2.empty();
}
};
225
我是用一个队列实现的，具体来说就是对队列排序，按栈一样把后入的放在队首，就可以正常像栈一样操作了。
class MyStack {
public:
queue<int>qin;
MyStack() {
}
void push(int x) {
qin.push(x);
if(!qin.empty()){
for(int i=1;i<qin.size();i++){
qin.push(qin.front());
qin.pop();
}
}
}
int top() {
return qin.front();
}
int pop() {
int a=top();
qin.pop();
return a;
}
bool empty() {
return qin.empty();
}
};
官方使用两个队列
用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
class MyStack {
public:
queue<int> que1;
queue<int> que2; // 辅助队列，用来备份
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que1.size();
size--;
while (size--) { // 将que1 导入que2，但要留下最后一个元素
que2.push(que1.front());
que1.pop();
}
int result = que1.front(); // 留下的最后一个元素就是要返回的值
que1.pop();
que1 = que2; // 再将que2赋值给que1
while (!que2.empty()) { // 清空que2
que2.pop();
}
return result;
}
/** Get the top element. */
int top() {
return que1.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que1.empty();
}
};