Implementing stack with two queues

Problem statment

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

Solution

There can be two ways you can solve the above problem.

• Option A: The stack – efficient when pushing an item
• Option B: The stack – efficient when popping an item

In this post lets us discuss the an implementation of option A.

Exception handling: We have a ‘Stack Overflow’ exception – which can occur @ push operation in runtime to handle that case. Similarly we have a ‘Stack Underflow’ exception for pop operation. The checks depends on the size of the DataStructure(no.of items that can be stored). In this case it will be size of the queue. Let us say it as ‘n’.

Pseudo code: (Option A):

n = QUEUE_SIZE

def push()
  if len(queue1) >= n:
    print 'Stack Overflow'
    return
  else:
    #enqueue in queue1


def pop()
  if len(queue1) == 0:
    print 'Stack Underflow'
    return

# while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
# dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Conclusion

Here, at any point of time this stack data structure (implemented with queues) will have max of ’n’ items and all push operations are O(1). It also throws ‘Stack Overflow’ and ‘Stack Underflow’ exceptions

Read Similar Blogs: