Stacks and Queues, Simplified

A breakdown of stacks and queues in JavaScript.

Visual guide to stacks. Source

Stacks and Queues are probably the most self-explanatory data structures, but to some they can still seem intimidating. Let’s think of them in terms of real-world applications.

You use a stack every day when you are browsing the internet or editing text. A stack is what keeps track of the websites visited/changes made so that our back/forward and undo/redo buttons function properly. Whatever goes on top of the stack is the first thing to get removed.

Visual representation of a queue. Source

If you’ve ever waited in line for anything, you’ve been part of a queue. The front of the line always gets processed first.

Stacks and queues can be implemented in different ways, but they must follow the rules highlighted above in italic.

Stack Implementation

A stack can be thought of like… a physical stack. In terms of programming however, we can think of a stack as an array. However, we need to limit the mutation of the array so it follows the Last In First Out(LIFO) rule.

We’re going to consider a teacher grading papers and entering them into her grade-book for this example. When the teachers finishes grading a paper, she places it in the stack. Once she’s finished grading, she’ll remove papers from the top of the stack to enter into the grade-book.

Array implementation of a stack using push/pop

This is a simple implementation of a stack — notice that the last paper that gets graded is the first one that gets “popped” off the stack and into the grade-book. We’ve used push and pop to operate on the end of the array, but couldn’t we do this with unshift and shift too?

Array implementation of a stack using shift/unshift

This implementation does follow the LIFO rule, but it’s not very efficient. Remember that arrays are indexed in JavaScript, so every time we change the beginning of the array, the rest of the array gets re-indexed.

We’ve uncovered the second rule of stacks and queues — an overall rule for data structures in general. The purpose of using a data structure is that we’re improving on the time and/or number of operations it takes to process that data — it’s time complexity. (If this sounds unfamiliar, check out my blog on Big O Notation).

Stacks and Queues are most efficient at insertion and removal, at O(1) or constant time. Using shift and unshift re-indexes the array, so at best we’re in O(n) time, where the time grows as the length of the array grows. Push and pop only change the end of the array, so it works in constant time. However, we don’t want to accidentally use another method on an array, so it’s better to limit ourselves by implementing it using another data structure — a linked list.

Linked list implementation of stack adding and removing to the beginning for constant time

Now we’ve limited the methods for our stack, we’ve ensured that it is efficient and follows the LIFO rule.

Queue Implementation

If we can implement a stack with an array, surely we can do the same with a Queue, right? In this example, we’re going to consider a print queue — the printer is going to handle documents in the order that they were sent in, in other words, First In First Out (FIFO).

Array implementation of queue using push and shift

In order for our queue to follow FIFO, we need to remove from the opposite end that we add to. That means that we’ll have to end up using shift or unshift, which will reduce our efficiency through re-indexing. We need to use a different data structure to implement our Queue.

Linked list implementation of queue

In this example we’re using enqueue to add elements and dequeue to remove elements.

Other Operations

Remember that Stacks and Queues are used for their efficiency in insertion and removal, so their time complexity for accessing and searching are limited to your implementation. In the case of our linked lists, they are O(n). However, as long as your implementation has constant time for Insertion/Removal and follows the LIFO/FIFO rules, your stack/queue will work.

Resources

The Startup

Get smarter at building your thing. Join The Startup’s +793K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Gianfranco Nuschese

Written by

Web Developer in Brooklyn, NY

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +793K followers.

Gianfranco Nuschese

Written by

Web Developer in Brooklyn, NY

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +793K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store