Hello me, nice to see you again. In case you had forgotten about the joys of implementing a stack using two queues, let’ me offer you some pointers (little C joke for you there).
Stacks and queues are already familiar concepts at this point, and you probably already know the difference between them. Namely, a stack is a FIFO data structure while a queue is LIFO. Previously we’ve implemented a stack using a dynamic array and a linked list, but how about implementing a stack using two queues?
The advantage of using queues to implement a stack is that a queue has O(1) access to the front, so the
top methods of the stack are actually very easy, compared to say a stack implementation with a normal singly linked list.
First thing’s first: A queue using a singly linked list
This implementation is pretty tricky at first, so let’s start by just defining our structs:
We have a couple building blocks here. We have queues which are composed of single links and two pointers, one sentinel link in the front and another pointer to the last link in the back. Then the stack itself is made of two queues, which we will explain why further down.
Initializing the queues is somewhat familiar from previous work that we’ve done!
When we create a queue, our
tail pointers both go to the sentinel since our queue is empty.
Similarly to before, the
next pointer in the sentinel starts at pointing to $NULL$.
Let’s implement some more functions for the queue! We haven’t explored this yet in this series, but now is as good as any to start.
A queue has a couple basic functions:
- Enqueuing (for us, that’s adding a new link at the end of the linked list)
- Dequeuing (this would be removing the link right after the sentinel)
- Front (returning the value right after the sentinel node)
Let’s start by writing our
Pretty straightforward function, just need to make sure that our queue’s tail pointer now points to this new link and that the current last link’s next pointer also points to the new link.
Let’s take a look at the
dequeuing function now which will remove and free the link after the sentinel.
The actual output of this function will be the value that we are removing from the queue, which will come in handy later.
One important part is defining pointer variable
If the queue only has one link, then
rm is that one link and removing it is essentially making queue’s tail pointer equal to the head pointer, which is the queue’s sentinel.
We then free the first link.
The other is making sure to properly handle the case when there is only one link in the list.
In that case, we have to make sure that the tail pointer and the head pointer are equal to each other.
We also have to make sure that the pointer
queue->head->next = NULL like in the initialized linked list queue.
Front function is pretty straightforward.
So are the
Note that even though
Remove return a value of TYPE, we don’t necessarily have to capture that value using some throwaway variable.
Now we are ready to start implementing the stack!
2 Queues, 1 Stack
The basic idea is that we have one queue which holds all the values and then another queue which we will use as a container to help move elements around in the first queue. Here’s the general idea:
- When we add an element to the stack, we want to add it on queue 1. However, since queues are FIFO and stacks have to be FIFO, we basically have to remove all the existing elements in queue 1 first and copy them over to queue 2 in order.
- Once queue 1 is empty, we add the new element to it
- We then take queue 2 and empty it, taking all the values we remove and sticking them on the back end of queue 1.
When the two queues work together, the first queue will behave like a stack!
And since it’s still a stack,
top are O(1).
Let’s start by writing the function to initialize the stack, which again is just two queues stuck together in a struct.
Let’s write some other basic functions:
These are pretty easy since it’s basically just doing functions on queues which we’ve already written!
So now we get into some spicier stuff. In the pseudocode I wrote above, I said that we would copy over elements from queue 1 and put them in queue 2 when we wanted to add a new element to the top of the stack. A slightly easier way to do this is to just have a function that swaps the two queues with each other.
Push will be our most complex function (but that means we’re almost done!)
Remember that we are basically treating queue 1 as our stack, so in the end of this push, we should have the new value at the front of queue 1.
To do this, we actually begin by pushing the new value to queue 2 (which is empty) and then moving everything from queue 1 to queue 2.
We will then use the
swap function AFTER we have added the new value to queue 2 AND have copied everything from queue 1 over to queue 2.
After we swap queue 2 and queue 1, queue 1 will have all the elements and queue 2 will be empty.
Our last functions are
top, but like I said, those are easy!
We finally made it!
You can test the above stack implementation using this code provided by the Oregon State Department of Computer Science or something like that.