From Queue To Stack
Computer Science
Level
3
1
2
3
This is not possible
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
A single Queue can be used as a Rolodex , by taking items out one by one and immediately putting them back in again. This allows you to cycle through all the elements, using one extra variable (of the item's type). Furthermore, it is necessary to know the number of items in the queue (either because it is a query offered by the queue data type, or by maintaining it in a separate integer variable). That way, you can cycle to any desired item in the queue for removal.
To implement a stack, its push operation would correspond to putting an item (at the end) in the queue, and its pop operation would correspond to rotating the queue until the last item put is at the front, and then taking that item out.
It would not be a very efficient implementation, because pop involves a number of operations proportional the the stack's size. Note that with one Priority Queue you could create a reasonably efficient stack.