Recitation 10: Queues, Stacks, and Pointer Manipulation

Queues

We will explore queues as a specific application for linked lists. To describe queues, we can make an analogy to standing in line at the store. When you're ready to pay, you get in the back of the line. As much as we might like to, you can't push everyone else out of the way, so you have to stay last in line. If someone comes after you, then they have to go behind you. On the other hand, after the current shopper finishes paying, the first person in line goes next. Eventually, it's your turn. At this point, you are at the front of the line. Equivalently, you can think of a queue as pieces of data waiting in line for your program to evaluate them. When we want to add a new element, or enqueue it, we add it to the back. When we want to pick a new element to evaluate, we remove it, or dequeue it from the front. This is refered to as a first in first out (FIFO) data structure.

So, how do we implement this as a linked list? We can pretty much use a linked list in its most basic form with a few more additions. For one, we want a type we can call a queue:

  struct queue_header {
list *front;
list *back;
}
typedef struct queue_header *queue;

We'll discuss why we chose this struct soon. Note that usually we don't put the '*' in the typedef. We do this to remind ourselves that we're working with pointers. However, in this case, we want to implement an abstract type that reveals as little about its implementation as possible.

So, why keep these two pointers? Intuitively, we can see that the intent is for these to point at the first and last thing in the linked list. We also choose to end our linked list with a dummy node, so back is always pointing to that dummy node. Recall that the two main operations we want to perform on linked lists are enqueue and dequeue. On a fairly high level, how do we want to go about implementing these? For dequeue, we can just remove the node pointed to by front and then update front so that it points to the old front->next. Similarly for enqueue, we fill the data field of the dummy node, pointed to by back, allocate a new dummy node, and update the pointers for the old back->next and back to the new dummy node. Be careful about the order you update pointers, since it can drastically affect what happens.

So, now we've seen that we can implement queues as linked lists, but is this a good choice? Let's think back to the two operations we've just described. In both cases, we can do the required work without traversing any amount of the linked list, meaning that both operations are $O(1)$. So, that sounds pretty encouraging. Furthermore, we can just keep adding nodes endlessly, so we don't have to worry about our queue growing arbitrarily large. For these reasons, it turns out that a linked list is a good choice of a data structure for a queue.

You should go back and take a look at the implementation to review why the functions work according to their specification. Some of these operations are shown visually in the links above.

Stacks

Fundamentally, stacks are very similar to queues. We will also implement stacks as a linked list. This time, we will refer to the two ends of the linked list as the "top" and "bottom." Similar to queues, we define two primary operations on stacks. To remove elements from the stack, we pop them off of the top. However, when we want to add new elements, they also get added to the top. This is known as a push operation. Clearly, the flow of data in and out of the stack is changed significantly. Stacks are a last in, first out (LIFO) data structure. With similar motivations, we propose the following struct wrapper for stacks:

  struct stack_header {
list *top;
list *bottom;
}
typedef struct queue_header *queue;

The push and pop functions are very similar to enqueue and dequeue, except that both operate on the top of the stack. So, you may argue that there's no reason to keep track of the bottom of the stack in the first place. If you're thinking this, you have a perfectly valid point--we could leave the bottom pointer out and still have a great stack implementation. However, we've included it for a few reasons:

1. Making it as similar as possible to queues.
2. It helps us write some strong annotations in our implementation
3. It's really easy to write stack_empty(stack S). It's just return S->top == S->bottom;.

Again, you should observe that all of the major functions that operate on stacks run in $O(1)$.

Interfaces

If you have any comments or see any errors, please let me know.