Interview OS
Back to Algorithms & Data Structures

Library

Stacks & queues

LIFO and FIFO building blocks.

Linear

Overview

Stacks (LIFO) and queues (FIFO) are the two disciplines for ordering pending work. Stacks power recursion, undo, and parsing; queues power scheduling and BFS. Choosing the right one often makes a hard problem trivial.

How it works

Linear
PushStorePopOutputAddpush/enqueueBuffertop/headRemoveO(1)Use
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Add

    • Stack is LIFO; queue is FIFO.
  2. 2

    Buffer

    • Array or linked-list backing.
  3. 3

    Remove

    • Stack pops the top; queue pops the front.
  4. 4

    Use

    • Undo, BFS, and scheduling.
    • Example: call stack

Overview

Stacks (LIFO) power recursion, parsing, and monotonic-stack tricks; queues (FIFO) power BFS and scheduling.

When to use it

  • Balanced-parentheses checks
  • Next-greater-element
  • Level-order traversal

Common pitfalls

  • Using array shift() (O(n)) for a queue
  • Forgetting empty-structure checks

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides