算法训练营第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和q2。push操作：push进q1。pop操作：将q1中除最后一个元素外都push进q2并pop，然后pop掉最后一个元素，再将q2赋值给q1，最后清空q2。

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();    }};