225. Implement Stack using Queues(Leetcode每日一题-2020.03.01)

本文主要是介绍225. Implement Stack using Queues(Leetcode每日一题-2020.03.01)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.

Notes:

You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Example

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false

Solution

使用两个queue
queue1用于存放数据
queue2用于top和pop操作时暂存数据

class MyStack {
public:/** Initialize your data structure here. */MyStack() {while(!inner_queue1.empty()){inner_queue1.pop();}}/** Push element x onto stack. */void push(int x) {inner_queue1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int queue1_size = inner_queue1.size();while(queue1_size > 1){inner_queue2.push(inner_queue1.front());inner_queue1.pop();--queue1_size;}int ret = inner_queue1.front();inner_queue1.pop();while(!inner_queue2.empty()){inner_queue1.push(inner_queue2.front());inner_queue2.pop();}return ret;}/** Get the top element. */int top() {int queue1_size = inner_queue1.size();while(queue1_size > 1){inner_queue2.push(inner_queue1.front());inner_queue1.pop();--queue1_size;}int ret = inner_queue1.front();inner_queue1.pop();while(!inner_queue2.empty()){inner_queue1.push(inner_queue2.front());inner_queue2.pop();}inner_queue1.push(ret);return ret;}/** Returns whether the stack is empty. */bool empty() {return inner_queue1.empty();}queue<int> inner_queue1;queue<int> inner_queue2;
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/