ReviseAlgo Logo

Stacks & Queues

Stacks & Queues Fundamentals

Master Stack and Queue fundamentals: LIFO vs FIFO principles, array-based vs list-based structures, and operation complexities.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Stacks and Queues?

Stacks and Queues are linear data structures that organize elements according to strict access rules:
  • A Stack operates on the LIFO (Last In First Out) principle.
  • A Queue operates on the FIFO (First In First Out) principle.

    • Why study them?

    Unlike lists or arrays where you can access or modify elements at any arbitrary index, Stacks and Queues restrict access. You can only interact with elements at the ends of the structure, ensuring a predictable order of processing.

    Where is it Used?

  • Function Call Execution: The CPU call stack tracks variables and return addresses for recursive functions (LIFO).
  • Task Buffers: Web servers queue incoming HTTP request packets, processing them in order of arrival (FIFO).

    • 2. Mental Models

    The Dinner Plate Stack (LIFO)

    Imagine a stack of dinner plates at a buffet:
  • You place a new clean plate on top of the stack.
  • When guests arrive, they take a plate from the top of the stack.
  • The last plate placed on the stack is the first one taken by a guest.

    • The Ticket Line Queue (FIFO)

    Imagine a line of fans waiting to buy tickets at a box office:
  • New fans join the line at the rear (tail).
  • The ticket seller serves the fan standing at the front (head) of the line.
  • The fan who arrived first is the first one served and leaves the line.

    • 3. Core Structural Backings

    Both Stacks and Queues can be implemented using two primary backing structures:

    1. Array-Based Implementations

  • Stack: Maintain a top pointer index tracking the last element. Insertion and deletion are simple index pointer assignments.
  • Queue: Maintain front and rear indices. To avoid moving elements during dequeues, we wrap indices using a Circular Array structure.
  • Trade-offs: Fast cache locality, but has a fixed capacity, requiring O(N) resizing overhead when full.

    • 2. Node/List-Based Implementations

  • Stack: Maintain a singly linked list where insertions and deletions happen exclusively at the head node.
  • Queue: Maintain a singly linked list with both head (for dequeues) and tail (for enqueues) references.
  • Trade-offs: Unlimited dynamic growth without resizing spikes, but suffers from cache misses and pointer reference overhead.

    • 4. Visual Comparison of Access Invariants

    Below is the schematic comparison of Stack (push/pop) and Queue (enqueue/dequeue) flows:

    Operation Complexity Profiles

    StructureOperationArray BackingLinkedList Backing
    Stackpush(x)O(1) amortizedO(1) guaranteed
    Stackpop()O(1)O(1)
    Queueenqueue(x)O(1) amortizedO(1) guaranteed
    Queuedequeue()O(1)O(1)

    5. Real-World Applications

  • Markdown Editors: Tracking typing actions in a history stack to support undo (pop) and redo operations.
  • Printer Spoolers: Coordinating print jobs sent by different network computers sequentially.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers verify whether you understand LIFO/FIFO constraints:
  • "Explain when you would choose an array over a linked list to implement a Stack." -> Choose arrays when memory overhead is strict and maximum size is known. Choose lists when allocation limits are highly dynamic.
  • "What is the consequence of not using a Circular Array for queues?" -> Dequeuing requires shifting all remaining elements forward, degrading dequeue operations to O(N) time.

    • Common Mistakes

    Warning: 1. Memory Leakage via Null References: In list-based stacks, forgetting to set orphaned node next pointers to null after pops can keep memory blocks from being garbage collected.
    > 2. Stack Overflow Crash: Failing to define base termination cases during recursive functions results in call stack frames exceeding CPU stack capacity.

    7. Summary

  • LIFO: Stack insertion (push) and deletion (pop) occur at the top index.
  • FIFO: Queue insertion (enqueue) occurs at the rear index; deletion (dequeue) occurs at the front index.
  • Complexity: All insertions/deletions take average O(1) time.
  • Circular Wraps: Essential for array-backed queues to prevent shifting elements.

    • 8. Quiz

    Question 1: What is the benefit of a circular array structure for queues? Answer: It allows index parameters to wrap around to the front of the array once they reach the end (rear = (rear + 1) % capacity), eliminating the need to shift elements forward during dequeue operations. This guarantees O(1) dequeue.
    Question 2: What is the consequence of stack recursion limits? Answer: Every recursive function call pushes a stack frame onto the system call stack. If recursion depth is too deep, the call stack overflow capacity is reached, crashing the program.
    Question 3: Can you implement a Stack using two Queues? What is the lookup complexity? Answer: Yes, by zipping elements back and forth. You keep one queue for elements and use the other as temporary storage. To push, you enqueue to the empty queue, then dequeue all elements of the other queue into it. The push operation is O(N) but lookups remain O(1).
    Question 4: True or False: Accessing the middle element of a Queue is O(1). Answer: False. Queues only permit interaction at the front and rear pointers. To access the middle element, you must dequeue elements sequentially, taking O(N) operations.
    Question 5: Why is checking isEmpty() crucial before popping from a stack? Answer: Attempting to pop or peek from an empty stack triggers a stack underflow exception (or returns null / raises errors), causing execution crashes.