leetcode|leetcode232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。
实现MyQueue类：
- void push(int x) 将元素x推到队列的末尾。
- int pop( ) 从队列的开头移除并返回元素。
- int peek( ) 返回队列开头的元素。
- bool empty( ) 如果队列为空，返回true；否则，返回false。
?输入：[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
????[ [ ], [1], [2], [ ], [ ], [ ] ]
?输出：[null, null, null, 1, 1, false]
【leetcode|leetcode232. 用栈实现队列】思路：
思路还是很简单的，既然栈的原则是先进后出（FILO），而队列的原则是先进先出（FIFO），那么我们可以使用两个栈来实现，一个栈专门用于入数据，而另一个栈专门用于出数据。
文章图片
当需要入数据的时候就直接对pushST进行压栈，当需要出数据的时候就直接将数据从popST当中弹出，当需要出数据但popST为空时，则先将pushST当中的数据全部压入popST后，再由popST进行出数据。判断“队列”是否为空，即判断pushST和popST是否同时为空。这样我们就相当于用两个栈实现了一个先进先出的队列了。
代码如下：
class MyQueue {public:
/** Initialize your data structure here. */
MyQueue() {//构造函数无需编写，使用默认构造函数即可
} /** Push element x to the back of queue. */
void push(int x) {_pushST.push(x);
//入数据直接对pushST进行压栈
} /** Removes the element from in front of queue and returns that element. */
int pop() {int front = peek();
//获取popST栈顶元素，即“队头”元素
_popST.pop();
//将popST栈顶元素删除，即删除“队头”元素
return front;
//返回删除的元素
} /** Get the front element. */
int peek() {if (_popST.empty()) //如果popST为空，则先将pushST当中的全部元素压入popST
{while (!_pushST.empty())
{_popST.push(_pushST.top());
_pushST.pop();
}
}
return _popST.top();
//返回popST栈顶元素，即“队头”元素
} /** Returns whether the queue is empty. */
bool empty() {return _pushST.empty() && _popST.empty();
//pushST和popST同时为空，则“队列”为空
}
private:
stack _pushST;
stack _popST;
};
/**
* 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();
*/
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点