COMPSCI MAR 25TH WED

Attendance

  • Attendance is noted.

Stacks Overview

  • Stacks are a simple data structure used to store ordered items.
  • LIFO (Last In First Out) data structure: the last item added is the first item removed.

Stack Operations

  • Major methods associated with stacks:
    • isEmpty: Checks if the stack is empty.
    • peek: Returns the item on the top of the stack without removing it.
    • pop: Removes and returns the item on the top of the stack.
    • push(item): Adds an item to the top of the stack.
    • size: Returns the number of items in the stack.

Tracing Stack Operations

  • Importance of tracing stack operations to familiarize with the LIFO process.
  • Sample operations performed:
    • Removing duplicates from a collection.
    • Reversing the order of elements in a list.
    • Conversion of numbers from base 10 to another base.

Evaluating Expressions with Stacks

  • Fully Parenthesized Infix Expression: Every operator has a set of parentheses around it.
    • The algorithm processes the expression left to right using stacks for characters and numbers.
    • Algorithm Basics:
      • Initialize a character stack and a double stack.
      • Push numbers onto the double stack and operators onto the character stack.
      • Upon encountering a right parenthesis, pop from the double stack and execute the operation indicated by the operator on the top of the character stack.
      • Continue until the expression is fully evaluated.
    • Uses PEMDAS (Parentheses, Exponents, Multiplication and Division, Addition and Subtraction) to maintain order of operations in evaluation.

Limitations of the Algorithm

  • The algorithm only works on fully parenthesized expressions and will not evaluate non-parenthesized expressions effectively.
  • Future discussions will cover algorithms that can handle non-parenthesized expressions using stacks.

Implementation of Stacks

  • No need to implement stacks from scratch due to previous implementation experience with container classes such as arrays and linked lists.

Array Implementation of Stack:

  • Key components for stack implemented with an array:
    • Data array: Holds the items in the stack.
    • manyItems: Tracks the number of items currently in the stack.
  • Pushing and popping operations:
    • Push:
    • Ensure capacity: If array is full, resize.
    • Place item at data[manyItems] and increment manyItems.
    • Pop:
    • Decrease manyItems, return the item at data[manyItems - 1].
  • Analyze runtime complexities:
    • Push and Pop: Both operations typically O(1) if no resizing is needed.
    • Ensure Capacity: O(n) during array resizing when necessary.

Linked List Implementation of Stack:

  • A linked list is effective for stack implementation since only top element is accessed:
    • Push: Create a new node with the current top linked, then update top to this new node.
    • Pop: Return the top node’s data, shift top pointer to the next node.
  • Advantages of linked lists:
    • Dynamic sizing, no need for capacity handling.
    • All stack operations (push, pop, peek, and size) operate in O(1) time complexity as they involve simple pointer manipulations.

Efficiency Comparison

  • Linked list implementation eliminates the need for methods related to capacity because the size grows and shrinks dynamically.
  • The linked list stack structure simplifies push/pop operations due to direct access to the top of the stack.

Summary of Methods and Their Complexities

  • Array Stack:
    • Cloning: O(n)
    • Size: O(1)
    • isEmpty: O(1)
    • Peak, Pop, Push: O(1)
    • Ensure Capacity: O(n)
  • Linked List Stack:
    • Cloning: O(n)
    • Size: O(1)
    • isEmpty: O(1)
    • Peak, Pop, Push: O(1)

Conclusion and Next Steps

  • Future discussions may involve queues or other data structures.
  • Practical implementation both through queues and stacks utilizing previous concepts learned.
  • Encourage asking questions for clarity and understanding as course progresses.