stack and queues

[abhinav priyadarshi]

how can be create a stack using two queues?

[srbakshi]

I think you can implement a stack using just one queue. You can use the enqueue/dequeue functions of the queue to implement the push/pop functions of the stack.

[donbock]

@srbakshi:

Typically, queue access functions put items in one end of a circular list and pull them out from the other end.

Typically, stack access functions put items in one end of a circular list and pull them out from the same end.

Do the enqueue/dequeue functions of the queue allow you to specify which end the circular list is being used?

[srbakshi]

Hi Donbock,

My thinking was as follows:

We have to implement the Push and Pop functionality of a stack using the Enqueue and Dequeue functionality of a queue. Here's what I thought could be done:

1. Push:

Will be same as an enqueue operation on a queue.

2. Pop:

Dequeue n-1 (n being the total number of items in the queue) number of items from the queue and enqueue them in the same queue. Then dequeue once more to get the last item.

Eg: Queue has 4-3-2-1 (Pop should fetch us 1 in this eg)
We dequeue 3 (size of queue - 1) items and enqueue them in the same queue:

3-2-1-4
2-1-4-3
1-4-3-2

Now dequeue once more to get the last item, i.e. 1.

:D

[hype261]

Srbakshi even though this would work it is very inefficient to do so. Your stack pop has a O(n) complexity compared to a O(1) for a regular stack.

If I had to created a stack using two queues, that had common data using the circular list method, I would just have one queue point to the beginning of the list and the second queue point at the end.

When I pushed some data I would call enqueue on the second queue and when I poped a data member I would call dequeue on the first queue. You would have to keep the pointers right for both queues during the enqueue or dequeue operation, but it should be do able.

[srbakshi]

@abhinav
Although my approach works you might want to look at hype261's answer as well since for a stack having a large number of items, my approach would be very inefficient. :)