bstract Data Types (ADTs)

Abstract Data Types (ADTs) are theoretical models for data types where the behavior is
defined by a set of operations without specifying the implementation details. The List ADT is
a fundamental example.

List ADT

The List ADT defines a collection of elements where each element has a position or index.
The key operations typically include:

 isEmpty(): Checks if the list is empty.

 size(): Returns the number of elements in the list.
 get(index): Retrieves the element at a specified index.
 set(index, element): Updates the element at a specified index.
 add(index, element): Inserts an element at a specified index.
 remove(index): Removes the element at a specified index.

Array-based Implementation

An array-based implementation of a list uses a fixed-size array to store elements. Operations

involve shifting elements to accommodate insertions and deletions.

Linked List Implementations

Singly Linked List

In a singly linked list, each element (node) contains data and a reference (or link) to the next
element in the sequence.

Circular Linked List

A circular linked list is similar to a singly linked list but with its last node pointing back to
the first node instead of null.

Doubly Linked List

In a doubly linked list, each node contains data and references to both the next and previous
nodes, allowing traversal in both directions.

Applications of Lists

Lists are versatile and commonly used for:

 Implementing stacks and queues.

 Managing collections of data where elements can be dynamically added or removed.
 Supporting operations like sorting, merging, and searching efficiently.

Polynomial Manipulation
Polynomials can be represented using lists, where each term (coefficient and exponent pair) is
typically stored in a node of a linked list.

Operations on Lists

Insertion

 Array-based: Requires shifting elements to make room.

 Linked list: Involves updating pointers (next or prev references).

Deletion

 Array-based: Involves shifting elements to fill the gap.

 Linked list: Requires updating pointers to bypass the deleted node.

Merge

 Merging two lists involves combining elements from both lists into a single sorted or
unsorted list, depending on the application.

Traversal

 Traversing a list means visiting each element sequentially:

o Array-based: Iterate over indices.
o Linked list: Follow next pointers until the end of the list.

UNIT-2

Stack ADT

Definition and Operations

Stack Abstract Data Type (ADT):

 Definition: A stack is a Last-In-First-Out (LIFO) data structure where elements are

inserted (pushed) and removed (popped) from the same end, commonly referred to as
the top.

Operations:

1. push(item): Adds an item to the top of the stack.

2. pop(): Removes and returns the item from the top of the stack.
3. peek(): Returns the item from the top of the stack without removing it.
4. isEmpty(): Checks if the stack is empty.
5. size(): Returns the number of elements in the stack.

Applications
  Function Call Stack: Used in programming languages to store information about
active subroutines and function calls.
 Expression Evaluation: Used to evaluate postfix expressions, handle recursion, and
backtrack efficiently.

Evaluating Arithmetic Expressions

Conversion of Infix to Postfix Expression

Infix: Traditional arithmetic notation where operators are placed between operands, e.g., a +
b * c.

Postfix (Reverse Polish Notation, RPN): Operators follow their operands, e.g., a b c * +.

Steps to Convert Infix to Postfix:

1. Operator Precedence: Establish operator precedence rules (* and / higher than + and
-).
2. Using a Stack: Use a stack to hold operators and manage their precedence.
3. Conversion Algorithm:
o Scan the infix expression from left to right.
o If an operand (variable or constant) is encountered, add it directly to the
postfix output.
o If an operator is encountered:
 Pop operators from the stack to the output until an operator with lower
precedence is encountered or the stack is empty.
 Push the current operator onto the stack.
o After scanning, pop all operators from the stack to the output.

Example

Convert a + b * c to postfix:

 Steps:
o Start with an empty stack and output.
o Scan a + b * c:
 a (operand) goes to output.
 + (operator) goes to stack.
 b (operand) goes to output.
 * (operator) has higher precedence than +, so push to stack.
 c (operand) goes to output.
o After scan, pop operators from stack to output: * +.
o Result: a b c * +.

Queue ADT

Definition and Operations

Queue Abstract Data Type (ADT):

  Definition: A queue is a First-In-First-Out (FIFO) data structure where elements are
inserted at the rear (enqueue) and removed from the front (dequeue).

Operations:

1. enqueue(item): Adds an item to the rear of the queue.

2. dequeue(): Removes and returns the item from the front of the queue.
3. peek(): Returns the item from the front of the queue without removing it.
4. isEmpty(): Checks if the queue is empty.
5. size(): Returns the number of elements in the queue.

Circular Queue

 Circular Implementation: Uses a fixed-size array where the rear can wrap around to
the front, optimizing space usage and providing efficient enqueue and dequeue
operations.

Priority Queue

 Definition: Extends the queue concept by assigning a priority level to each element.
Elements with higher priority are dequeued before those with lower priority.
 Operations: Typically include insert_with_priority(item, priority) and
extract_highest_priority().

Applications of Queues

 Buffer Management: Used in operating systems to manage I/O buffers and

scheduling of tasks.
 Simulation Systems: Queues model waiting lines in simulations such as traffic flow,
customer service, and manufacturing processes.

Conclusion

Understanding the operations and applications of Stack and Queue ADTs is crucial in
designing efficient algorithms and data structures. From managing function calls and
expression evaluation using stacks to modeling real-world scenarios and managing priorities
with queues, these ADTs provide foundational tools for a wide range of computational tasks
and problem-solving applications.