Chapter 6 — Data Structures Stack Queue

Data Structure Overview (Stack & Queue)

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. An Abstract Data Type (ADT) describes the behavior (operations and properties) of a data structure without specifying implementation details.

Stack and Queue are simple linear ADTs that differ in the order in which elements are removed:

• Stack follows LIFO (Last In, First Out). The most recently added element is the first to be removed.
• Queue follows FIFO (First In, First Out). The earliest added element is the first to be removed.

Common operations

• Stack: push(element) — insert; pop() — remove and return top; peek()/top() — return top without removing; isEmpty(); isFull() (if fixed capacity).
• Queue: enqueue(element) — insert at rear; dequeue() — remove from front and return; front()/peek() — return front element without removing; isEmpty(); isFull() (if fixed capacity).

Implementations

• Array (fixed or dynamic): use an index (top for stack; front and rear for queue). For queues, a circular buffer (modular arithmetic) avoids wasted space.
• Linked list: dynamic size; for stack push/pop at head; for queue keep pointers to head (front) and tail (rear) to achieve O(1) enqueue and dequeue.

When to use which?

• Use a stack when you need reverse-order processing (e.g., function call management, undo features, expression evaluation).
• Use a queue when you need to preserve arrival order (e.g., scheduling, buffering, breadth-first search).

Complexity (typical)

Primary operations (push/pop/enqueue/dequeue/peek) are O(1) time for both stack and queue in common implementations. Space complexity is O(n) where n is number of stored elements.

Definition (ADT): A stack is an Abstract Data Type (ADT) that stores a collection of elements with two principal operations — push (insert) and pop (remove) — and follows the LIFO (Last-In, First-Out) discipline: the last element pushed is the first to be popped.

Core operations and their semantics:

• create(): Initialize an empty stack (top = -1 for array-based; head = NULL for linked list).
• push(x): Insert element x on top of the stack. Precondition (array): top < capacity - 1. Postcondition: new top points to x.
• pop(): Remove and return the top element. Precondition: stack not empty. Postcondition: top moves down by one.
• peek()/top(): Return the top element without removing it. Precondition: stack not empty.
• isEmpty(): Returns true if stack contains no elements.
• isFull() (bounded stacks): Returns true if stack has reached capacity.
• size(): Number of elements currently in the stack.

Array-based implementation (brief): Use an array A[0..capacity-1] and an integer top initialized to -1. To push: increment top and set A[top] = x. To pop: return A[top] and decrement top. Overflow occurs if top == capacity - 1. Underflow occurs if top == -1.

Linked-list implementation (brief): Use nodes with (data, next). Maintain pointer top (head). To push: create new node, set node.next = top, top = node. To pop: remove node at top, top = top.next, return node.data. Linked representation avoids fixed capacity but uses extra memory per node for pointer.

Example sequence (visual):

Initial: top = -1  (empty)
push(10) -> stack: [10]        top index = 0
push(20) -> stack: [20, 10]    top index = 1
push(30) -> stack: [30, 20, 10] top index = 2
pop()    -> returns 30, stack: [20, 10] top = 1
peek()   -> returns 20, stack unchanged

When to use a stack: Use stacks when you need LIFO order — e.g., reversing data, parsing expressions (infix to postfix), evaluating postfix expressions, managing function calls (call stack), backtracking (undo operations), depth-first search (DFS).

Correctness notes: Always check preconditions before push/pop to avoid overflow or underflow. For array stacks, maintain invariant -1 <= top <= capacity - 1. For linked stacks, ensure proper memory allocation and deletion to avoid leaks.

What is a Stack?

A stack is an abstract data type that follows Last-In-First-Out (LIFO) order. Elements are inserted and removed at one end called the top. Typical operations: push(x) (insert), pop() (remove), peek() or top() (read top), isEmpty() and sometimes isFull().

Two common implementations

1) Array-based (static) implementation

Use a fixed-size array A[0..MAX-1] and an integer top that stores index of the current top element (or -1 when empty).
- Initialization: top = -1 (empty).
- Push: increment top then set A[top] = x; check overflow (top == MAX-1). - Pop: return A[top] then decrement top; check underflow (top == -1).

// Pseudocode (array)
push(x):
  if top == MAX-1: error "Stack Overflow"
  top = top + 1
  A[top] = x

pop():
  if top == -1: error "Stack Underflow"
  val = A[top]
  top = top - 1
  return val

peek():
  if top == -1: error "Stack is empty"
  return A[top]

2) Linked-list (dynamic) implementation

Use a singly linked list where insertion and deletion happen at the head node. Maintain a pointer/reference top to the head. Each node contains data and next. No fixed size; grows until memory exhausted.

// Pseudocode (linked list)
push(x):
  node = new Node(x)
  node.next = top
  top = node

pop():
  if top == NULL: error "Stack Underflow"
  val = top.data
  temp = top
  top = top.next
  delete temp
  return val

peek():
  if top == NULL: error "Stack is empty"
  return top.data

Comparison (advantages & disadvantages)

• Time complexity: both implementations give O(1) for push, pop and peek.
• Space:
  • Array: requires fixed capacity (simple, contiguous memory); risk of overflow if capacity exceeded.
  • Linked list: dynamic size (no fixed limit besides memory), but each element has extra pointer overhead and non-contiguous memory.
• Simplicity: array implementation is simple and cache-friendly; linked-list requires pointers and dynamic memory management.
• Use cases: array stacks are suitable when max size is known; linked-list stacks are preferred when size is unpredictable.

Special conditions

• Stack Underflow: pop or peek when stack is empty (top == -1 for array; top == NULL for linked list).
• Stack Overflow (array-only): push when top == MAX-1.

Memory and performance notes

Array stack uses contiguous memory, yields better locality and slightly faster access due to indexing. Linked-list stack allows unbounded growth (until heap exhaustion) but uses extra memory per node for the next pointer and has more allocation/deallocation overhead.

Definition: A stack is a linear data structure that follows LIFO (Last In, First Out) — the last element pushed is the first popped. Core operations: push (insert), pop (remove), peek/top (read top), isEmpty, and isFull (for bounded stacks).

Implementations: Array-based (fixed or dynamically resized) and linked-list-based (dynamic size). Array implementation uses an index 'top' pointing to the current top element; linked-list uses nodes with a head as top.

Why stacks are useful: They store intermediate state in reverse order of arrival, which is ideal for problems that require undoing steps, nested contexts, or backtracking. Stacks are simple, efficient, and appear in compilers, operating systems, algorithms and everyday software features.

Common applications (short):

• Function call management / Call stack: Each function call creates an activation record pushed on the call stack; on return it is popped. This handles local variables, return address and helps implement recursion.
• Expression evaluation & conversion: Convert infix to postfix/prefix (Shunting-yard algorithm) and evaluate postfix expressions using a stack of operands.
• Balanced parentheses / syntax checking: Push opening brackets and match with closing ones to validate code or expressions.
• Undo/Redo: Maintain history of operations (two stacks often used: undo and redo).
• Browser history (Back/Forward): Back stack and forward stack model user navigation.
• Depth-first search (DFS) & backtracking: Use a stack to manage nodes to visit or decisions to undo.
• Expression parsing & compilers: Parsing states and intermediate code generation use stacks extensively.

Worked example — Postfix evaluation: Evaluate '5 1 2 + 4 * + 3 -'. Algorithm: scan tokens left to right; push numbers; on operator pop operands, apply operator, push result.

Steps (brief): push 5; push 1; push 2; '+' → pop 2,1 → push 3; push 4; '*' → pop 4,3 → push 12; '+' → pop 12,5 → push 17; push 3; '-' → pop 3,17 → push 14. Result = 14.

Worked example — Bracket matching: For expression '{ [ ( ) ] }', push each opening symbol; on encountering a closing symbol, check top for matching opening. If all match and stack empty at end → balanced.

Notes for students: Understand stack invariants (top pointer or head), visualize push/pop as adding/removing from one end, and practice dry-run examples (expression evaluation, DFS, recursion) to internalize behavior.

What is a stack? A stack is a linear abstract data type that follows Last-In-First-Out (LIFO) ordering: the last element pushed is the first one popped. The top of the stack is the end where insertions and deletions occur.

Core operations (typical signatures):

• push(x) — place element x on top
• pop() — remove and return the top element (error if empty)
• peek()/top() — return the top element without removing it
• isEmpty(), isFull() — status checks

Basic concepts:

• Overflow — trying to push into a bounded (fixed-capacity) stack that is full.
• Underflow — trying to pop from an empty stack.
• Top pointer/index — a variable that indicates where the next push/pop happens.
• Locality of reference — array-based stacks have better cache locality than linked stacks.

Variants:

• Array-based (static / bounded) stack

  Uses a contiguous array and an integer top. Capacity fixed at creation. Simple and fast for push/pop but subject to overflow.

• Dynamic / resizable array stack

  Starts with a capacity and doubles (or grows by a factor) when full. Avoids overflow by reallocating; occasional expensive resize but amortized cost is O(1).

• Linked-list stack

  Each element is a node; top points to head node. Push/pop are O(1) and no fixed capacity (limited only by memory). Slightly higher per-element overhead.

• Persistent / immutable stack

  Functional-style stacks where operations return new stacks sharing structure with old ones (useful in functional languages and undo systems).

• Concurrent (thread-safe) stacks

  Provide synchronization (locks or lock-free atomics) so multiple threads can push/pop safely. Variants include mutex-protected stacks and lock-free stacks using compare-and-swap (CAS).

• Specialized stacks
  • Min-stack / Max-stack — supports retrieving current minimum/maximum in O(1) by storing auxiliary info (e.g., paired elements or a second stack of minima).
  • Monotonic stack — maintains elements in increasing/decreasing order to solve problems like nearest greater element efficiently.
• Derived structures using stacks

  Queue using two stacks, expression evaluation with operator and operand stacks, call stack (runtime stack for function calls), parser stacks for nested structures.

Implementation notes / pseudocode:

Array push(x):
  if top == capacity-1: // overflow
    error or resize
  top = top + 1
  A[top] = x

Array pop():
  if top == -1: // underflow
    error
  val = A[top]
  top = top - 1
  return val

Performance:

• Push: O(1) (amortized O(1) if using resizing array)
• Pop: O(1)
• Space: O(n) to store n elements (plus overhead for linked or persistent stacks)

Amortized resizing idea (resizable array doubling): when capacity doubles from C to 2C, the copying cost is O(C) but occurs rarely. Over n pushes starting from small capacity, total extra copying cost ≤ 2n, so amortized cost per push remains O(1).

When to choose which variant:

• Array-based: prefer when max size is known and you want minimal per-element overhead and best performance.
• Resizable array: prefer for general-purpose stacks when you want array benefits without fixed capacity.
• Linked-list: use when elements are frequently inserted/removed and memory fragmentation/overhead is acceptable or when you need true unbounded size without copying.
• Persistent: use in functional setups or when you need cheap snapshots/undo.
• Concurrent: required when multiple threads access the stack; choose lock-free for high-performance low-latency systems when complexity is justified.

Common applications: expression evaluation and conversion (infix/postfix), function-call stack (recursion), undo-redo, browser history (back/forward), syntax parsing (matching brackets), evaluating stock span and monotonic-stack problems.

Definition (ADT): A Queue is an Abstract Data Type (ADT) that stores elements in a First-In-First-Out (FIFO) order. Elements are inserted at one end called rear and removed from the other end called front. The ADT defines behaviour (operations) without specifying implementation details.

Core properties:

• Order: FIFO — the element inserted earliest is removed first.
• Access: Only front and rear positions are directly accessible.
• Implementations: array (linear or circular), linked list.

Basic operations of Queue ADT:

• create() — initialize an empty queue.
• isEmpty() — return true if queue has no elements.
• isFull() — for fixed-size implementations, true if no space remains.
• enqueue(item) — insert item at rear.
• dequeue() — remove and return item from front.
• peek() / front() — return element at front without removing it.
• size() — return number of elements.

Important implementation notes:

• Linear array implementation: advance rear when enqueuing; when elements are dequeued the front index moves forward. A simple linear array can waste space after many dequeues.
• Circular array implementation: treat array as circular so indices wrap around, avoiding wasted space. Use modulo arithmetic to update indices.
• Linked list implementation: maintain pointers to front and rear; enqueue and dequeue both take O(1) time and space grows dynamically.

Pseudo-code (circular array):

create(capacity): front = 0; rear = 0; count = 0; capacity = capacity
isEmpty(): return (count == 0)
isFull(): return (count == capacity)
enqueue(x):
  if isFull() then error 'Queue Full'
  arr[rear] = x
  rear = (rear + 1) % capacity
  count = count + 1

dequeue():
  if isEmpty() then error 'Queue Empty'
  x = arr[front]
  front = (front + 1) % capacity
  count = count - 1
  return x

Time & space complexity:

• Enqueue: O(1)
• Dequeue: O(1)
• Peek/Front: O(1)
• Space: O(n) where n is number of slots/capacity or number of stored nodes (linked list)

Notes: Variants of queues include priority queues, double-ended queues (deques), and circular queues. The ADT focuses on the interface; implementation choice affects memory use and whether the queue has fixed capacity.

A queue is an abstract data type that follows FIFO (first in, first out). Implementations must support primary operations: enqueue (insert at rear), dequeue (remove from front), peek/front, isEmpty and isFull (when capacity bounded). Common implementations are array-based (linear), circular (ring buffer), and linked-list based. Each has trade-offs in simplicity, space use and handling of overflow.

1. Array-based (linear) queue

• Representation: fixed-size array, two indices front and rear (often initialized front = 0, rear = -1).
• Enqueue: increment rear, place element at array[rear]. Dequeue: take array[front], increment front.
• Problems: after several dequeues, front advances and free space at front is wasted unless elements are shifted or indices reset when queue becomes empty.
• Complexities: enqueue O(1), dequeue O(1) if no shifting; if shifting used to reclaim space, shifting can be O(n).

2. Circular queue (ring buffer)

• Representation: fixed-size array with indices front and rear that wrap using modulo arithmetic.
• Index update formula: rear = (rear + 1) % capacity; front = (front + 1) % capacity.
• isFull test (one common convention): (rear + 1) % capacity == front. Alternative: maintain a count variable and test count == capacity.
• Size formula (when using indices only): size = (rear - front + capacity) % capacity + 1 (if using inclusive rear/front convention); if using count variable then size = count.
• Advantages: no wasted space, constant-time operations, ideal for buffers and round-robin scheduling.

3. Linked-list based queue

• Representation: nodes with data and next pointer, with two pointers front and rear for O(1) enqueue and dequeue.
• Enqueue: create new node, set rear.next = new node, rear = new node. Dequeue: remove node at front, set front = front.next.
• Advantages: dynamic size (limited by memory), no fixed capacity or shifting; Deallocation required to avoid memory leaks.
• Complexities: enqueue O(1), dequeue O(1), space O(n) where n is number of elements.

Pseudocode (common)

Array enqueue (circular):
if ( (rear + 1) % capacity == front ) then overflow
else rear = (rear + 1) % capacity
     array[rear] = x
     if front == -1 then front = rear

Array dequeue (circular):
if front == -1 then underflow
else x = array[front]
     if front == rear then front = rear = -1
     else front = (front + 1) % capacity
     return x

Linked-list enqueue:
node = new Node(x)
if rear == NULL then front = rear = node
else rear.next = node; rear = node

Linked-list dequeue:
if front == NULL then underflow
else x = front.data; front = front.next
if front == NULL then rear = NULL
return x

When to use which

• Use circular array when you need a fixed-size, memory-efficient buffer (e.g., I/O buffers, producer-consumer queues).
• Use linked list when queue size is dynamic and unknown or may grow large unpredictably (e.g., task scheduling with variable tasks).
• Simple linear array may be acceptable for short-lived queues or when shifting cost is negligible.

Edge cases & tips

• Always check for underflow (dequeue on empty) and overflow (enqueue on full for bounded queues).
• Decide a convention for full/empty when using indices only: either reserve one cell to differentiate full vs empty, or maintain a count variable.
• For circular queues prefer count variable if you want an easier size calculation; prefer index-only approach to save memory if capacity is strict.

What is a Queue?

A queue is a linear abstract data type that follows FIFO (First-In-First-Out) order: elements are inserted at the rear (enqueue) and removed from the front (dequeue). Queues model real-world waiting lines and are fundamental in algorithms (BFS, scheduling, buffering).

Basic Operations

• enqueue(x): insert element x at rear.
• dequeue(): remove and return element at front.
• front()/peek(): return element at front without removing.
• isEmpty(): true if queue has no elements.
• isFull(): true if queue cannot accept more elements (for fixed-size implementations).
• size(): number of elements currently in queue.

Implementations

• Array-based (linear): maintain front and rear indices. Simple but may run out of space even when there is free room at front unless elements are shifted.
• Circular array (circular queue / ring buffer): indices wrap around using modulo arithmetic. Efficient fixed-size implementation.
• Linked list: front and rear pointers; dynamic size; enqueue and dequeue both O(1).

Common Problems / Edge Cases

• Underflow: dequeue on an empty queue.
• Overflow: enqueue on a full fixed-size queue.
• In circular queues, to distinguish full vs empty you either keep a count variable or reserve one empty slot.

Types and Variants

• Simple (Linear) Queue: FIFO queue implemented in array or list. May require shifting in naive array implementation.
• Circular Queue (Ring Buffer): rear and front wrap around using (index + 1) % capacity. No shifting needed; efficient for fixed capacity.
• Priority Queue: Elements have priorities; dequeue removes element with highest (or lowest) priority rather than FIFO. Typical implementation: binary heap (min-heap or max-heap), using comparator rules.
  • Used where some tasks must be served before others (e.g., OS job scheduling with priorities).
• Deque (Double-Ended Queue): Insert and delete at both ends. Supports operations: insertFront, insertRear, deleteFront, deleteRear. Useful for sliding window problems.
  • Variants: input-restricted deque (insertion allowed at one end only), output-restricted deque (deletion allowed at one end only).
• Double-ended Priority Queue: Supports extracting both min and max efficiently (e.g., implemented via specialized data structures like double heaps).

Time Complexity Summary

• Array-based circular queue: enqueue O(1), dequeue O(1), peek O(1).
• Linked-list queue (with tail pointer): enqueue O(1), dequeue O(1).
• Priority queue (binary heap): insert O(log n), extract-min/max O(log n), peek O(1).
• Deque (doubly linked list or circular buffer): all end operations O(1).

When to Use Which Variant?

• Use simple queue for straightforward FIFO processing (e.g., order processing).
• Use circular queue for fixed-size buffers (e.g., I/O buffers, producer-consumer problems).
• Use priority queue when some items must be served before others based on priority (e.g., task scheduling).
• Use deque for algorithms needing insertion/deletion at both ends (e.g., sliding window minima).

Notes for Implementation (Class 12 focus)

• Show array indices and update front/rear carefully. For circular queue, update as: rear = (rear + 1) % capacity; front = (front + 1) % capacity.
• Check isEmpty and isFull correctly depending on chosen convention (using count or reserved slot).

Definition & property: A queue is a linear abstract data type that follows FIFO (First In First Out) ordering: the first element inserted is the first removed. Core operations are enqueue (insert at rear), dequeue (remove from front), peek/front, isEmpty and isFull (for fixed capacity).

Types of queues:

• Simple (linear) queue — fixed front/rear indices.
• Circular queue — reuses freed space; indices wrap using modulo arithmetic.
• Priority queue — each element has a priority; dequeue returns the highest (or lowest) priority element (not strictly FIFO).
• Deque (double-ended queue) — insertion/removal at both ends.

Implementations: Arrays (with front/rear indices) or linked lists (front and rear pointers). Array implementation can be made efficient using a circular buffer.

Why use queues: Queues model real-world waiting lines and ordered resource processing. They provide constant-time enqueue/dequeue (for linked list or circular array) and maintain strict ordering that many algorithms and systems require.

Common algorithmic use: Breadth-First Search (BFS) in graphs/tree traversals uses a queue to explore nodes level by level. Many simulations and scheduling tasks rely on queues to preserve arrival order.

Practical considerations: For bounded buffers use circular queues to avoid wasted space. For priority-based processing use a priority queue (heap) rather than FIFO. In concurrent systems a queue often requires synchronization (mutexes/locks or lock-free structures) or specialized concurrent queues.

Overview: This topic compares stack and queue ADTs, explains time/space complexity for common implementations (array and linked list), and highlights typical implementation issues and how to avoid them.

• Basic operations:
  • Stack: push(x), pop(), peek()/top(), isEmpty()
  • Queue: enqueue(x), dequeue(), front()/peek(), isEmpty()
• Comparison (conceptual):
  • Stack: LIFO (last-in, first-out). Useful for undo, recursion management, expression evaluation, backtracking.
  • Queue: FIFO (first-in, first-out). Useful for scheduling, breadth-first search, print/call queues.
• Implementations:
  • Array-based: fixed-size array or dynamic array. Simple indexing; must handle overflow or resize.
  • Linked-list-based: nodes with pointers. No fixed capacity (limited by memory); need careful pointer updates and memory management.
• Complexity summary (Big-O):
  • Stack (array or linked list): push — O(1) (amortized O(1) if dynamic resizing), pop — O(1), peek — O(1), space — O(n).
  • Queue (linked list with tail pointer or circular array): enqueue — O(1), dequeue — O(1), peek — O(1), space — O(n).
  • Naive/linear array queue with shifting after dequeue: dequeue becomes O(n) for each shift (avoid this by using circular buffer).
• Amortized complexity:
  • Dynamic array stack: occasional O(n) copy when capacity doubles, but average (amortized) cost of push remains O(1) across many operations.
• Key implementation notes:
  • Use a circular buffer (modulo indexing) for array-based queues to get O(1) enqueue/dequeue without shifting.
  • For linked-list queues, maintain both head and tail pointers for O(1) enqueue and dequeue.
  • Keep a count variable (size) if you need to quickly check empty/full states in circular buffers.

Common issues and fixes:

• Overflow (array full) — either check and reject operation or resize array (double capacity).
• Underflow (pop/dequeue on empty) — always check isEmpty() before popping/dequeuing.
• Circular queue off-by-one / wrong empty/full test — use either a count variable or reserve one slot (full when (rear+1)%cap == front) to distinguish full vs empty.
• Pointer errors in linked list — when dequeuing the last node, set both head and tail to null; ensure deleted nodes are freed (or allow GC).
• Memory leaks — free nodes in manual-memory languages and avoid losing references.
• Incorrect index updates — always use modulo for circular indexes: rear = (rear + 1) % capacity.
• Concurrency issues — for multi-threaded access, use locks or thread-safe queues/stacks (avoid race conditions).

When to choose which implementation:

• Use array (fixed) when capacity is known and you want compact memory layout and fast indexing.
• Use dynamic array (vector) for average O(1) pushes with occasional resizing cost.
• Use linked list when unpredictable size and constant-time insert/delete at ends is required, and pointer overhead is acceptable.