0.3 by Qwen

Chapter 1: Applications of Abstract Data Types (ADTs)

Abstraction and Design Principles

Definition

• Abstraction: Distilling a complicated system down to its most fundamental parts and describing them in simple, precise language.
• Abstract: Existing in thought but without concrete existence.
• Encapsulation: Grouping of code and hiding internal implementation details (information hiding).
• Modularity: Organizing software into separate functional units.

Causes

• Not specified in notes

Goals / Objectives

• Allow users to focus on the “big picture” rather than implementation details.
• Enable developers to modify class implementations without affecting users.
• Maintain a clear contract (interface) between components.
• Organize complex software systems into manageable, interacting units.

Importance

• Supports reusability and maintainability of code.
• Keeps interactions between system components clear and well-organized.
• Essential for managing complexity in modern software systems.
• Foundational to both procedural and object-oriented programming paradigms.

Procedures

• Provide a layer over basic functionality that hides implementation.
• Define interfaces that specify operations without revealing how they are performed.
• Divide system components into modules with defined responsibilities.

Advantages & Disadvantages

• Advantages:
  • Programmer has freedom in implementing internal details.
  • Easier to maintain and update code without breaking dependent components.
  • Promotes code reuse and modularity.
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Improves software design quality and long-term maintainability.
• Enables collaborative development by clearly defining component boundaries.

Examples

• Integer.parseInt() – user calls the method without knowing internal parsing logic.
• Human vs. Integer: abstraction allows thinking of “integer” as a concept separate from its memory representation (e.g., value 65 stored as bits).

---

Abstract Data Types (ADTs)

Definition

• An ADT is a type conceived apart from concrete reality.
• Consists of data with certain characteristics and a set of operations to manipulate that data.
• The implementation of an ADT is called a data structure.

Causes

• Not specified in notes

Goals / Objectives

• Provide a high-level view of data organization and allowed operations.
• Separate what an ADT does from how it does it.

Importance

• Forms the foundation for reusable and modular code.
• Enables reasoning about data behavior without implementation distractions.

Procedures

• Define data characteristics and permissible operations.
• Implement using constructs and primitive data types (as data structures).

Advantages & Disadvantages

• Advantages:
  • Reusability
  • Maintainability
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Facilitates the design of complex software through well-defined data interfaces.

Examples

• Integer
• Double
• String
• Fraction
• Counter

---

Collection ADTs

Definition

• A general term for an ADT that contains a group of objects.
• Linear collections store entries in a linear sequence (e.g., List, Stack, Queue).
• Collections may or may not allow duplicates and may or may not maintain order.

Causes

• Not specified in notes

Goals / Objectives

• Organize multiple objects into a single manageable unit.
• Support specific access, insertion, and removal patterns based on use case.

Importance

• Fundamental to modeling real-world groupings (e.g., task lists, customer queues).
• Different collection types enable efficient solutions to different problem types.

Procedures

• Entries are added, removed, or accessed according to collection-specific rules.
• Linear collections differ in restrictions on how entries may be manipulated.

Advantages & Disadvantages

• Advantages:
  • Tailored behavior for specific application needs (e.g., LIFO, FIFO, unrestricted access)
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Choice of collection ADT directly affects algorithm efficiency and correctness.

Examples

• List: task lists, playlists, marathon runner registration
• Stack: reversing strings, checking palindromes, program call stack
• Queue: print queues, customer service lines, round-robin CPU scheduling

---

Lists

Definition

• A linear data structure storing an ordered collection of elements.
• A linear collection where entries may be added, removed, and searched without restriction.
• Can be unordered (default) or sorted (covered later).

Causes

• Not specified in notes

Goals / Objectives

• Store and manage sequences of data where position matters.
• Allow flexible access and modification at any index.

Importance

• One of the most versatile and commonly used collection types.
• Supports applications requiring dynamic, indexed storage.

Procedures

• Basic operations:
  • add(e): Insert element at end
  • remove(i): Remove and return element at position i
  • get(i): Return element at position i (no removal)
  • isEmpty(): Check if list is empty
  • clear(): Remove all elements

Advantages & Disadvantages

• Advantages:
  • Flexible insertion and access
  • Supports duplicates and arbitrary ordering (in unordered lists)
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Enables modeling of real-world sequences like shopping lists or registration records.

Examples

• Shopping list app
• Marathon runner registration system
• High-precision arithmetic (using lists to represent very long integers)

---

Stacks

Definition

• A collection following the Last-In, First-Out (LIFO) principle.
• Linear collection where entries can only be removed in reverse order of insertion.
• Typically does not support searching.

Causes

• Not specified in notes

Goals / Objectives

• Enforce LIFO processing order.
• Support operations that require reversal or nesting (e.g., matching brackets).

Importance

• Critical for managing nested or hierarchical processes.
• Mirrors real-world behaviors like call stacks in programs.

Procedures

• Basic operations:
  • push(e): Insert element at top
  • pop(): Remove and return top element
  • peek(): Return top element without removal
  • isEmpty(): Check if stack is empty
  • clear(): Remove all elements
• Used in algorithms like:
  • String reversal: push all chars, then pop to reverse
  • Bracket matching: push open brackets, pop and match on close brackets
  • Postfix expression evaluation: push operands, apply operators to popped values

Advantages & Disadvantages

• Advantages:
  • Simple and efficient for LIFO scenarios
  • Natural fit for recursive-like processes
• Disadvantages:
  • Limited access (only top element)
  • Not suitable for FIFO or random-access needs

Impact / Effect

• Enables correct parsing of nested structures (e.g., code syntax).
• Underlies program execution via the system/program stack.

Examples

• Reversing a string
• Checking for balanced brackets: {[()]} (balanced) vs. {[(])} (unbalanced)
• Program stack: stores activation records (arguments, local variables, return addresses) for method calls
• Palindrome checking
• Postfix expression evaluation (e.g., a b + c /)

---

Queues

Definition

• A collection following the First-In, First-Out (FIFO) principle.
• Elements enter at the rear and are removed from the front.
• Linear collection where entries are removed in the same order they were added.
• Typically does not support searching.

Causes

• Not specified in notes

Goals / Objectives

• Model real-world waiting lines and fair resource allocation.
• Ensure chronological processing of requests.

Importance

• Essential for simulating real-world queuing systems.
• Supports fairness and order preservation in processing.

Procedures

• Basic operations:
  • enqueue: Add entry to rear
  • dequeue: Remove entry from front
  • getFront: Retrieve (not remove) front entry
  • isEmpty(): Check if queue is empty
  • size(): Return number of entries
• Used in:
  • Round-robin CPU scheduling: cycle through processes
  • Share profit calculation: sell shares in purchase order (FIFO)

Advantages & Disadvantages

• Advantages:
  • Ensures fairness and order
  • Matches natural real-world queuing behavior
• Disadvantages:
  • Not specified in notes

Impact / Effect

• Directly influences customer satisfaction and system efficiency in service simulations.
• Enables accurate financial modeling (e.g., FIFO share sales).

Examples

• Print queues
• Customer service lines (e.g., Post Office number system)
• Round-robin schedulers for CPU time allocation
• Simulation of waiting lines for business analysis
• Share portfolio tracking: buying shares added to queue, selling removes oldest first

---

Comparative Applications of Stack vs. Queue

Definition

• Choosing between stack (LIFO) and queue (FIFO) based on access pattern required by the application.

Causes

• Not specified in notes

Goals / Objectives

• Select the appropriate ADT that matches the temporal logic of the problem.

Importance

• Using the wrong ADT leads to incorrect behavior or inefficient solutions.

Procedures

• Analyze whether the problem requires:
  • Reversal or nesting → use stack
  • Chronological order or fairness → use queue

Advantages & Disadvantages

• Advantages:
  • Correct ADT choice leads to simple, correct algorithms
• Disadvantages:
  • Misapplication causes logical errors

Impact / Effect

• Determines correctness of applications like undo features or browser history.

Examples

• Web browser page-visited history: Stack – “Back” button revisits most recent page first (LIFO)
• Access to shared resources (e.g., printer): Queue – ensures fair, first-come-first-served access (FIFO)
• Undo sequence in text editor: Stack – last action undone first (LIFO)