Stacks, Queues & Custom Dictionary-Based ADTs

Abstract Data Types (ADTs) – General Concepts

  • User-Defined Data Abstractions
    • Allow programmers to create domain-specific data structures beyond built-in types.
    • Provide interfaces (constructors, selectors, mutators, predicates) that hide the underlying representation.
  • Tagged (Labeled) Data
    • Use a tag (often a string in index 0 of a tuple) to mark what kind of object a value is.
    • Enables data-directed dispatch: operations first inspect the tag, then send the request to the proper code path for that type.
    • Encourages defensive programming:
    • Perform explicit type checks before mutating/inspecting a structure.
    • Raise informative exceptions to fail gracefully when a wrong type is supplied.
  • Common Interface Vocabulary
    • Constructor: procedure that builds a fresh instance (e.g., makeQueue).
    • Selector: reads data without changing state (e.g., front).
    • Mutator: changes internal state (e.g., enqueue).
    • Predicate: asks a Boolean question (e.g., isQueueEmpty).
  • Representation Choice
    • Once the constructor chooses a representation, all other operations must be consistent with that choice.
    • In examples below, a tuple (tag, list_contents) serves as the concrete rep for both stacks and queues.

Queue ADT (First-In, First-Out)

  • Semantics
    • Maintains FIFO ordering.
    • Real-world & algorithmic uses:
    • Graph traversal (Breadth-First Search).
    • Game search (Iterative Deepening variations).
    • Event handling / task scheduling.
  • Interface Summary
    • Constructors: makeQueue : void \to Queue.
    • Mutators:
    • enqueue : (Queue<A>, A) \to void (add to back).
    • dequeue : (Queue<A>) \to void (remove from front).
    • Selectors: front : Queue<A> \to A (peek at front element).
    • Predicates:
    • isQueueEmpty : Queue<A> \to Bool.
    • isQueue : Any \to Bool (type check).
  • Basic (unsafe) implementation skeleton
  def makeQueue():
      return ('queue', [])

  def contents(q):
      return q[1]

  def enqueue(q, el):
      contents(q).append(el)      # add to back

  def dequeue(q):
      contents(q).pop(0)          # remove from front

  def front(q):
      return contents(q)[0]

  def isQueueEmpty(q):
      return contents(q) == []

  def isQueue(obj):
      return type(obj) == type(()) and obj[0] == 'queue'
  • Safer (defensive) variants
    • Every public function checks isQueue and emptiness before mutation or selection.
    • Errors:
    • TypeError("enqueue : Not a Queue") when wrong type.
    • IndexError("Queue is Empty") when dequeuing empty queue.
  • Alternative Back/Front Choice
    • Could instead store front at list tail:
    • enqueue inserts at index 0.
    • dequeue pops last element.
    • front returns last element ([-1]).
    • Demonstrates representation change requires coherent updates to every operation.
  • Interactive Example
  >>> q = makeQueue()
  >>> enqueue(q, 5); enqueue(q, 3); enqueue(q, 7)
  >>> q
  ('queue', [5, 3, 7])
  >>> front(q)
  5
  >>> dequeue(q)
  >>> front(q)
  3

Stack ADT (Last-In, First-Out)

  • Semantics
    • Maintains LIFO ordering (push/pop at same end).
    • Typical applications:
    • Parsing & expression evaluation.
    • Graph traversal (Depth-First Search).
    • Function call/return (recursion stack).
    • Game backtracking.
  • Interface Summary
    • Constructors: makeStack : void \to Stack.
    • Mutators:
    • push : (Stack<A>, A) \to void.
    • pop : (Stack<A>) \to void.
    • Selector: top : Stack<A> \to A.
    • Predicates:
    • isStackEmpty : Stack<A> \to Bool.
    • isStack : Any \to Bool.
  • Chosen Representation – top at front of list
  def makeStack():
      return ('stack', [])

  def contents(s):
      return s[1]

  def push(s, el):
      contents(s).insert(0, el)   # front = top

  def pop(s):
      contents(s).pop(0)

  def top(s):
      return contents(s)[0]

  def isStack(obj):
      return type(obj) == type(()) and obj[0] == 'stack'

  def isStackEmpty(s):
      return contents(s) == []
  • Safe wrappers mirror the queue’s defensive style.
  • Alternate Representation – top at back (append, pop(), [-1]).
  • Demonstration
  >>> s1 = makeStack()
  >>> push(s1, 5); push(s1, 3); push(s1, 7)
  >>> s1
  ('stack', [7, 3, 5])
  >>> top(s1)
  7
  >>> pop(s1)
  >>> top(s1)
  3

Aliasing & Mutation Pitfalls

  • Aliasing: two variables reference the same mutable object.
  >>> s1 = makeStack()
  >>> push(s1, 3); push(s1, 5)
  >>> s2 = s1           # no copy, just another alias
  >>> push(s1, 7)
  >>> top(s2)           # reflects change made through s1
  7
  • Surprise factor: Mutations through one alias affect all.
  • Practical guidance:
    • Use pure (immutable) data when possible.
    • When mutation is required, document aliasing expectations or provide explicit copy operations.

Additional Example ADTs (Dictionary-Based)

Big Cats ADT
  • Purpose: store biological and conservation info for large felines.
  • Representation: Python dict with keys:
    • "species", "scientific_name", "habitat" (list), "diet" (list), "weight_range_kg" (tuple), "lifespan_years", "conservation_status".
  • Interface
    • Constructor: create_big_cat(...) -> dict (fills all attributes).
    • Mutators: update_conservation_status, add_habitat, add_diet_item (each returns the mutated dict).
    • Selectors: get_big_cat_summary, get_big_cat_species.
    • Predicate: compare_big_cats(cat1, cat2) -> bool (same species?).
  • Real-world relevance: Supports wildlife databases & conservation apps.
Car ADT
  • Representation: dict with keys make, model, year, mileage, fuel_type, color, features (list).
  • Operations
    • Constructor: create_car.
    • Mutators: update_mileage, change_color, add_feature.
    • Selectors: get_car_mileage, get_car_color, get_car_year.
    • Predicate: is_car(car) type check.
  • Practical angle: Could back a rental-fleet management system.
Movie ADT
  • Representation: dict with title, genre (list), director, release_year, rating (float), cast (list), duration (int).
  • Operations
    • Constructor: create_movie.
    • Mutators: update_rating, add_genre, add_cast_member.
    • Selector: get_movie_summary (formatted description).
    • Predicate: compare_movies(movie1, movie2) (same title & year?).
  • Use case: online streaming catalog or personal media library.

Defensive Programming & Ethical/Practical Implications

  • Fail-fast philosophy: detect misuse immediately, not silently corrupt data.
    • Raises TypeError when a function receives incompatible objects.
    • Raises IndexError for underflow (dequeue/pop on empty structures).
  • Maintainability: Clear ADT boundaries reduce bugs during refactoring; representation can change without breaking external code.
  • Extensibility: Tagged data & data-directed dispatch allow open sets of types—new tags can be introduced with new operations without editing old code.
  • Ethical aspect: Accurate error messages help learners & colleagues avoid confusion, improving accessibility and reducing frustration.