Stacks & Queues
Implement stacks and queues in C using arrays and linked lists — understand LIFO/FIFO principles and solve classic problems.
50 min•By Priygop Team•Last updated: Feb 2026
Stack Implementation
- Array-based Stack: Fixed size array with top index. push: items[++top] = value. pop: return items[top--]. peek: return items[top]. Check overflow/underflow
- Linked List Stack: Dynamic size, no overflow. push: insert at head (O(1)). pop: remove head (O(1)). Each node is malloc'd — slower due to allocations but no size limit
- Applications: Function call stack (recursion), undo/redo operations, expression evaluation, balanced parentheses checking, browser back button
- Infix to Postfix: Use operator stack — push operators, pop when precedence is lower. Numbers go directly to output. Parentheses control precedence
- Postfix Evaluation: Push numbers to stack. On operator, pop two operands, apply operator, push result. Final stack value is the answer
- Two Stacks in One Array: Use one array, grow stacks from opposite ends — stack1 grows from index 0 up, stack2 grows from index n-1 down
Queue Implementation
- Array-based Queue (Circular): front and rear indices. Enqueue: items[rear] = value, rear = (rear+1) % SIZE. Dequeue: return items[front], front = (front+1) % SIZE
- Linked List Queue: Maintain head (front) and tail (rear) pointers. Enqueue: add at tail O(1). Dequeue: remove from head O(1). Dynamic size
- Priority Queue: Elements have priorities — highest priority is dequeued first. Implement with sorted array, unsorted array, or binary heap (most efficient)
- Deque (Double-Ended Queue): Insert and delete from both ends — front and rear. Array-based or linked list. Used in sliding window problems
- Applications: CPU scheduling (round-robin), BFS graph traversal, print job spooling, message queues, buffering in I/O operations
- Implement Queue using Two Stacks: Stack1 for enqueue (push). Stack2 for dequeue (if empty, transfer all from Stack1). Amortized O(1) per operation