算法训练营第10天-栈和队列01|232.用栈实现队列，225.用队列实现栈
���录
相关知识
1. STL
2. 容器（参考C++STL【容器】详解 （全站最详细） - 知乎）
3. 栈和队列
232.用栈实现队列
225.用队列实现栈
相关知识
1. STL
标准模板库 STL（Standard Template Library）， C++ 标准库的一部分。STL 使用模板（Template）实现了各种常用的数据结构及算法，封装了多种容器。编程使用STL可以直接使用它提供的数据结构及算法，而不用实现具体细节，非常方便。
六大组件：容器（Containers），分配器（Allocators），算法（Algorithm），迭代器（Iterators），适配器（Adapters），仿函数（Functors）
STL使用方法参考 C++ STL总结 | 行码棋
2. 容器（参考C++STL【容器】详解 （全站最详细） - 知乎）
顺序性容器
| 容器 | 简介说明 |
|---|---|
| vector | 可变大小数组。相当于数组，可动态构建，支持随机访问，无头插和尾插，仅支持inset插入，除尾部外的元素删除比较麻烦。但使用最为广泛 |
| deque | 双端队列。支持头插、删，尾插、删，随机访问较vector容器来说慢,但对于首尾的数据操作比较方便 |
| list | 双向循环链表。使用起来很高效，对于任意位置的插入和删除都很快，在操作过后，以后指针、迭代器、引用都不会失效 |
| forward_list | 单向链表。只支持单向访问，在链表的任何位置进行插入/删除操作都非常快 |
| array | 固定数组。vector的底层即为array数组，它保存了一个以严格顺序排列的特定数量的元素 |
匹配式容器
| 容器 | 简介说明 |
|---|---|
| set/mutliset | 集合/多重集合。对于set，在使用insert插入元素时，已插入过的元素不可重复插入，这正好符合了集合的互异性，在插入完成显示后，会默认按照升序进行排序，对于multiset，可插入多个重复的元素 |
| map/mutlimap | 映射/多重映射。二者均为二元关联容器（在构造时需要写两个参数类型，前者对key值，后者对应value值），因为有两个参数，因此在插入元素的时候需要配合对组pair进行插入，具体见深入详解 |
容器适配器
| 容器 | 简介说明 |
|---|---|
| stack | 堆栈。其原理是先进后出（FILO），其底层容器可以是任何标准的容器适配器，默认为deque双端队列 |
| queue | 队列。其原理是先进先出（FIFO），只有队头和队尾可以被访问，故不可有遍历行为，默认也为deque双端队列 |
| pirority_queue | 优先队列。它的第一个元素总是它所包含的元素中优先级最高的，就像数据结构里的堆，会默认形成大堆，还可以使用仿函数来控制生成大根堆还是生成小根堆，若没定义，默认使用vector容器 |
3. 栈和队列
广义：栈是先入后出的数据结构，队列是先入先出的数据结构
狭义：栈和队列是STL（C++标准库）里面的两个数据结构。
在STL中，栈和队列不提供迭代器遍历所有数据；它们不是容器，而是容器适配器，可用deque, vector, list等容器作为底层结构。
232.用栈实现队列
题目 232. 用栈实现队列
文档 代码随想录
状态：没想到可以使用两个栈的思路；提供思路后可以独立完成
1.思路
使用两个栈，一个输入栈一个输出栈。队列的push操作：push入输入栈。pop操作：若输出栈为空，则将输入栈中的元素依次push进输出栈，最后输出栈pop；若输出栈不为空，则直接输出栈pop。top操作：与pop相似，但不执行栈的pop。当两个栈都为空时，队列为空。
2.代码
class MyQueue {
public:
stack staIn;
stack staOut;
MyQueue() {
}
void push(int x) {
staIn.push(x);
}
int pop() {
if(staOut.empty()){
while(!staIn.empty()){
staOut.push(staIn.top());
staIn.pop();
}
}
int result = staOut.top();
staOut.pop();
return result;
}
int peek() {
if(!staOut.empty()) return staOut.top();
else{
while(!staIn.empty()){
staOut.push(staIn.top());
staIn.pop();
}
return staOut.top();
}
}
bool empty() {
if(staIn.empty()&&staOut.empty()) return true;
else return false;
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
225.用队列实现栈
题目 225. 用队列实现栈
文档 代码随想录
状态 独立完成
1. 思路
使用两个队列，q1和qpush操作：push进qpop操作：将q1中除最后一个元素外都push进q2并pop，然后pop掉最后一个元素，再将q2赋值给q1，最后清空q
2.代码
class MyStack {
public:
queue que1;
queue 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();
}
};
3.优化思路：只用一个队列，pop操作只需要把除最后一个元素外的其他元素依次放到队尾，最后pop掉那个元素即可
class MyStack {
public:
queue que;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que.size();
size--;
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
/** Get the top element. */
int top() {
return que.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que.empty();
}
};