Queue Data Structure | Skilled.dev
Learn

Queues

Loading...
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 (the one that has been in the queue the longest) 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
Loading...

Table of Contents