Linear DS

Stack & Queue

Restricted access lists implementing LIFO and FIFO retrieval behaviors.

What is Stack & Queue?

Stacks and Queues are fundamental linear data structures that restrict how elements are added and removed. A Stack follows the Last-In-First-Out (LIFO) principle, where elements are inserted (push) and removed (pop) from the same end (top). A Queue follows the First-In-First-Out (FIFO) principle, where elements are inserted (enqueue) at the rear and removed (dequeue) from the front.

Key Characteristics:

  • Stack: Last-In-First-Out (LIFO) model
  • Queue: First-In-First-Out (FIFO) model
  • Push/Enqueue adds elements to the structure
  • Pop/Dequeue removes elements in order

Complexity Analysis

Avg Time Complexity: O(1) for Push, Pop, Enqueue, and Dequeue
Space Complexity: O(n) capacity storage
Best Case: O(1) (standard operations)
Worst Case: O(1) (standard operations)

How it Works Step-by-Step

  1. Stack Push: Increment top pointer and place element at stack[top].
  2. Stack Pop: Retrieve element at stack[top], then decrement top pointer.
  3. Queue Enqueue: Add element to rear index, updating rear pointer.
  4. Queue Dequeue: Retrieve element from front index, updating front pointer.

Code Implementation

Worked Trace Example

Pushing 10, then 20 onto a Stack: Stack contains [10, 20] (top).
Popping from Stack: removes 20. Stack contains [10].

Enqueueing 10, then 20 into a Queue: Queue contains [10 (front), 20 (rear)].
Dequeueing from Queue: removes 10. Queue contains [20].