Stacks and Queues - An Introduction

Previously we've discussed about two types of containers for storage of data, arrays and linked structures. To expand a little further, we'll introduce two abstract data types that can be built from linked structures or arrays, stacks and queues.

An abstract data type (ADT) provides a definition rather than the concrete implementation. It defines what the data structure or data type can and cannot do (operations it can perform, and constraints of the structure). ADT's are generally implemented using existing data structures or data types. 

Stacks and queues are examples of ADT's. Conceptually each provide the description of the operations it can perform, and the limitations as to how they are supposed to operate. 

Stacks - 

The stack data structure functions as literally as the name suggests. Imagine at a dockyard, a crane stacking a number of shipping containers one on top of another. 

Figure 1 - Stacks of shipping containers 

Figure 1 shows a bunch of shipping containers all stacked on top of another. If we treat each column of containers as a single stack, we begin to notice that we're unable to remove the containers towards the bottom without removing the top most containers first. This is exactly how the ADT stack works.

A stack functions as a "Last in First Out" (LIFO) data structure, meaning the last item to be placed onto the stack is the first item taken out. Returning to the shipping container example, it means that we cannot remove the bottom most container until we've removed all the others above it. 

The process of adding and removing items from a stack is called push and pop.

• Push (x, s) - Is the equivalent of adding an item onto the stack. This method definition means "to push item x onto the stack s".


• Pop (s) - Is the equivalent of removing the top most item from the stack. This method definition means "to pop the top most item from stack s".

Push and pop are the two most basic operations that are performed on any stack. There is a third operation top (also known as peek), that is sometimes defined. 

• Top/Peek (s) - Is the equivalent of asking "which item is at the top of the stack". It returns the requested item (if any) without removing it from the stack.

Queues - 

The queue data structure is just as literal as the definition for a stack. Imagine a single filed line of people at a bank like the illustration below.

Figure 2 - A queue of people in a line

Figure 2 illustrates exactly what a queue data structure represents. The person at the front of the line is the first one out of the line, all new people must follow the rules and line up at the end, no queue jumping or asking for favours. 

A queue functions as a "First in First Out" (FIFO) data structure. The two main operations to add and remove items from a queue are called enqueue and dequeue.

• Enqueue (x, q) - Is the equivalent of "insert item x at the end of the queue q" or telling someone to line up at the end of the line. 


• Dequeue(q) - Is the equivalent of "remove and return the first item from the queue q", or having the bank teller say "next person please!".

These are the two most basic operations on a queue, however like a stack, there is also a third operation that can also be implemented, front (or peek).

• Front/Peek(q) - Is the equivalent of looking to see who's at the front of the queue, without actually removing them from the line. 

Summary - 

Stacks and queues can be implemented with both arrays and linked structures. To determine which structure is best to use is dependant on the situation.

If the we know the size of the stack or queue in advance, then we can use an array, otherwise it would be better to use a linked list since it is more dynamic when adding additional items. 

Stacks are useful to use when retrieval order of items does not really matter like in batch jobs. It is also useful for reversing a particular order of items since we can take advantage of the "Last in First Out" property of a stack.

Queues are useful when we want to control the waiting times for particular items. A queue allows us to minimise the maximum waiting time.  It is also useful if ordering of items is important.