Implementing stack with 2 queues

Problem statement

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


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

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_SIZEdef push()
if len(queue1) >= n:
print 'Stack Overflow'
#enqueue in queue1
def pop()
if len(queue1) == 0:
print 'Stack Underflow'
# while size of queue1 is bigger than 1, dequeued all items but last from queue1 into queue2
# dequeue and return the last item of queue1, then switch the names of queue1 and queue2


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