How do I convert a Queue into the Stack?

Technology CommunityCategory: QueuesHow do I convert a Queue into the Stack?
VietMX Staff asked 3 years ago

If you have an ADT Queue with only push_front() and pop_back() as its interface, there is no way to use it as a stack.

A queue is normally a FIFO container, while a stack is LIFO. This means that you cannot just copy the data in sequential order from your queue to your stack, since that will make the elements appear in the “wrong” order. If you merely want to copy the data from the queue onto a stack, then you need to reverse the data first, which is impossible without allocating memory for all the elements in the queue, if your queue has only that interface mentioned above. There is no good way (performance wise) to reverse a queue. A queue is a one-way container, internally an element only has to know about the next element in line, not about the previous one. This means that you cannot iterate through the queue starting at the back, and that iteration always is O(n).

If you have access to the internals of the queue, then its a trivial question, you can reverse the data in place.