Queue Implemented Using Stacks

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.

The latter implementation is more efficient — transfer between the two stacks occurs only when dequeue is called and the output stack is already empty — as well as more compact and readable.

Stack-Swapping Implementation

This version keeps one stack empty, and swaps all content between the two each time we switch between enqueue and dequeue operations.

#include <stdio.h>
#include <stack>

// This implementation uses two stacks.  It keeps one empty, and swaps content
// whenever we switch between eprforming enqueues and dequeues.
class FakeQueue
{
    std::stack<int> s1;
    std::stack<int> s2;

	// We need to keep track of the last operation (push vs. pop) so that we can
    // resorder our stack whenever we switch between enqueue and dequeue.
	typedef enum { PUSH = 0, POP } STACK_OPS;
	STACK_OPS last_op;

	void SwapStacks();

public:
	void enqueue(int i);
	bool dequeue(int &i);

	FakeQueue() : last_op(PUSH)
	{ /* empty constructor */ }
};

// SwapStacks swaps the stack between s1 and s2.
void FakeQueue::SwapStacks()
{
	if (s1.empty())
	{
		while (!s2.empty())
		{
			s1.push(s2.top());
			s2.pop();
   		}
	}
	else
	{
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
    }
}

void FakeQueue::enqueue(int i)
{
	if (last_op == POP)
	{
		SwapStacks();
		last_op = PUSH;
	}

	if (s1.empty())
        s2.push(i);
	else
        s1.push(i);
}

// Retrieves the oldest item in the virtual queue.  If the queue is empty, sets i to
// -1 and returns false.  Otherwise, it returns true.
bool FakeQueue::dequeue(int &i)
{
    if (last_op == PUSH)
    {
        SwapStacks();
        last_op = POP;
    }

    if (!s1.empty())
    {
        i = s1.top();
        s1.pop();
        return true;
    }
    else if (!s2.empty())
    {
        i = s2.top();
        s2.pop();
        return true;
    }
    else
    {
        // Queue is empty.
        i = -1;
        return false;
    }
}

int main(int /*argc*/, char ** /*argv*/)
{
    FakeQueue queue;
    int i;

    // Perform a variety of queues and dequeues to show that the queue order is
    // always maintained.

    queue.enqueue(1);
    queue.enqueue(2); // contains { 1, 2 }

    queue.dequeue(i);
    printf("Dequeued %d\n", i);

    queue.enqueue(3);
    queue.enqueue(4); // contains { 2, 3, 4 }

    queue.dequeue(i);
    printf("Dequeued %d\n", i);

    queue.enqueue(5); // contains { 3, 4, 5 }

    while (queue.dequeue(i))
    {
        printf("Dequeued %d\n", i);
    }

    return 0;
}

Input-Output Stack Implementation

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.

#include <stdio.h>
#include <stack>

// The second implementation uses dedicated input and output stacks.
class FakeQueue
{
    std::stack<int> in;
    std::stack<int> out;

public:
    void enqueue(int i);
    bool dequeue(int &i);
};

void FakeQueue::enqueue(int i)
{
    in.push(i);
}

bool FakeQueue::dequeue(int &i)
{
    // Abort if our queue is empty.
    if (in.empty() && out.empty())
    {
        i = -1;
        return false;
    }

    // If the "out" stack is empty, shift the contents of the "in" stack into
    // it...
    if (out.empty())
    {
        while (!in.empty())
        {
            out.push(in.top());
            in.pop();
        }
    }

    // Pop the return value from the "out" stack:
    i = out.top();
    out.pop();

    return true;
}

int main(int /*argc*/, char ** /*argv*/)
{
    FakeQueue queue;
    int i;

    // Perform a variety of queues and dequeues to show that the queue order is
    // always maintained.

    queue.enqueue(1);
    queue.enqueue(2); // contains { 1, 2 }

    queue.dequeue(i);
    printf("Dequeued %d\n", i);

    queue.enqueue(3);
    queue.enqueue(4); // contains { 2, 3, 4 }

    queue.dequeue(i);
    printf("Dequeued %d\n", i);

    queue.enqueue(5); // contains { 3, 4, 5 }

    while (queue.dequeue(i))
    {
        printf("Dequeued %d\n", i);
    }

    return 0;
}