Queue is First-in, first out

stack is First-in, last-out

so to implement queue, we can have two stacks,which is (first-in, last-out) and (last-in, First-out).

s1 is for push operation

s2 is for pop and peek operation

class MyQueue {

private:

stack<int> s1;

stack<int> s2;

public:

/** Initialize your data structure here. */

MyQueue() {

```
}
/** Push element x to the back of queue. */
void push(int x) {
while(!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
s1.push(x);
return;
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
int tmp = s2.top();
s2.pop();
return tmp;
}
/** Get the front element. */
int peek() {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty() && s2.empty();
}
```

};

/**

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

*/

Optimization

actually we don't need to transfer bunch of elements between s1 and s2. Only when s2 is empty, we start the transfer

push: O(1)

pop: O(1) in average

class MyQueue {

private:

stack<int> s1;

stack<int> s2;

public:

/** Initialize your data structure here. */

MyQueue() {

```
}
/** Push element x to the back of queue. */
void push(int x) {
s1.push(x);
return;
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int tmp = s2.top();
s2.pop();
return tmp;
}
/** Get the front element. */
int peek() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty() && s2.empty();
}
```

};

/**

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

*/