Class Notes: Stacks and Abstract Data Types

Overview of Today's Class

• Focus on stacks and their applications.
• Discuss abstract data types, interfaces, and exceptions.
• Implementation of stacks in Java.
• Amortized analysis and growable stacks.
• Stacks in Java Virtual Machines.

Abstract Data Types (ADT)

• Definition: Specification of instances and axioms defining the semantics of operations on those instances.
• Examples of Data Types: Integers, Real Numbers, etc.
• Operations: Defined through interfaces, specifying signatures, parameters, and results.
• Operations Types:
  • Constructor Operation: Creates an instance of the data type.
  • Access Functions: Access elements of the data type.
  • Manipulation Procedures: Modify the data type.

Importance of Data Types

• Help identify requirements and building blocks of algorithms.
• Provide a higher level of abstraction for discussing algorithms (e.g., stacks, queues).
• Encapsulate the data structure and algorithms, separating correctness and efficiency.

Example: Dynamic Set

• Definition: A set that allows adding/removing elements, defined by methods:
  • new(): Create a new dynamic set.
  • insert(S, V): Insert element V into set S.
  • remove(S, V): Remove element V from set S.
  • contains(S, V): Check if element V is in set S (returns Boolean).
• Axioms: Define expected behavior of operations (e.g., new set is empty).

Stacks

• Definition: Collection of elements with Last In, First Out (LIFO) principle.
• Key Operations:
  • new(): Create a new stack.
  • push(o): Add element o to the top of the stack.
  • pop(): Remove the top element from the stack.
  • top(): Return the top element (without removing it).
  • size(): Return the number of elements in the stack.
  • isEmpty(): Check if the stack is empty.

Axioms Governing Stack Operations

• Pushing an element, then popping should return the same element.
• top() after a push(v) should return v.

Interfaces and Exceptions in Java

• Interface: Declaration of methods without implementation details, separates specification from implementation.
• Exceptions: Mechanism to handle errors in Java. Use throw to signal errors and try/catch blocks to handle them.
• Example: Method eatPizza() throws StomachAcheException if too much pizza is consumed.

Stack Implementation in Java

1. Array Stack:
   • Uses an array to hold stack elements.
   • Operations run in constant time (O(1)).
   • Issues: Fixed size can lead to stack full exceptions.
2. Dynamic Stack:
   • Grows the stack size when full by creating a new array and copying elements.
   • Two growth strategies discussed:
     • Tight Strategy: Increment stack size by a constant c.
     • Growth Strategy: Double the stack size when full.

Amortized Analysis of Stack Growth

• Tight Strategy: May lead to O(n^2) time complexity due to frequent reallocation and copying of elements.
• Growth Strategy: More efficient; leads to O(n) time complexity for n pushes due to exponential growth reducing the number of required reallocations.

Application Example: Stock Prices Span Calculation

• Span Definition: Maximum number of consecutive days price is less than or equal to today's price.
• Goal: Compute span using array P for stock prices and array S for spans.
• Stack Utilization: To optimize the span calculation process by keeping track of indices where previous prices exceeded current prices, allowing faster query on spans.

Conclusion

• Stack implementations can be efficient and flexible through dynamic resizing.
• Understanding abstract data types is crucial for algorithm design.
• Next class will cover queues and linked lists.