Back to curriculum

Queues Cheat Sheet

  • Quick summary: a sequential collection where elements are added at one end and removed from the other end.
  • Important facts:
    • Modeled after a real-life queue: first come, first served.
    • First in, first out (FIFO) data structure.
    • Similar to a linked list, the first (last added) node is called the tail, and the last (next to be removed) node is called the head.
    • Two fundamental operations are enqueuing and dequeuing:
      • To enqueue, insert at the tail of the linked list.
      • To dequeue, remove at the head of the linked list.
    • Usually implemented on top of linked lists because they're optimized for insertion and deletion, which are used to enqueue and dequeue elements.
  • Pros:
    • Constant-time insertion and deletion.
  • Cons:
    • Access and search are O(n).
  • Notable uses:
    • CPU and disk scheduling, interrupt handling and buffering.
  • Time complexity (worst case):
    • Access: O(n)
    • Search: O(n)
    • Insertion (enqueuing): O(1)
    • Deletion (dequeuing): O(1)
  • See also:

Show Cheatsheet

Queues Definition: A container of objects that are inserted and removed according to the first-in, first-out principle.

Interview Problems

Why do I see duplicate challenges? You'll see duplicates because a question may fall into different categories. We keep them here because we believe that it is good to sporadically review old problems. They are optional if already completed-- but reviewing them (and more importantly re-doing them with the new knowledge) will ensure that you've internalized the patterns.

Related Lessons