Here are two solutions for using stacks to emulate a queue. The first always keeps one or both stacks empty, shifts the set of values back and forth as the caller switches between enqueuing and dequeueing. The second maintains an input stack and an output stack. All enqueued data goes directly onto the input stack. When dequeue is called, if the output stack has anything on it, it takes the topmost value, otherwise it transfers the entire input stack into the output stack.<\/p>\n
The latter implementation is more efficient — transfer between the two stacks occurs only when dequeue is called and<\/b> the output stack is already empty — as well as more compact and readable.<\/p>\nStack-Swapping Implementation<\/h3>\n
This version keeps one stack empty, and swaps all content between the two each time we switch between enqueue and dequeue operations.<\/p>\n
\r\n#include <stdio.h>\r\n#include <stack>\r\n\r\n\/\/ This implementation uses two stacks. It keeps one empty, and swaps content\r\n\/\/ whenever we switch between eprforming enqueues and dequeues.\r\nclass FakeQueue\r\n{\r\n std::stack<int> s1;\r\n std::stack<int> s2;\r\n\r\n\t\/\/ We need to keep track of the last operation (push vs. pop) so that we can\r\n \/\/ resorder our stack whenever we switch between enqueue and dequeue.\r\n\ttypedef enum { PUSH = 0, POP } STACK_OPS;\r\n\tSTACK_OPS last_op;\r\n\r\n\tvoid SwapStacks();\r\n\r\npublic:\r\n\tvoid enqueue(int i);\r\n\tbool dequeue(int &i);\r\n\r\n\tFakeQueue() : last_op(PUSH)\r\n\t{ \/* empty constructor *\/ }\r\n};\r\n\r\n\/\/ SwapStacks swaps the stack between s1 and s2.\r\nvoid FakeQueue::SwapStacks()\r\n{\r\n\tif (s1.empty())\r\n\t{\r\n\t\twhile (!s2.empty())\r\n\t\t{\r\n\t\t\ts1.push(s2.top());\r\n\t\t\ts2.pop();\r\n \t\t}\r\n\t}\r\n\telse\r\n\t{\r\n while (!s1.empty())\r\n {\r\n s2.push(s1.top());\r\n s1.pop();\r\n }\r\n }\r\n}\r\n\r\nvoid FakeQueue::enqueue(int i)\r\n{\r\n\tif (last_op == POP)\r\n\t{\r\n\t\tSwapStacks();\r\n\t\tlast_op = PUSH;\r\n\t}\r\n\r\n\tif (s1.empty())\r\n s2.push(i);\r\n\telse\r\n s1.push(i);\r\n}\r\n\r\n\/\/ Retrieves the oldest item in the virtual queue. If the queue is empty, sets i to\r\n\/\/ -1 and returns false. Otherwise, it returns true.\r\nbool FakeQueue::dequeue(int &i)\r\n{\r\n if (last_op == PUSH)\r\n {\r\n SwapStacks();\r\n last_op = POP;\r\n }\r\n\r\n if (!s1.empty())\r\n {\r\n i = s1.top();\r\n s1.pop();\r\n return true;\r\n }\r\n else if (!s2.empty())\r\n {\r\n i = s2.top();\r\n s2.pop();\r\n return true;\r\n }\r\n else\r\n {\r\n \/\/ Queue is empty.\r\n i = -1;\r\n return false;\r\n }\r\n}\r\n\r\nint main(int \/*argc*\/, char ** \/*argv*\/)\r\n{\r\n FakeQueue queue;\r\n int i;\r\n\r\n \/\/ Perform a variety of queues and dequeues to show that the queue order is\r\n \/\/ always maintained.\r\n\r\n queue.enqueue(1);\r\n queue.enqueue(2); \/\/ contains { 1, 2 }\r\n\r\n queue.dequeue(i);\r\n printf("Dequeued %d\\n", i);\r\n\r\n queue.enqueue(3);\r\n queue.enqueue(4); \/\/ contains { 2, 3, 4 }\r\n\r\n queue.dequeue(i);\r\n printf("Dequeued %d\\n", i);\r\n\r\n queue.enqueue(5); \/\/ contains { 3, 4, 5 }\r\n\r\n while (queue.dequeue(i))\r\n {\r\n printf("Dequeued %d\\n", i);\r\n }\r\n\r\n return 0;\r\n}\r\n<\/pre>\nInput-Output Stack Implementation<\/h3>\n
This version uses dedicated input and output stacks. All input goes on the input stack. When dequeue is called, if the output stack has anything on it, it takes the topmost value, otherwise it transfers the entire input stack into the output stack.<\/p>\n
\r\n\r\n#include <stdio.h>\r\n#include <stack>\r\n\r\n\/\/ The second implementation uses dedicated input and output stacks.\r\nclass FakeQueue\r\n{\r\n std::stack<int> in;\r\n std::stack<int> out;\r\n\r\npublic:\r\n void enqueue(int i);\r\n bool dequeue(int &i);\r\n};\r\n\r\nvoid FakeQueue::enqueue(int i)\r\n{\r\n in.push(i);\r\n}\r\n\r\nbool FakeQueue::dequeue(int &i)\r\n{\r\n \/\/ Abort if our queue is empty.\r\n if (in.empty() && out.empty())\r\n {\r\n i = -1;\r\n return false;\r\n }\r\n\r\n \/\/ If the "out" stack is empty, shift the contents of the "in" stack into\r\n \/\/ it...\r\n if (out.empty())\r\n {\r\n while (!in.empty())\r\n {\r\n out.push(in.top());\r\n in.pop();\r\n }\r\n }\r\n\r\n \/\/ Pop the return value from the "out" stack:\r\n i = out.top();\r\n out.pop();\r\n\r\n return true;\r\n}\r\n\r\nint main(int \/*argc*\/, char ** \/*argv*\/)\r\n{\r\n FakeQueue queue;\r\n int i;\r\n\r\n \/\/ Perform a variety of queues and dequeues to show that the queue order is\r\n \/\/ always maintained.\r\n\r\n queue.enqueue(1);\r\n queue.enqueue(2); \/\/ contains { 1, 2 }\r\n\r\n queue.dequeue(i);\r\n printf("Dequeued %d\\n", i);\r\n\r\n queue.enqueue(3);\r\n queue.enqueue(4); \/\/ contains { 2, 3, 4 }\r\n\r\n queue.dequeue(i);\r\n printf("Dequeued %d\\n", i);\r\n\r\n queue.enqueue(5); \/\/ contains { 3, 4, 5 }\r\n\r\n while (queue.dequeue(i))\r\n {\r\n printf("Dequeued %d\\n", i);\r\n }\r\n\r\n return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Here are two solutions for using stacks to emulate a queue. The first always keeps one or both stacks empty, shifts the set of values back and forth as the caller switches between enqueuing and dequeueing. The second maintains an … Continue reading