// Source : https://leetcode.com/problems/implement-queue-using-stacks/description/
// Author : Tianming Cao
// Date : 2018-02-02
/**********************************************************************************
* 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.
*
* Notes:
* You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, 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).
*
**********************************************************************************/
package myQueue;
import java.util.Stack;
/**
* This problem is a sibling of problem 225(https://leetcode.com/problems/implement-stack-using-queues/description/)
* The solution is:
* 1. stack1 is always in charge of push operation
* 2. stack2 is always in charge of peek and pop operation
* 3. if we want to do peek or pop operation, but stack2 is empty,
* we should first pop all the elements from stack1 and push them into stack2 in turn.
* Give a Example:
*
* First, push numbers "1,2,3,4,5" to stack1, then stack1's structure is:
*
* |5|
* |4|
* |3|
* |2|
* |1|
*
* Second, if we want to get the front element "1",we should pop all the elements of stack1 and push them into stack2,
* after this, stack1 is empty, and stack2's structrue is:
*
* |1|
* |2|
* |3|
* |4|
* |5|
*
* So we can get stack2's top element "1" as the front element of queue.
*
* Next, if we want to push "6" to the back of queue, we should push "6" into stack1 as before, so stack1's structure is:
*
* |6|
*
* Finally, if we want to do pop operation twice ,we should remove the top element of stack2 twice, so stack2's structure is:
*
* |3|
* |4|
* |5|
*
* as expect, the removed element is "1" and "2".
*/
public class MyQueue {
public Stack stack1;
public Stack stack2;
public int size;
public MyQueue() {
stack1 = new Stack();
stack2 = new Stack();
size = 0;
}
public void push(int x) {
stack1.push(x);
size++;
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
int value = stack2.pop();
size--;
return value;
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
int value = stack2.peek();
return value;
}
public boolean empty() {
return size == 0 ? true : false;
}
}