Java Program to Implement Stack using Two Queues

Intuition

Stack is LIFO (last in – first out) data structure, in which elements are added and removed from the same end, called top. In general stack is implemented using array or linked list, but in the current article we will review a different approach for implementing stack using queues. In contrast queue is FIFO (first in – first out) data structure, in which elements are added only from the one side – rear and removed from the other – front. In order to implement stack using queues, we need to maintain two queues q1 and q2. Also we will keep top stack element in a constant memory.

Algorithm

Push

The new element is always added to the rear of queue q1 and it is kept as top stack element

Push an element in stack

Figure 1. Push an element in stack

Java

Complexity Analysis

    • Time complexity : O(1)O(1). Queue is implemented as linked list and add operation has O(1)O(1) time complexity.

 

    • Space complexity : O(1)O(1)

 

Pop We need to remove the element from the top of the stack. This is the last inserted element in q1. Because queue is FIFO (first in – first out) data structure, the last inserted element could be removed only after all elements, except it, have been removed. For this reason we need to maintain additional queue q2, which will serve as a temporary storage to enqueue the removed elements from q1. The last inserted element in q2 is kept as top. Then the algorithm removes the last element in q1. We swap q1 with q2 to avoid copying all elements from q2 to q1.

Pop an element from stack

 

Figure 2. Pop an element from stack

Java

Complexity Analysis

  • Time complexity : O(n)O(n). The algorithm dequeues n elements from q1 and enqueues n – 1n1 elements to q2, where nn is the stack size. This gives 2n – 12n1 operations.
  • Space complexity : O(1)O(1).

Reverse a stack using recursion

Reverse a stack using recursion

Design a stack that supports getMin() in O(1) time and O(1) extra space

An approach that uses O(1) time and O(n) extra space is discussed here.

In this article, a new approach is discussed that supports minimum with O(1) extra space. We define a variableminEle that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when minimum element is removed. To handle this, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack. Below are detailed steps and explanation of working.

Push(x) : Inserts x at the top of stack.

  • If stack is empty, insert x into the stack and make minEle equal to x.
  • If stack is not empty, compare x with minEle. Two cases arise:
    • If x is greater than or equal to minEle, simply insert x.
    • If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x. For example, let previous minEle was 3. Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack.

Pop() : Removes an element from top of stack.

  • Remove element from top. Let the removed element be y. Two cases arise:
    • If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
    • If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y). This is where we retrieve previous minimum from current minimum and its value in stack. For example, let the element to be removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3.

Important Points:

  • Stack doesn’t hold actual value of an element if it is minimum so far.
  • Actual minimum element is always stored in minEle

Illustration

Push(x)
stack_insert

  • Number to be Inserted: 3, Stack is empty, so insert 3 into stack and minEle = 3.
  • Number to be Inserted: 5, Stack is not empty, 5> minEle, insert 5 into stack and minEle = 3.
  • Number to be Inserted: 2, Stack is not empty, 2< minEle, insert (2*2-3 = 1) into stack and minEle = 2.
  • Number to be Inserted: 1, Stack is not empty, 1< minEle, insert (2*1-2 = 0) into stack and minEle = 1.
  • Number to be Inserted: 1, Stack is not empty, 1 = minEle, insert 1 into stack and minEle = 1.
  • Number to be Inserted: -1, Stack is not empty, -1 < minEle, insert (2*-1 – 1 = -3) into stack and minEle = -1.

Pop()
stack_removal

  • Initially the minimum element minEle in the stack is -1.
  • Number removed: -3, Since -3 is less than the minimum element the original number being removed is minEle which is -1, and the new minEle = 2*-1 – (-3) = 1
  • Number removed: 1, 1 == minEle, so number removed is 1 and minEle is still equal to 1.
  • Number removed: 0, 0< minEle, original number is minEle which is 1 and new minEle = 2*1 – 0 = 2.
  • Number removed: 1, 1< minEle, original number is minEle which is 2 and new minEle = 2*2 – 1 = 3.
  • Number removed: 5, 5> minEle, original number is 5 and minEle is still 3

Implementation:

 

Result: