Know Your Data Structures: Queues and Stacks
Tuesday, August 08, 2006

Stacks

A stack is a dynamic linear data structure where insertion and deletion of items is already predetermined. This basically means that we already know where items are added and deleted before we perform the operation itself. Here's how it works. Stacks only allow you to insert and delete items from the top (or tail of the stack). This logic flow is called LIFO ("Last In First Out") and means that the deletion of an item from the stack is always the item that was most recently added. A good analogy that I've read is a stack of dishes in a restaurant's buffet line. New plates are added at the top of stack and when a customer grabs one, the top-most plate is removed. Insert and delete operations are called push and pop respectively and both are performed in constant time O(1).

When implementing a stack data structure, there are two main boundary conditions you need to account for: underflow and overflow. An underflow occurs when an empty stack is "popped." This means that a delete operation was attempted on an empty stack. An overflow occurs when a full stack is "pushed." This means that an insert operation was attempted on a full stack. Below, I have provided some pseudocode showing how a simple stack structure works:

void Push(int newValue)
{
    if (Stack isn't full (e.g. overflow))
    {
        - Add item to top of stack
        - Increment your top index value
    }
}

void Pop(int & newValue)
{
    if (Stack isn't empty (e.g. underflow))
    {
        - Remove item from top of stack and assign
          to the newValue parameter
        - Decrement your top index value
    }
}

Queues

A queue is also a dynamic linear data structure with predetermined insertion and deletion operations. The main difference between a stack and queue is that a queue practices FIFO ("First In First Out"). This means that new items are added at the top of the queue (or tail) and are removed from the bottom (or head). A good analogy is your standard waiting line to get into the movie theater. You get in line at the end and wait until those customers before you have purchased tickets and walked away. Then you get to go next while the people who entered the line after you await their turn. Insert and delete operations are called enqueue and dequeue respectively and both are performed in constant time O(1) just like stacks.

Queues require slightly more work because we are required to keep up with both the beginning (the "head") and the ending (the "tail") of the structure in our implementations. With stacks, all we have to do is just make sure that the top-most element is within boundary limits. With queues, we are required to make sure that when an element is added, it goes in the tail's current location and when an item is removed, we have to make sure that the element in the head's current location is deleted. Also, the same boundary conditions in stacks exist for queues (e.g. underflows and overflows). Below, I have provided some pseudocode showing how a simple queue structure works:

void Enqueue(int newVal)
{
    if (Queue isn't full (e.g. overflow))
    {
        - Add your value to the tail of the queue
        - Increment your tail index (or wrap it)
    }
}

void Dequeue(int & newVal)
{
    if (Queue isn't empty (e.g. underflow))
    {
        - Remove item from queue and assign to the
          newVal parameter
        - Increment your head index (or wrap it)
    }
}

Stacks and queues are simple and easy to use for certain programming projects (e.g. postfix/infix evaluations). The easiest implementation technique used for both is to use an array as the internal structure (my pseudocode examples use an array). There are more complex implementations but arrays are used more frequently because of the simplicity. As always, post comments if something isn't clear and I'll try to help out. If you'd like the full queue and stack class files (.h & .cpp) let me know and I'll provide a link to them. Until next time...

-Gilemonster

Labels: General