0

Also, you can't use pointers

This question is an interview question and sounds confusing to me as stack ADT is given and operations on queue are asked...

Anubha
  • 1,345
  • 6
  • 23
  • 35
  • See [this question](http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks?rq=1) – Casey Jul 13 '12 at 11:29

1 Answers1

0

In a queue enqueuing always insert the data at the riht-most filled position, in a stack also the data is inserted at the last(top). So, emulating enqueuing operation on a stack is not difficult. One push() operation will suffice. The problem is with the dequeuing operation. One way to emulate dequeue is to use two instances of the stack and on dequeue request empty stack 1 into stack 2 and then pop from stack 2 then restore stack 1 with stack2.

Time complexity for enqueue operaion is O(1)(same as for a queue) but for dequeue operaion the time complexity will be O(n) where n is the number of items in the stack which is greater than O(1) of queue.

karn
  • 5,963
  • 3
  • 22
  • 29