QueueUsingTwoStacks.java

packagecom.thealgorithms.others;

importjava.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)
 */
classQueueWithStack {

// Stack to keep track of elements inserted into the queue
privateStack<Object> inStack;
// Stack to keep track of elements to be removed next in queue
privateStack<Object> outStack;

/**
 * Constructor
 */
publicQueueWithStack() {
this.inStack = newStack<>();
this.outStack = newStack<>();
 }

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

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

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

/**
 * Peek at the element from the back of the queue
 *
 * @return the back element of the queue
 */
publicObjectpeekBack() {
returnthis.inStack.peek();
 }

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

/**
 * Returns true if the inStack is empty.
 *
 * @return true if the inStack is empty.
 */
publicbooleanisInStackEmpty() {
return (inStack.size() == 0);
 }

/**
 * Returns true if the outStack is empty.
 *
 * @return true if the outStack is empty.
 */
publicbooleanisOutStackEmpty() {
return (outStack.size() == 0);
 }
}

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

/**
 * Main method
 *
 * @param args Command line arguments
 */
publicstaticvoidmain(String[] args) {
QueueWithStackmyQueue = newQueueWithStack();
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.isInStackEmpty()) ? "null" : 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
 }
}