# LeetCode – Implement Queue using Stacks

### 题目：

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

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

### 解题：

本地使用stack实现一个queue的功能， queue特点是先进先出， stack的特点是先进后出

1.  创建一个辅助栈tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素取出放入input，其他三个操作也就直接调用栈的操作即可，参见代码如下：

### 实现：

class MyQueue {
private:
stack<int> input,output;
public:
/** Initialize your data structure here. */
MyQueue() {

}
/** Push element x to the back of queue. */
void push(int x) {
stack<int> tmp;
while (!input.empty()){
tmp.push(input.top());
input.pop();
}
input.push(x);
while(!tmp.empty()){
input.push(tmp.top());
tmp.pop();
}
}

/** Removes the element from in front of queue and returns that element. */
int pop() {

int val;
val = input.top();
input.pop();
return val;
}

/** Get the front element. */
int peek() {
return input.top();

}

/** Returns whether the queue is empty. */
bool empty() {
return input.empty();

}

### 解题：

2 .入栈不处理， 出栈的时候，通过临时栈进行转换

class MyQueue {
private:
stack<int> input,output;
public:
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
input.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
peek();
int val;
val = output.top();
output.pop();
return val;
}

/** Get the front element. */
int peek() {
if (output.empty()) {
while(!input.empty()) {
output.push(input.top());
input.pop();
}
}

return output.top();

}

/** Returns whether the queue is empty. */
bool empty() {
return input.empty() && output.empty();

}
}