# 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

[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, **/
/*****************************************/

int stack_push(stack_template *tail, stack_template *input)
{
stack_template *temp = tail-&gt;next;
tail-&gt;next = input;
input-&gt;next = temp;
return 0;
}

int stack_pop(stack_template *tail, stack_template *output)
{
stack_template *temp = tail-&gt;next;
temp = temp-&gt;next;
output = tail-&gt;next;
//Make the tail point to the new head
tail-&gt;next = temp;
return 0;
}

int queue_enqueue(queue_template *tail, queue_template *input)
{
queue_template *temp = tail-&gt;next;
//Add the new tail onto the old tail
tail-&gt;next = input;
//Make the new tail point to the head
input-&gt;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: