Implementing stack with two queues and a finite queue size

Question

Following up on this question: Implement Stack using Two Queues

I'm looking to implement Version A (efficient push) of the answer however I also need to be considerate of the queue size i.e. I cannot 'enqueue forever' but at a certain point the queue will run out of space.

I need to make sure all push operations are done with constant time complexity.

How would I go on to implement this? Copying the queue once its full will obviously result in a complexity of O(n).

I could create a new empty queue and start pushing there, however it needs to represent a stack and at a certain point at pop operations, it will reach the end of the new queue and won't know the rest of the items are in the old queue.

If you only copy the queue when it is full, then the cost of the copy *amortized over all of the pushes* is pretty close to O(1) per push. — Scott Hunter, Jan 04 '18 at 19:11
Why would it be possible to add a queue but not a value to an existing queue when you run out of space? Why would running out of space not just be an indication that your implemented stack runs out of space? What are your limitations? — trincot, Jan 04 '18 at 21:31

score 1 · Accepted Answer · answered Jan 05 '18 at 05:46

Agree on fixing upperlimit on no.of items to be enqueued in queue. The same thing is applicable for Stack as well. 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 with exceptions looks like below:

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

Here, At any point of time your Stack DataStructure (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

Hope it helps!

Implementing stack with two queues and a finite queue size

1 Answers1