An Introduction to Stacks and Queues

Improve your data structures

Samuel Guo
Feb 17 · 6 min read
Photo by Pankaj Patel on Unsplash.

Background

Optimizing code is rarely an easy task. The code may be working as intended, but if it takes too long to execute, then the code is inefficient and needs to be optimized. Data structures — a necessary evil in the coding world — represent the main crux for optimization. Using the correct data structure for the correct scenario will make your code run considerably faster than using a brute-force method.

One of these data structures is stacks and queues. Personally, I feel like this is a lesser-known data structure that’s extremely easy to implement and doesn’t get enough love.


Stacks and Queues

Before we dive any deeper, let’s define what stacks and queues are. Stacks follow the first-in-last-out (FILO) pattern. Queues follow the first-in-first-out (FIFO) pattern. Although these two terms are typically bundled together as a phrase, they follow two different design patterns.


Stacks

Let’s take a deeper dive with stacks and start off with an empty stack.

We don’t have anything at the moment. Next, let’s add 10 to the stack.

Adding “10” to the empty stack.

After adding the 10 to the stack, it falls to the bottom of the stack. Keep in mind that the 10 is the first one into the stack. If you add 20 and 30 in that order, the stack should now look like the pictures below:

Adding 20 to the current stack.
Adding 30 to the current stack.

The current stack, from bottom to top, is now 10, 20, and 30. What if I want to get the 10 out? Well, we can’t at the moment because 30 and 20 are blocking the way. We would need to take out the 30, then take out the 20, and then finally we would be able to take out the 10. The 10 would be the last one to come out of the current stack.

Removing 30 from the current stack.
Removing 20 from the current stack.
Removing 10 from the current stack.

This is what it means to be first in, last out (FILO). The first element placed into the stack will be the last element to be removed from the stack. The 10 was the first element to be placed into the stack (first in) and it would be the last element to be removed from the stack (last out). I know this sounds redundant, but explaining these terms as explicitly as possible will help avoid any confusion.


Stacks in Code Terms

Now that we understand what it means to be FILO and how a stack works, it’s time to actually implement a stack in terms of code. I am going to be using JavaScript to demonstrate this. But first, to give a clearer picture, let’s reuse our previous example. For demonstration purposes, let’s rotate the stack 90 degrees clockwise so that it now looks like this:

In regards to code, we can use an array to represent an empty stack.

let stack = []

Next, we can add 10 to the empty stack.

Adding 10 to the empty stack.

In code terms, this is the same as the following:

stack.push(10)
console.log(stack) // [10]

Now let’s put in 20 and 30 in that order.

Adding 20 to the current stack.
Adding 30 to the current stack.

In code terms, this is the same as the following:

stack.push(20)
stack.push(30)
console.log(stack) // [10, 20, 30]

Now let’s bring it back and start removing from the stack, starting with the most recent addition.

Removing 30 from the current stack.

In code, this is the same as:

stack.pop()
console.log(stack) // [10, 20]

For the sake of brevity, I’m going to skip the pictures, but we would do the same thing for 20 and then 10. In code, we would invoke the .pop() method two more times.

stack.pop()
stack.pop()
console.log(stack) // []

Implementing a stack is really that simple! Thanks to JavaScript’s built-in methods, we can implement a stack data structure by using an array and using .push() and .pop() to create our own stack.


Queues

So far, we’ve only talked about stacks and how stacks are FILO. If you were able to follow how stacks work, queues are very similar. Since queues follow the first-in-first-out (FIFO) design pattern, we can also use an array to represent the queue.

Another way of thinking of queues is queueing up on a line. Typically, the people in line are serviced based on the order in which they arrived — just like if you were queueing in line to get into a venue.

I am going to combine images with code to save some time and space.

Similarly to how we started an empty stack, let’s start off an empty queue.

let queue = []

Next, we’re going to add 10, 20, and 30 to the queue in that order. You can use the same images we did for the stack as a reference for the queue, as it is literally doing the same thing. In terms of the code, we will still be using the .push() method.

queue.push(10)
queue.push(20)
queue.push(30)
console.log(queue) // [10, 20, 30]

So far, the first-in portion stayed the same. Since queues are first-out, this is where it diverges from stacks. Currently, our queue looks like the following:

Current queue.

Since the 10 was the first element to be added, it will now be the first removed.

Removing the 10 from the current queue.

So, how would we do this in code? Thankfully, JavaScript also has a built-in method that does this for us: .shift().

queue.shift()
console.log(queue) // [20, 30]

Now, if we were to empty out the queue in the same order as the elements were added in, we would keep invoking the .shift() method.

queue.shift()
queue.shift()
console.log(queue) // []

Implementing a queue is also that simple! As with the stack, we can use JavaScript’s built-in methods for first in with the .push() method and first out with .shift().


Time Complexity of Stacks and Queues

For this section, I am making the following assumptions:

  1. You understand time complexity and Big O notation.
  2. You understand the memory allocation mechanism of arrays.

If you don’t understand the two concepts mentioned above, I highly recommend reading about them before proceeding any further.

For stacks, the time complexity of using the .push() is O(1) because .push() always adds to the end of the array and indexing the pushed element is one operation, as it increases the index by one. Using the .pop() is also O(1) because .pop() accesses and removes the last element of the array. When the last element is removed, the rest of the elements are not affected because they don’t need to be re-indexed. So overall, the time complexity of stacks is O(1).

For queues, since we are using .push() as well, that time complexity is still O(1) for the same reasons mentioned in the last paragraph. However, using the .shift() method has a time complexity of O(n). This is because when you remove the first element from an array, the computer will need to re-index the rest of the elements, which is dependent on the length of the array. So overall, the time complexity of using queues is O(n).

Hopefully, you’ll be able to implement this. If not, at least you walked away knowing an additional data structure!

Better Programming

Advice for programmers.

Samuel Guo

Written by

Better Programming

Advice for programmers.

More From Medium

More from Better Programming

More from Better Programming

More from Better Programming

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade