Stacks

Overview

A stack is a dynamic data structure that follows the Last In, First Out (LIFO) principle. This means the last item added to the stack is the first one to be removed. Stacks are commonly used in scenarios such as managing function calls, undoing operations in text editors, and navigating browser history.

Characteristics of a Stack

• Dynamic Data Structure: The size of the stack can grow or shrink dynamically as items are added or removed.
• LIFO Principle: The most recently added item is the first to be removed.

Key Operations

• Push: Adds an item to the top of the stack.
• Pop: Removes the item from the top of the stack.
• Peek: Returns the item at the top without removing it.
• IsEmpty: Checks if the stack is empty.
• IsFull (optional in static implementations): Checks if the stack has reached its maximum capacity.

Use Cases for Stacks

• Function Call Management: Stores return addresses when functions are called.
• Undo Mechanism: Tracks previous actions for easy reversal.
• Expression Evaluation: Converts infix expressions to postfix and evaluates them.
• Depth-First Search (DFS): Tracks visited nodes in a tree or graph traversal.

Implementation of Stacks

Dynamic Implementation Using a Linked List

A stack can be implemented using a linked list, where each node contains the data and a reference to the next node.

CLASS Node
    DATA value
    POINTER next

CLASS Stack
    POINTER top

    METHOD Push(value)
        NEW_NODE ← Node(value)
        NEW_NODE.next ← top
        top ← NEW_NODE

    METHOD Pop()
        IF top IS NULL
            RETURN "Stack Underflow"
        ELSE
            value ← top.value
            top ← top.next
            RETURN value

    METHOD Peek()
        IF top IS NULL
            RETURN "Stack is Empty"
        ELSE
            RETURN top.value

    METHOD IsEmpty()
        RETURN top IS NULL

Static Implementation Using an Array

A stack can also be implemented using a static array with a fixed size.

CLASS Stack
    ARRAY data[size]
    INTEGER top ← -1

    METHOD Push(value)
        IF top = size - 1
            RETURN "Stack Overflow"
        ELSE
            top ← top + 1
            data[top] ← value

    METHOD Pop()
        IF top = -1
            RETURN "Stack Underflow"
        ELSE
            value ← data[top]
            top ← top - 1
            RETURN value

    METHOD Peek()
        IF top = -1
            RETURN "Stack is Empty"
        ELSE
            RETURN data[top]

    METHOD IsEmpty()
        RETURN top = -1

    METHOD IsFull()
        RETURN top = size - 1

Note Summary