Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

One Structure Design – Stack and Queue

As anyone with some experience can attest, Lists are generally highly inefficient data structures. Locating any given object is an O(n) operation, and sorting is at best O(n log n). However, there are two implementations of lists that are superior to all others: stacks and queues.

Stacks

Imagine a tower of blocks, like we use in the Tower of Hanoi puzzle (or like small children play with). As you add each element to the tower, the previous element becomes harder to reach. In order to get to the bottom of the tower, you have to take off the top block each time. This is a stack. Basically, when we create a stack in our computer, we add things at the head of the list and remove them from the head. This creates last-in-first-out (LIFO) operation.

Queues

Now imagine a line at your local Department of Motor Vehicles (or Transportation – whatever you have in your state). Or somewhere else. Seriously, nobody wants to think about the bureaucracy lines. The first person in line is taken care of first, right? And the later you show up, the longer it takes to get to you. This is a first-in-first-out (FIFO) list, which we call a queue. In a computer, this means that we do one of two things: 1. We add to the head and remove from the tail 2. We add to the tail and remove from the head The problem is, while stacks are easy, queues require us to be able to reach the end of the list. This means that, if we have n items, it will take nO(n) operations to either add or remove every item – this is an O(n^2) operation!

Solution: Make a circle

Imagine that we design a list with the following rules: 1. We always know where the end of the list is (as opposed to the head) 2. The end of the list always points back to the start 3. We can only remove from the head of the list 4. We can add to either the head or the tail of the list This list would allow us to create a stack (add and remove from head) and a queue (add to tail, remove from head) with minimal modification. Furthermore, the queue becomes every bit as efficient as the stack, because it takes exactly 1 jump to reach the head and 0 jumps to reach the tail. Now, both the stack and queue are O(1) operations! Roughly sketched out, it would look something like this:

[code language=”c”] struct list_template
{
//A super-basic list just has one pointer
struct list_template *next;
}

//Just set up a typedef – same structure, two names
typedef struct list_template queue_template;
typedef struct list_template stack_template;

/*****************************************/
/** We deal with the tail, **/
/** Not the head **/
/*****************************************/

int stack_push(stack_template *tail, stack_template *input)
{
//Hold the head
stack_template *temp = tail->next;
//Replace old head with input
tail->next = input;
//Make new head point to old head
input->next = temp;
return 0;
}

int stack_pop(stack_template *tail, stack_template *output)
{
//Hold the head
stack_template *temp = tail->next;
//Get the new head
temp = temp->next;
//Take out the old head
output = tail->next;
//Make the tail point to the new head
tail->next = temp;
return 0;
}

int queue_enqueue(queue_template *tail, queue_template *input)
{
//hold the head
queue_template *temp = tail->next;
//Add the new tail onto the old tail
tail->next = input;
//Make the new tail point to the head
input->next = temp;
//Make the original pointer point to the new tail
tail = input;
return 0;
}

int queue_dequeue(queue_template *tail, queue_template *output)
{
//We’re popping from the head, so let’s cheat!
stack_pop (
(stack_template *) tail,
(stack_template *) output
);
return 0;
}
[/code]

See how easy that was? It’s a good thing.

photo by: