things & stuff

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 advantage of the latter implementation is that transfer between the two stacks occurs only when dequeue is called and the output stack is already empty.

Below is the C++ code implementing and testing the two queue classes, FakeQueue and FakeQueue2:

#include 
#include 

// The first implementation uses two stacks, but always keeps one empty.  The
// stacks are swapped anytime we switch between performing enqueues and
// dequeues.
class FakeQueue
{
    std::stack s1;
    std::stack s2;

	// We need to reorder our stack whenever that we switch betwee queueing and
	// dequeueing.
	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 'queue'.  If the queue is empty, sets i to
// -1 and returns false.
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 empty.
        i = -1;
        return false;
    }
}

// The second implementation uses an "in" and an "out" queue.
class FakeQueue2
{
    std::stack in;
    std::stack out;

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

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

bool FakeQueue2::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...

    queue.enqueue(1);
    queue.enqueue(2);

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

    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(5);

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

    queue.enqueue(6);
    queue.enqueue(7);
    queue.enqueue(8);
    queue.enqueue(9);

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

    queue.enqueue(10);

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

    return 0;
}