Queue Data Structure | Skilled.dev
Learn

Queues

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.
enqueue(front)
back
mid
front

Cheat Sheet

enqueue
last
first
dequeue
Big O Complexity
enqueueO(1)
dequeueO(1)
peekO(1)
spaceO(n)
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
Prev
Generate All Permutations
Next
Implement a Queue

Table of Contents