Convert a queue to the stack?
I have a queue with n elements in it and the front is at 0 . I need to create a stack of these numbers with 0 at the top.
It can only be done with EnQueue, DeQueue, Push, and Pop, and constant storage. I dont need an answer so much as an idea of how I could approach this problem.
Please don't answer this for me, but just try to understand I'm new at programming and could just use an idea of what is a way this can be done.
This isnt for homework, I just need some advice on how to proceed. My first idea, reversing the queue and then pushing it did not work. I even tried sketching out other situations with no avail. Then I wondered if dequeueing and pushing them all, then popping and enqueueing them all, then dequeue and push again.
I am still learning fundamental programming concepts. Please be nice! :)
What am I facing?
The biggest problem you are facing is that your two containers aren't directly compatible with each other.
A queue is normally a FIFO1 container, while a stack is LIFO2. 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 (following your description).
Another problem is that 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).
The same problem is with your stack.
The things described earlier put together makes this quite a tedious problem, though there are solutions they aren't always the most straight forward.
Hints on how to solve this issue..
You'll need some sort of intermediate state to store your elements, or could we use the LIFO/FIFO properties of our containers to our advantage?
Below is an implementation which does what you want, if you don't want to know the answer to your question don't hover with your mouse over this gray area.
It will require some additional storage since space for an extra element will be allocated during copying from one container to another.. this is inevitable , though the storage is constant.
Remember that the copy-initialization can be optimized by using rvalue-references and move in C++11.
Can't seem to get syntax highlighting working inside a spoiler..
Sample implementation can be found here.
It takes advantage of the fact that a queue is FIFO and stack LIFO, by copying the data queue to stack, then stack to queue and finally queue to stack again we have effectively reversed the order of elements in a way that will match your description.
footnotes
1. FIFO = First In First Out
2. LIFO = Last In First Out
DeQueue everything from Queue, immediately Pushing each element to Stack. Now Pop everything from Stack, immediately EnQueueing to Queue. What's in Queue now?
Presuming your Queue and Stack hold fixed sized items, the above ahem subroutine certainly only uses constant additional storage: Only storage for 1 item is needed as each item transits from Queue to Stack or vice-versa.
Edit : As you point out, my subroutine reverses the content of the Queue. Having done so, it is fairly simple to drain the Queue into the Stack again to get the desired outcome.
And, as you point out, this requires transferring 3n = O(n) items, where n is the initial size of the Queue. Could you do better? I don't believe so, or at least not significantly. In some sense, without even a counter (which would take O(log n) > O(1) extra storage), the only reasonable thing to do is drain the queue into the stack or vice versa.
上一篇: 队列和堆栈和引用
下一篇: 将队列转换为堆栈？