CC4 FLecture1 - Stacks

Data Structures and Algorithms: STACKS

Objectives

  • Comprehend the algorithms for:

    • push(x): Insert an item onto the stack.

    • pop(): Remove the most recent item from the stack.

    • top(): View the top item without removing it.

    • isEmpty(): Check if the stack is empty.

  • Understand the basic concepts and architecture of stack data structures.

  • Implement stack data structures using different implementations:

    • Arrays

    • Linked Lists

    • Reverse Strings

    • Balance Parentheses

    • Infix and Postfix structures.

  • Describe relative advantages and disadvantages of stack data structures.

Introduction to Stacks

  • A stack is a Last-In-First-Out (LIFO) data structure where items are added/removed only from the top.

  • Characteristics of Stacks:

    • Depth: Number of elements in the stack. An empty stack has a depth of zero.

    • Homogeneous: All elements are of the same type.

    • Ordered: Elements are in a strict order.

    • Restricted Access: Direct access to elements is not permitted; only the top item can be accessed.

    • The size of a stack may be theoretically unlimited but depends on memory availability.

Stack ADT (Abstract Data Type)

  • A stack can be defined as a list where insertion and deletion occur only at one end, termed the top.

Operations on Stacks

  • Push (x): Adds item x onto the stack. Must check for sufficient capacity to prevent overflow.

  • Pop(): Removes the top item from the stack. Must check if the stack is non-empty to avoid underflow.

  • Top(): Returns the top element on the stack without removing it, also referred to as peek.

  • IsEmpty(): Returns true if the stack is empty, false otherwise. Typically called before popping to avoid underflows.

  • IsFull(): Determines if the stack is full.

  • Create: Initializes an empty stack.

  • Destroy: Removes all elements from the stack and deallocates memory.

Detailed Algorithm for Operations

Algorithm of push()

  1. Check if the stack is full.

  2. If full, produce an error and exit.

  3. If not full, increment the top pointer.

  4. Insert the data element in the current top position.

  5. Return success.

Algorithm of pop()

  1. Check if the stack is empty.

  2. If empty, produce an error and exit.

  3. If not empty, access the data at the top and decrement the top pointer.

  4. Return success.

Implementation of Stacks

Array-based Implementation

  • Simplifies the array-based list, identifying the top position.

  • Efficiency trade-offs:

    • If top is at position 0, each push/pop requires elements to be shifted costing O(n).

    • Appending at the tail can reduce the cost to O(1) for push/pop operations.

  • Detailed Steps:

    • Use an array of a suitable datatype to store stack data.

    • Maintain an index (top) to track the topmost element.

    • Increment and decrement this index when pushing or popping elements.

Linked List Implementation

  • Nodes are linked, allowing dynamic sizing of stacks based on usage.

  • Key aspects:

    • Elements are added/removed from the head of the list.

    • Implementation involves pointers to manage the top node and subsequent memory operations.

Advantages and Disadvantages of Stacks

Advantages:

  • Controlled management of data through the LIFO approach.

  • Local variables within functions that are ephemeral are stored efficiently.

  • Cleanup occurs automatically after function returns without additional deallocation efforts required by users.

Disadvantages:

  • Limited memory for stack allocation leading to potential stack overflow with excessive usage.

  • Random access to stack elements is not possible.

Applications of Stacks

  • Commonly used in:

    • Expression evaluation and parsing (e.g., balancing parentheses).

    • Function call management in programming (activation records).

    • Algorithm implementations like Depth-First Search (DFS).

    • Undo mechanisms in applications (text editors, browser navigation).

Recursion and Stacks

  • Stacks manage the state of recursive function calls efficiently by retaining the return addresses and variables in activation records.

Additional Content

Algebraic Expressions

  • Understanding operands, operators, and different notations like Infix, Postfix, and Prefix is crucial in using stacks for expression evaluation.

Conversion Algorithms

Infix to Postfix Conversion

  • Procedures for efficiently converting expressions.

Evaluation of Postfix Expressions

  • Utilizing stacks for seamless left-to-right evaluation.