Unit 3: Stacks and Queues

I. Foundations of Stacks

A. Introduction to stacks

A stack is a linear data structure in which insertion and deletion occur only at one end, called the top, according to the Last In, First Out (LIFO) principle.

• LIFO rule: The most recently inserted element is removed first; if 10, 20, and 30 are pushed in order, 30 is popped first.
• Top: The variable or pointer TOP identifies the current last element; an empty stack has no valid top element.
• Restricted access: Elements are inserted using PUSH and removed using POP; arbitrary middle insertion or deletion is not a standard stack operation.
• Core operations:
  • PUSH(x) inserts element x.
  • POP() removes and returns the top element.
  • PEEK() or TOP() returns the top element without removing it.
  • isEmpty() checks whether the stack contains no elements.
• Errors: Underflow occurs when popping an empty stack, while overflow occurs when pushing into a full fixed-size stack.
• Complexity: Push, pop, and peek normally require O(1) time.
• Applications: Stacks support function calls, recursion, undo operations, browser history, backtracking, syntax parsing, and expression processing.

II. Stack Representations and Operations

A. List representation of stacks

A list-based stack stores each element in a linked node and keeps a pointer to the node at the top.

• Node structure: Each node contains DATA, the stored value, and NEXT, a pointer to the node below it.
• Top pointer: TOP = NULL represents an empty stack; otherwise, TOP points to the newest node.
• Push linkage: A new node is linked before the current top:
  • Set NEW.NEXT = TOP.
  • Set TOP = NEW.
• Pop linkage: Save TOP, advance TOP to TOP.NEXT, and release the saved node.
• Advantages: Capacity grows dynamically, and overflow occurs only when memory allocation fails.
• Limitations: Every element needs pointer storage, and noncontiguous nodes may have poorer cache performance.
• Cost: Insertion and deletion at the head both take O(1) time.

B. Array representation of stacks

An array-based stack stores elements in consecutive memory locations and uses an integer index to identify the top.

• Representation: For an array STACK[0...N-1], initialize TOP = -1, where N is the capacity.
• Empty condition: TOP == -1.
• Full condition: TOP == N - 1.
• Top element: When nonempty, the current element is STACK[TOP].
• Advantages: Arrays provide compact storage, direct indexing, and strong cache locality.
• Limitation: A fixed array has finite capacity; resizing requires allocating and copying elements.
• Example: After pushing 4, 7, and 9, the array positions 0, 1, and 2 hold those values and TOP = 2.

C. Stack traversal

Stack traversal visits every element, usually from the top downward, without changing the logical contents.

• Array traversal: Visit indices from TOP through 0.
• Linked traversal: Begin at TOP and repeatedly follow NEXT until NULL.
• Order: A stack containing bottom-to-top values A, B, C is traversed as C, B, A.
• Complexity: Visiting n elements takes O(n) time and O(1) auxiliary space.
• Preservation: Traversal should not modify TOP; using repeated pops would destroy the stack unless elements were restored.

for i <- TOP downto 0
    visit STACK[i]

Here, i is the current index and visit processes an element.

D. Push operation

The push operation inserts a new element at the top while preserving LIFO order.

• Array procedure: Check for overflow, increment TOP, and store the value at STACK[TOP].
• Linked procedure: Allocate a node, store the value, point it to the old TOP, and update TOP.
• Invariant: After a successful push, the inserted value is the element returned by the next pop.
• Complexity: Push takes O(1) time; dynamic-array resizing may occasionally take O(n).

PUSH(STACK, x)
    if TOP = N - 1
        report OVERFLOW
    else
        TOP <- TOP + 1
        STACK[TOP] <- x

Here, x is the inserted value and N is the array capacity.

E. Pop operation

The pop operation removes and returns the current top element.

• Array procedure: Check for underflow, save STACK[TOP], decrement TOP, and return the saved value.
• Linked procedure: Save the top node’s data, move TOP to TOP.NEXT, and deallocate the old node.
• Underflow guard: If TOP = -1 for an array or TOP = NULL for a list, no element can be removed.
• Complexity: Pop requires O(1) time.

POP(STACK)
    if TOP = -1
        report UNDERFLOW
    else
        x <- STACK[TOP]
        TOP <- TOP - 1
        return x

Here, x temporarily stores the removed element.

III. Stack-Based Expression Processing

A. Arithmetic expressions

Arithmetic expressions combine operands, operators, and grouping symbols according to precedence and associativity rules.

• Operands: Values or variables such as 8, x, and total.
• Operators: Common binary operators are +, -, *, /, and exponentiation ^.
• Precedence: Parentheses are evaluated first, followed by exponentiation, multiplication or division, and addition or subtraction.
• Associativity: +, -, *, and / are generally left-associative; exponentiation is commonly right-associative.
• Infix form: Operators appear between operands, as in A + B * C.
• Stack role: Operators and parentheses are temporarily stored while parsing or evaluating expressions.

B. Polish notation

Polish notation removes the need for precedence rules and parentheses by fixing each operator’s position relative to its operands.

1. Prefix notation: The operator precedes its operands; infix A + B becomes + A B.
2. Postfix notation: The operator follows its operands; infix A + B becomes A B +.

• Unambiguous structure: Infix (A + B) * C becomes prefix * + A B C and postfix A B + C *.
• Evaluation direction: Prefix is commonly scanned right to left, whereas postfix is scanned left to right.
• Machine suitability: A stack can evaluate either form without searching for parentheses or repeatedly applying precedence rules.

C. Evaluation of expressions

A postfix expression is evaluated by pushing operands and applying each operator to the two most recent values.

• Operand rule: When a number is encountered, push it.
• Operator rule: Pop the right operand first, pop the left operand second, compute left operator right, and push the result.
• Final condition: A valid expression leaves exactly one value on the stack.
• Worked example: For postfix 5 2 3 * +, push 5, 2, 3; apply * to obtain 6; then apply + to obtain 11.
• Complexity: An expression containing n tokens is evaluated in O(n) time using up to O(n) stack space.
• Error detection: Too few operands, division by zero, or multiple remaining values indicate an invalid evaluation.

D. Transformation of expressions

Expression transformation uses an operator stack to convert infix notation into prefix or postfix notation.

• Operand handling: Append each operand directly to the postfix output.
• Operator handling: Before pushing an operator, pop operators having higher precedence, or equal precedence when the incoming operator is left-associative.
• Parentheses handling: Push (; on encountering ), pop to the output until ( is found, then discard the pair.
• Completion: After scanning the expression, pop all remaining operators to the output.
• Example: Infix A + B * C becomes postfix A B C * + because * has higher precedence than +.
• Prefix conversion: One method scans a suitably reversed infix expression, forms postfix, and reverses the result while handling parentheses and associativity carefully.
• Complexity: Each token is pushed and popped at most once, giving O(n) time and O(n) auxiliary space.

IV. Queue Representations and Operations

A. Array representation of queues

An array queue stores elements in indexed locations and tracks removal and insertion positions using FRONT and REAR.

• Linear queue: Insertions advance REAR, while deletions advance FRONT.
• Initial state: A common convention sets FRONT = 0, REAR = -1, and element count COUNT = 0.
• Circular queue: Indices wrap around using modulo arithmetic:
  • Next rear: (REAR + 1) mod N.
  • Next front: (FRONT + 1) mod N.
• Full condition: With a count variable, COUNT = N; the empty condition is COUNT = 0.
• Benefit of circularity: Vacated positions are reused, avoiding false overflow in a linear array queue.

B. List representation of queues

A linked queue uses nodes and maintains pointers to both the first and last elements.

• Pointers: FRONT points to the next node to delete, and REAR points to the newest node.
• Empty state: Both FRONT and REAR are NULL.
• Insertion: Attach the new node after REAR and update REAR.
• Deletion: Remove the node at FRONT and advance FRONT.
• Final-node rule: After deleting the only node, set both pointers to NULL.
• Complexity: Both insertion and deletion take O(1) time.

C. Queue traversal

Queue traversal visits elements from FRONT toward REAR, preserving First In, First Out order.

• Logical order: If 10, 20, and 30 were inserted in sequence, traversal visits 10, 20, 30.
• Linked traversal: Start at FRONT and follow NEXT until NULL.
• Circular-array traversal: Visit COUNT positions, repeatedly using (index + 1) mod N.
• Complexity: Traversing n elements requires O(n) time.
• Non-destructive requirement: Traversal uses temporary indices or pointers rather than repeated deletions.

D. Queue insertion

Queue insertion, also called enqueue, adds an element at the rear.

• Array enqueue: Check whether the queue is full, advance REAR circularly, store the value, and increment COUNT.
• Linked enqueue: Allocate a node; if empty, assign both pointers to it, otherwise connect it after REAR.
• Ordering guarantee: A newly enqueued element is removed only after all previously queued elements.
• Complexity: Enqueue takes O(1) time.

REAR <- (REAR + 1) mod N
QUEUE[REAR] <- x
COUNT <- COUNT + 1

Here, x is the inserted value and N is the capacity.

E. Queue deletion

Queue deletion, also called dequeue, removes and returns the element at the front.

• Array dequeue: Check for underflow, save QUEUE[FRONT], advance FRONT circularly, and decrement COUNT.
• Linked dequeue: Save the front node’s value, advance FRONT, and release the old node.
• FIFO result: Among all current elements, the one inserted earliest is removed first.
• Empty transition: In a linked queue, deleting the last node also sets REAR = NULL.
• Complexity: Dequeue requires O(1) time.

V. Specialized Queues

A. Priority queues

A priority queue removes elements according to priority rather than insertion time alone.

• Ordering rule: In a max-priority queue, the largest priority is removed first; in a min-priority queue, the smallest is removed first.
• Tie handling: Elements with equal priorities may follow FIFO order to provide stable service.
• Implementations:
  • An unsorted array offers O(1) insertion but O(n) deletion of the highest-priority item.
  • A binary heap offers O(log n) insertion and deletion, with O(1) access to the highest-priority item.
• Example: Tasks (A,2), (B,5), and (C,3) leave in the order B, C, A in a max-priority queue.
• Applications: Priority queues support CPU scheduling, shortest-path algorithms, event simulation, and emergency service systems.

B. Deques

A deque, or double-ended queue, permits insertion and deletion at both the front and rear.

1. Input-restricted deque: Insertion is allowed at only one end, but deletion is allowed at both ends.
2. Output-restricted deque: Deletion is allowed at only one end, but insertion is allowed at both ends.

• Core operations: insertFront, insertRear, deleteFront, and deleteRear.
• Implementation: Circular arrays and doubly linked lists support all four operations in O(1) time.
• Relationship to other structures: Restricting operations can make a deque behave as either a stack or a queue.
• Applications: Deques support sliding-window algorithms, palindrome checking, task scheduling, and maintaining recent-history buffers.