Introduction To Abstract Data Types (ADT) (Copy)

Definition and Overview

• An Abstract Data Type (ADT) is a conceptual model of a data structure that defines a collection of data along with a set of operations that can be performed on that data.
• ADTs do not specify how the data is stored or how the operations are implemented.
• Examples of ADTs include:
  • Stacks (Last In, First Out – LIFO)
  • Queues (First In, First Out – FIFO)
  • Linked Lists (Nodes pointing to each other)

Common ADTs Covered in This Chapter

1. Stack

• A stack is a collection of elements that follows the Last In, First Out (LIFO) principle.
• The first item added is the last item removed.
• Operations associated with stacks:
  • Push → Adds an item to the top.
  • Pop → Removes an item from the top.
  • Peek (Top) → Retrieves the top item without removing it.
  • isEmpty → Checks if the stack is empty.
  • isFull → Checks if the stack is full (in a fixed-size implementation).
• Example Usage of Stacks:
  • Memory management (e.g., call stack for function calls).
  • Expression evaluation (e.g., postfix notation calculations).
  • Undo/Redo operations in text editors.
  • Backtracking (e.g., in recursive algorithms).

Stack Implementation Using Arrays

• Uses an array to store elements.
• A topPointer keeps track of the last added element.
• When pushing an item:
  • Check if the stack is full.
  • Increment the topPointer.
  • Store the item at stack[topPointer].
• When popping an item:
  • Check if the stack is empty.
  • Retrieve the item at stack[topPointer].
  • Decrement the topPointer.

Stack Implementation Using Linked Lists

• Uses nodes, where each node contains:
  • Data (value stored in the stack).
  • Pointer to the next node.
• The topPointer points to the last added node.
• When pushing, a new node is created and added to the top.
• When popping, the top node is removed, and topPointer is updated.

2. Queue

• A queue is a collection of elements that follows the First In, First Out (FIFO) principle.
• The first item added is the first item removed.
• Operations associated with queues:
  • Enqueue → Adds an item to the back.
  • Dequeue → Removes an item from the front.
  • Peek (Front) → Retrieves the front item without removing it.
  • isEmpty → Checks if the queue is empty.
  • isFull → Checks if the queue is full (in a fixed-size implementation).
• Example Usage of Queues:
  • Printer job scheduling.
  • Buffering in keyboard inputs.
  • Process scheduling in operating systems.

Queue Implementation Using Arrays

• Uses an array to store elements.
• Two pointers track the front (frontPointer) and rear (rearPointer).
• When enqueueing:
  • Check if the queue is full.
  • Increment the rearPointer and store the item.
• When dequeuing:
  • Check if the queue is empty.
  • Retrieve the item at queue[frontPointer].
  • Increment the frontPointer.

Circular Queue (Optimized Array Implementation)

• A circular queue reuses empty spaces when elements are dequeued.
• When the rearPointer reaches the end, it wraps around to the beginning.

Queue Implementation Using Linked Lists

• Uses nodes, where each node contains:
  • Data (value stored in the queue).
  • Pointer to the next node.
• The frontPointer points to the first element.
• The rearPointer points to the last element.
• When enqueueing, a new node is created and added to the rear.
• When dequeuing, the front node is removed, and frontPointer is updated.

3. Linked List

• A linked list is a dynamic data structure where elements (nodes) are linked using pointers.
• Unlike arrays, linked lists do not require contiguous memory and can grow dynamically.
• Each node contains:
  • Data (the actual value).
  • Pointer to the next node.
• The startPointer keeps track of the first node.
• Types of Linked Lists:
  • Singly Linked List → Each node points to the next node.
  • Doubly Linked List → Each node points to both the previous and next nodes.
  • Circular Linked List → The last node links back to the first node.

Linked List Operations

• Insertion:
  • A new node is created and linked to the appropriate position.
  • If inserting at the start, update startPointer.
• Deletion:
  • The node to be removed is located and bypassed in the link.
• Traversal:
  • The list is traversed using pointers to access each node sequentially.

Linked List vs. Arrays

• Example Usage of Linked Lists:
  • Dynamic memory allocation.
  • Managing playlists in media players.
  • Implementing stacks and queues.

Comparison of Stacks, Queues, and Linked Lists

Practical Applications of ADTs

• Stacks:
  • Used in recursion, undo/redo operations, and parsing expressions.
• Queues:
  • Used in scheduling tasks, processing jobs, and managing buffers.
• Linked Lists:
  • Used for managing dynamic data, navigation systems, and adjacency lists in graphs.

Conclusion

• Abstract Data Types (ADTs) are fundamental to efficient data management.
• Stacks, queues, and linked lists are widely used in programming and system design.
• Understanding the operations and implementation of ADTs is crucial for problem-solving in computer science.