package Others;

import java.util.Stack;

/**
 * This implements Queue using two Stacks.
 *
 * <p>Big O Runtime: insert(): O(1) remove(): O(1) amortized isEmpty(): O(1)
 *
 * <p>A queue data structure functions the same as a real world queue. The elements that are added
 * first are the first to be removed. New elements are added to the back/rear of the queue.
 *
 * @author sahilb2 (https://www.github.com/sahilb2)
 */
class QueueWithStack {

 // Stack to keep track of elements inserted into the queue
 private Stack inStack;
 // Stack to keep track of elements to be removed next in queue
 private Stack outStack;

 /** Constructor */
 public QueueWithStack() {
 this.inStack = new Stack();
 this.outStack = new Stack();
 }

 /**
 * Inserts an element at the rear of the queue
 *
 * @param x element to be added
 */
 public void insert(Object x) {
 // Insert element into inStack
 this.inStack.push(x);
 }

 /**
 * Remove an element from the front of the queue
 *
 * @return the new front of the queue
 */
 public Object remove() {
 if (this.outStack.isEmpty()) {
 // Move all elements from inStack to outStack (preserving the order)
 while (!this.inStack.isEmpty()) {
 this.outStack.push(this.inStack.pop());
 }
 }
 return this.outStack.pop();
 }

 /**
 * Peek at the element from the front of the queue
 *
 * @return the front element of the queue
 */
 public Object peekFront() {
 if (this.outStack.isEmpty()) {
 // Move all elements from inStack to outStack (preserving the order)
 while (!this.inStack.isEmpty()) {
 this.outStack.push(this.inStack.pop());
 }
 }
 return this.outStack.peek();
 }

 /**
 * Peek at the element from the back of the queue
 *
 * @return the back element of the queue
 */
 public Object peekBack() {
 return this.inStack.peek();
 }

 /**
 * Returns true if the queue is empty
 *
 * @return true if the queue is empty
 */
 public boolean isEmpty() {
 return (this.inStack.isEmpty() && this.outStack.isEmpty());
 }
}

/**
 * This class is the example for the Queue class
 *
 * @author sahilb2 (https://www.github.com/sahilb2)
 */
public class QueueUsingTwoStacks {

 /**
 * Main method
 *
 * @param args Command line arguments
 */
 public static void main(String args[]) {
 QueueWithStack myQueue = new QueueWithStack();
 myQueue.insert(1);
 System.out.println(myQueue.peekBack()); // Will print 1
 // instack: [(top) 1]
 // outStack: []
 myQueue.insert(2);
 System.out.println(myQueue.peekBack()); // Will print 2
 // instack: [(top) 2, 1]
 // outStack: []
 myQueue.insert(3);
 System.out.println(myQueue.peekBack()); // Will print 3
 // instack: [(top) 3, 2, 1]
 // outStack: []
 myQueue.insert(4);
 System.out.println(myQueue.peekBack()); // Will print 4
 // instack: [(top) 4, 3, 2, 1]
 // outStack: []

 System.out.println(myQueue.isEmpty()); // Will print false

 System.out.println(myQueue.remove()); // Will print 1
 System.out.println(myQueue.peekBack()); // Will print NULL
 // instack: []
 // outStack: [(top) 2, 3, 4]

 myQueue.insert(5);
 System.out.println(myQueue.peekFront()); // Will print 2
 // instack: [(top) 5]
 // outStack: [(top) 2, 3, 4]

 myQueue.remove();
 System.out.println(myQueue.peekFront()); // Will print 3
 // instack: [(top) 5]
 // outStack: [(top) 3, 4]
 myQueue.remove();
 System.out.println(myQueue.peekFront()); // Will print 4
 // instack: [(top) 5]
 // outStack: [(top) 4]
 myQueue.remove();
 // instack: [(top) 5]
 // outStack: []
 System.out.println(myQueue.peekFront()); // Will print 5
 // instack: []
 // outStack: [(top) 5]
 myQueue.remove();
 // instack: []
 // outStack: []

 System.out.println(myQueue.isEmpty()); // Will print true
 }
}