Unit II LISTS, STACKS AND QUEUES

Abstract Data Type (ADT) – The List ADT – The Stack ADT: Definition, Array representation of
stack, Operations on stack: Infix, prefix, and postfix notations Conversion of an arithmetic
Expression from Infix to postfix. Applications of stacks. The Queue ADT: Definition, Array
representation of queue, Types of queues: Simple queue, circular queue, double ended queue
(de-queue) priority queue, operations on all types of Queues.

Abstract Data Types (ADTs)

●​ Core Idea:
○​ An ADT is a high-level description of a data type, focusing on what it does, not
how it's done.
○​ It's a conceptual model that defines the behavior of a data type in terms of its
operations and their properties.
○​ Think of it as a blueprint or specification.
●​ Key Components:
○​ Data: The type of information the ADT holds.
○​ Operations: The actions that can be performed on the data.
○​ Behavior: The rules and constraints that govern how the operations work.
●​ Abstraction:
○​ ADTs are built on the principle of abstraction, separating the interface (what you
can do) from the implementation (how it's done).
○​ Users of an ADT interact with it through its defined operations, without needing to
know the internal details.
●​ Benefits:
○​ Modularity: ADTs promote modular design, making code easier to organize and
maintain.
 ○​ Information Hiding: Implementation details are hidden, allowing for changes
without affecting users.
○​ Reusability: ADTs can be used in various parts of a program or in different
programs.
○​ Clarity: ADTs provide a clear and concise way to define data types.
●​ Examples:
○​ Stack:
■​ Data: A collection of items.
■​ Operations: push (add), pop (remove), peek (view top), isEmpty.
■​ Behavior: Last-In, First-Out (LIFO).
○​ Queue:
■​ Data: A collection of items.
■​ Operations: enqueue (add), dequeue (remove), front (view front),
isEmpty.
■​ Behavior: First-In, First-Out (FIFO).
○​ List:
■​ Data: A collection of items.
■​ Operations: insert, delete, search, get.
■​ Behavior: items are ordered.
○​ Map (Dictionary):
■​ Data: key value pairs.
■​ Operations: insert, delete, find.
■​ Behavior: Keys are unique.
●​ Implementation:
○​ ADTs can be implemented using various underlying data structures and
programming techniques.
○​ The choice of implementation is hidden from the user.

The List ADT (Abstract Data Type)

🔹 Introduction to List ADT
●​ A List ADT is an ordered collection of elements where elements can be inserted,
deleted, or accessed based on their position.
●​ Lists can have duplicate elements and can be implemented using arrays or linked lists.
●​ The size of a list can be dynamic (if implemented using a linked list) or fixed (if
implemented using an array).

🔹 Properties of List ADT

1.​ Ordered Collection – Elements are stored in a specific order.
 2.​ Dynamic Size – The size can change in a linked list, but in an array-based list, it is fixed.
3.​ Duplicate Elements – Lists can store multiple occurrences of the same value.
4.​ Indexing – Each element can be accessed using an index (in an array).
5.​ Insertion & Deletion – Elements can be inserted or deleted at any position.

🔹 Basic Operations on List ADT

1.​ Insertion – Adding an element at a specific position.
2.​ Deletion – Removing an element from a specific position.
3.​ Traversal – Visiting each element in the list.
4.​ Searching – Finding an element in the list.
5.​ Updation – Modifying an element at a specific position.

🔹 Representation of List ADT

1️⃣ Array Representation of List ADT

●​ In an array-based list, elements are stored in contiguous memory locations.

●​ Advantages: Fast access to elements using an index (O(1) time complexity).
●​ Disadvantages: Insertion and deletion can be slow because shifting elements is
required (O(n) time complexity).

2️⃣ Linked List Representation of List ADT

●​ A linked list is a dynamic data structure consisting of nodes.

●​ Each node contains:
1.​ Data (the value)
2.​ Pointer to the next node
●​ Linked lists are memory-efficient and allow fast insertions and deletions.

Applications of List ADT

1.​ Database Management Systems – Storing records in a sequential manner.
2.​ Contact Lists & Playlists – Maintaining ordered data.
3.​ Undo/Redo Operations – Implementing history tracking in software.
4.​ Task Scheduling – Managing tasks in operating systems.

📌 Diagram: Array vs. Linked List Representation

Array-Based List
Linked List

Stack ADT (Abstract Data Type)

🔹 Stack: Definition and Array Representation

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
 ●​ The last element inserted is the first one to be removed.
●​ It is used for operations like function calls, expression evaluation, and backtracking.

📌 Array Representation of Stack

●​ A stack can be implemented using an array where:
○​ A top variable keeps track of the index of the last inserted element.
○​ Push operation inserts an element at top + 1.
○​ Pop operation removes the element at top.
○​ Overflow occurs when top reaches the maximum size.
○​ Underflow occurs when top = -1 (stack is empty).

✅ Pros: Simple and fast (O(1) for push & pop)​

❌ Cons: Fixed size (in array implementation)
🔹 Operations on Stack
1.​ Push (Insertion) – Adds an element to the top.
2.​ Pop (Deletion) – Removes the top element.
3.​ Peek (Top element access) – Returns the top element without removing it.
4.​ isEmpty() – Checks if the stack is empty.
5.​ isFull() – Checks if the stack is full.
🔹 Infix, Prefix, and Postfix Notations
Expressions can be written in three different notations:

1.​ Infix Notation – Operators are placed between operands.

○​ Example: A + B
2.​ Prefix Notation (Polish Notation) – Operators are placed before operands.
○​ Example: + A B
3.​ Postfix Notation (Reverse Polish Notation) – Operators are placed after operands.
○​ Example: A B +

🔸 Why Use Postfix Notation?

●​ No need for parentheses to indicate precedence.
●​ Can be easily evaluated using a stack.

🔹 Conversion: Infix to Postfix

Algorithm to Convert Infix to Postfix

1.​ Scan the infix expression from left to right.

2.​ If the symbol is an operand, add it to the output.
3.​ If the symbol is an operator:
○​ While the stack is not empty and the top has higher precedence, pop and add to
output.
○​ Push the current operator onto the stack.
4.​ If the symbol is '(', push it onto the stack.
5.​ If the symbol is ')', pop from stack and add to output until '(' is found.
6.​ At the end, pop all remaining operators from the stack.

🔹 Applications of Stack
1.​ Expression Evaluation (Postfix, Prefix)
2.​ Function Calls (Recursion uses stack internally)
3.​ Undo/Redo Operations in Editors
4.​ Backtracking (Maze solving, DFS in graphs)
5.​ Memory Management (Handling function calls in RAM

Queue ADT (Abstract Data Type)

🔹 Definition of Queue
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.

●​ The first element inserted is the first one to be removed.

●​ It has two ends:
○​ Front → Points to the first element.
○​ Rear → Points to the last element.

✅ Real-life Examples:
●​ Queue in a ticket counter – The first person in the queue is served first.
●​ Print Queue – The first document sent for printing is printed first.

🔹 Array Representation of Queue

A queue can be implemented using an array where:

●​ Front keeps track of the first element.

●​ Rear keeps track of the last element.
●​ Enqueue (Insertion) happens at the rear.
●​ Dequeue (Deletion) happens at the front.

🔹 Applications of Queue
1.​ CPU Scheduling (Round Robin Algorithm).
2.​ Printer Queue (First document gets printed first).
3.​ Network Packet Handling (Data transmission uses queues).
4.​ Breadth-First Search (Graph traversal).
Types of Queues and Their Operations
🔹 1. Simple Queue (Linear Queue)

A simple queue follows the FIFO (First In, First Out) principle.

●​ Insertion (Enqueue) happens at the rear.

●​ Deletion (Dequeue) happens from the front.
●​ Problem: After multiple deletions, unused spaces cannot be reused without shifting
elements.

🔹 2. Circular Queue

A circular queue solves the problem of wasted space in a simple queue by connecting the
end to the beginning.

●​ Rear wraps around when it reaches the last position.

●​ More efficient than a simple queue.

🔹 3. Double-Ended Queue (Deque)

A deque (double-ended queue) allows insertion and deletion from both front and rear.
 ●​ Types of Deques:
○​ Input-Restricted Deque: Insertion at only one end, deletion from both.
○​ Output-Restricted Deque: Deletion at only one end, insertion from both.

📌 Deque Operations
●​ enqueueFront(value): Inserts an element at the front.
●​ enqueueRear(value): Inserts an element at the rear.
●​ dequeueFront(): Removes an element from the front.
●​ dequeueRear(): Removes an element from the rear.

🔹 4. Priority Queue
A priority queue is a special type of queue where each element has a priority, and elements
with higher priority are dequeued first.

●​ If two elements have the same priority, they follow FIFO order.
●​ Can be implemented using arrays, linked lists, or heaps.

📌 Priority Queue Operations

●​ enqueue(value, priority): Insert an element based on priority.
●​ dequeue(): Remove the highest-priority element.

✅ Pros: Efficient task scheduling.​

❌ Cons: Requires extra logic for ordering elements.

🔹 Applications of Different Queues

1.​ Simple Queue – Printer queue, ticket booking system.
2.​ Circular Queue – CPU scheduling, memory buffer.
3.​ Deque – Palindrome checking, browser history.
4.​ Priority Queue – Process scheduling, hospital emergency system.