Queue Data Structure | Skilled.dev


Course launching September 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
A queue is a linear data structure that handles items based on the order in which they are added. We add items to the back of the queue and remove items from the front, all in O(1) time. Queues operate in first-in-first-out (FIFO) order. The first item added (oldest in the queue) is the first one that will be removed.
A queue data structure is exactly how we handle lines at stores. The first person (the one who has been waiting the longest) is going to be at the front of the line and will be helped first.

Cheat Sheet

Big O Complexity
Pros 🔥
  • Fast Access at the Ends
    We can add an item to the back and remove an item from the front in O(1) time.
  • Ordered
    The data is ordered where items added first are at the front and items added last are at the back.
Cons 🤕
  • Slow Lookups
    To access any item other than the front, it will take O(n) time to iterate through the queue and find it.

Queues in Interviews

  • Build a stack using queues
  • Task scheduling or ordering items
  • Caching or storing some fixed number of items

Queues Explained

Queues are fundamental data structures to how we execute code, but they also easily map to real-world scenarios. Anytime we wait in line, we are behaving just like a queue - the first person who arrived will be helped first. Call centers function in the same manner. The operators handle calls based on who phoned in first.

Queues are utilized in programming in many ways:

  • A CPU handling multiple processes and scheduling
  • Events and message queues (ex. RabbitMQ, ZeroMQ, pub/sub)
  • LRU Cache
  • Fundamental to the JavaScript event loop
  • Breadth first search
Generate All Permutations
Implement a Queue

Table of Contents