A Primer on Stacks and Queues

Covering the implementation of two key data structures

Data structures, formats for storing data, allow us to do four main things with a set of data: (i) input, (ii) modify, (iii) maintain, and (iv) retrieve. All data structures give us these basic capabilities. Each of these capabilities is also useful to us in a unique way, so prior to selecting a data structure for our data, we need to think about a few things. What is it that we need to do with our data? Are we concerned about memory usage? How quickly do we need our program to run? Each data structure varies in its functionality, memory, and runtime, and it’s important to understand how.

Primarily, I will discuss the implementation of two data structures: stacks and queues. It is unlikely that you will need to implement these structures on your own — most languages have them built-in — but knowing how to do it will help you understand these data structures and prepare you for interview questions.

Stacks

A stack is a linear data structure that follows the Last-In-First-Out (“LIFO”) method. As the name implies, elements are stacked on top of each other, and the only element that can be removed is the last in the stack. Imagine trying to remove a pancake from the middle of a stack. Well, it would likely topple over, so your best bet is to remove the top pancake each time until the stack is gone. That’s a real-world scenario in which you’d be applying the LIFO method. You also encounter stacks every time you browse the internet. The powerful “back button” is just a stack of websites you’ve previously visited in the order in which you visited them!

Basic operations:

• Insert an element at the top of the stack (push)
• Remove the top element from the stack (pop)
• Return the top element without removing it (peek)
• Check if the stack is empty or full

General process:

1. Create a pointer to keep track of the top element.
2. Push: Check if the stack is full. If it is, return an error and exit. If the stack is not full, increment the index of the top to point to the next empty space. Add the element to the open space indicated by the top pointer. Return success.
3. Pop: Check if the stack is empty. If it is, return an error and exit. If it is not empty, access the element that top is pointing to and decrease the value of top by one. Return success.

Queues

A queue is similar to stack in that it is also a linear data structure that stores data in a sequential manner. However, queues follow the First-In-First-Out (“FIFO”) method. Each of us likely encounters this method on a daily basis when we are getting a morning coffee or buying lunch. Every new customer joins the end of the line, or queue, and the first person in line is the first to order and leave the line.

In contrast to a stack, where only the top end is accessible, both ends of a queue are open: one end is used for inserting data and another end is used for removing data.

Basic operations:

• Add an element to the queue (enqueue)
• Remove an element from the queue (dequeue)
• Return the element at the front of the queue without removing it (peek)
• Check if the queue is full or empty

General Process:

1. Create two pointers, one to keep track of the front and one to keep track of the rear.
2. Enqueue: Check if the queue is full. If it is, return an error and exit. If it is not, increment the rear point to point to the next open spot. Add the element to the queue location indicated by the rear pointer. Return success.
3. Dequeue: Check if the queue is empty. If it is, return an error and exit. If it is not, find the front pointer. Increment the front pointer to the next element and return that element. Return success.

Selecting the Appropriate Data Structure

Stacks and queues are essentially lists or arrays with less flexibility. So why would we want to store our data in a stack or queue instead of an array? In order to select the appropriate data structure, we need to think about what we would like to do with our data and how quickly we would like to do it.

We may want to store our data in a stack or queue to enforce certain methods of operating on our data. An array doesn’t establish any order in which elements must be added or removed. For that reason, you would need to shift all elements that follow or precede the element you are adding or removing. This requires iteration over the entire list. Instead, if your algorithm consistently needs to access the top element in an array, use a stack. If your algorithm needs access to the first and last elements in an array, use a queue. This will make your code cleaner and will make your algorithm operate more efficiently.

In terms of Big O Notation, inserting and deleting elements in arrays are O(N), meaning an algorithm’s performance will grow linearly in proportion to the size of the data set given that the operations will require iteration over the entire data set. In contrast, inserting and deleting elements in stacks and queues are O(1), meaning they will always execute in the same amount of time regardless of the size of the data. This is quite intuitive as stacks and queues eliminate the need for iteration over the data set.

Data structures are fundamental building blocks for programming. Remember to think critically about the data structures you’re using when building your code — they will have an impact on your final product. I’ve only touched on a few types in this piece, but there are many others and I urge you to read about them too to get a full understanding of your options.