Computer Science · College · BCA, BTech & MCA

Stacks, Queues & Recursion: LIFO, FIFO & Expression Parsing

Master Stacks (LIFO) and Queues (FIFO), Circular Queues with modular arithmetic, Infix to Postfix conversion, and Call Stack mechanics in recursive execution.

1Stack Data Structure (LIFO Principle)

Stacks, Queues & Recursion: LIFO, FIFO & Expression Parsing: Subject, Target Audience, Topic Core Full size

Stacks, Queues & Recursion: LIFO, FIFO & Expression Parsing

Master Stacks (LIFO) and Queues (FIFO), Circular Queues with modular arithmetic, Infix to Postfix conversion, and Call Stack mechanics in recursive execution.

  1. 1Subject — Computer Science
  2. 2Target Audience — BCA, BTech & MCA Students
  3. 3Topic Core — LIFO, FIFO, Circular Queues & Call Stack

AStackis a linear data structure adhering to theLast-In, First-Out (LIFO)protocol. The element added most recently is the first to be retrieved. All insertions and removals occur exclusively at one designated end termed thetop.

Core Stack Operations and Complexities

  • push(x)

    Description
    Insert element x onto top of stack
    Array Implementation
    arr[++top]=xarr[++top] = x (check top ==MAX−1\text{top}\ == MAX-1 for overflow)
    Linked List Implementation
    Insert at head (newNode .next=top ;top =newNode \text{newNode}\ .next = \text{top}\ ; \text{top}\ = \text{newNode}\ )
    Time Complexity
    O(1)

  • pop()

    Description
    Remove and return the top element
    Array Implementation
    return arr[top−−]\text{return}\ arr[top--] (check top ==−1\text{top}\ == -1 for underflow)
    Linked List Implementation
    Remove from head (top =top .next\text{top}\ = \text{top}\ .next)
    Time Complexity
    O(1)

  • peek() / top()

    Description
    Inspect value of top element without removal
    Array Implementation
    return arr[top]\text{return}\ arr[top]
    Linked List Implementation
    return top .data\text{return top}\ .data
    Time Complexity
    O(1)

  • isEmpty()

    Description
    Check if stack has zero elements
    Array Implementation
    return top ==−1\text{return top}\ == -1
    Linked List Implementation
    return top ==null \text{return top}\ == \text{null}\
    Time Complexity
    O(1)
python· Python: Validating Balanced Parentheses Using a Stack
def is_balanced(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for ch in s:
        if ch in mapping.values():
            stack.append(ch) # push opening bracket
        elif ch in mapping.keys():
            if not stack or stack.pop() != mapping[ch]:
                return False
    return len(stack) == 0

# Test cases
print(is_balanced("{[()]}")) # True
print(is_balanced("{[(])}")) # False
Output:
True
False

2Queue Data Structure & Circular Queue Architecture

AQueueoperates on theFirst-In, First-Out (FIFO)discipline. Elements enter at therear(enqueue \text{enqueue}\ ) and depart from thefront(dequeue \text{dequeue}\ ).

In a standard linear array queue, dequeuing leaves unused vacant memory in the front that cannot be reused without expensive shifting. ACircular Queueovercomes this limitation by wrapping around usingmodular arithmetic: rear =(rear +1)\text{rear}\ = (\text{rear}\ + 1) % \text{CAPACITY}\ .

Circular Queue State Transitions with Modular Arithmetic

  1. 1

    Initial Empty State

    front =−1,rear =−1\text{front}\ = -1, \text{rear}\ = -1

  2. 2

    Enqueue First Element

    front = 0, rear = 0, arr[0] = item

  3. 3

    Enqueue Subsequent Elements

    rear = (rear + 1) % N, arr[rear] = item

  4. 4

    Full Condition Check

    (rear + 1) % N == front (no vacant slot left)

  5. 5

    Dequeue Element

    item = arr[front]; if front == rear reset to -1 else front = (front + 1) % N

3Infix to Postfix Conversion & Call Stack in Recursion

Computers cannot efficiently evaluate infix arithmetic expressions (A+B∗C)(A + B * C) directly due to operator precedence and parentheses. UsingDijkstra’s Shunting-yard algorithm, stacks convert human-readable infix notation toPostfix (Reverse Polish Notation)(ABC∗+)(A B C * +), which executes in a single linear pass with no backtracking.

Expression Notations Comparison

  • Infix

    Operator Position
    Between operands
    Example Expression
    (A+B)∗(C−D)(A + B) * (C - D)
    Evaluated By
    Human readable, requires precedence rules

  • Prefix (Polish)

    Operator Position
    Before operands
    Example Expression
    ∗+AB−CD* + A B - C D
    Evaluated By
    Right-to-left scan with stack

  • Postfix (RPN)

    Operator Position
    After operands
    Example Expression
    AB+CD−∗A B + C D - *
    Evaluated By
    Left-to-right scan with stack (compilers/calculators)
Exam tip: Recursion is fundamentally powered by the OS runtime Call Stack. Every recursive function invocation creates anActivation Record / Stack Framestoring local parameters, variables, and the return address. If the base case is missing or recursion depth exceeds stack limits, a StackOverflowError \text{StackOverflowError}\ is triggered.

Remember

  • Stacks follow LIFO (push, pop, peek at top in O(1)); Queues follow FIFO (enqueue at rear, dequeue at front in O(1)).
  • Circular Queues utilize modular arithmetic (idx + 1) % N to eliminate memory wastage in array-based FIFO queues.
  • Expression parsing (Infix to Postfix) and syntax validation (matching brackets) are primary applications of stacks.
  • Recursion relies directly on the system call stack; a missing base case results in StackOverflowError.

Check yourself

  1. Question 1

    When converting the infix expression (A+B)∗C(A + B) * C to postfix, what is the resulting postfix expression?

  2. Question 2

    In an array-based circular queue of size N, what condition indicates that the queue is completely full?

Read it? Now test it. Timed exam questions on this topic, then a report on what to revise.

Take a test

Want a lesson on another topic? Type any topic or add a photo of your notes — get a lesson like this in seconds.

Learn a topic

More Computer Science explained