UNIT-1

Answer the below long questions -(10 Marks)

Q1. a) Explain the classification of data structures with suitable examples. Discuss linear and non-
linear data structures in detail.

Ans. CLASSIFICATION OF DATA STRUCTURES

A data structure is a way of organizing and storing data so that it can be accessed and modified
efficiently. Data structures are classified into different types based on the way data elements are
organized and related to each other.

Data structures are mainly classified into:

1. Primitive Data Structures

2. Non-Primitive Data Structures

--------------------------------------------------

1. Primitive Data Structures

Primitive data structures are the basic data types provided by programming languages. They store
single values.

Examples:

• Integer

• Float

• Character

• Boolean

Example:

int a = 10;

char ch = 'A';

--------------------------------------------------

2. Non-Primitive Data Structures

Non-primitive data structures are more complex and can store multiple values.

They are further classified into:

1. Linear Data Structures

2. Non-Linear Data Structures

===================================

LINEAR DATA STRUCTURES

In linear data structures, elements are arranged in a sequential manner. Each element is connected
to the next element.

Characteristics:

• Data elements are stored one after another.

• Traversal is done in a single level.

• Easier to implement.

Types of Linear Data Structures:

a) Array

An array is a collection of elements of the same data type stored in contiguous memory locations.

Example:

int arr[5] = {10,20,30,40,50};

Representation:

Index : 0 1 2 3 4

Data : 10 20 30 40 50

Advantages:

• Fast access using index.

• Easy to traverse.

Disadvantages:

• Fixed size.

• Insertion and deletion are difficult.

--------------------------------------------------

b) Linked List

A linked list consists of nodes where each node contains data and a pointer to the next node.

Representation:

[10|•] → [20|•] → [30|NULL]

Advantages:
• Dynamic size.

• Easy insertion and deletion.

Disadvantages:

• Extra memory required for pointers.

• Sequential access only.

--------------------------------------------------

c) Stack

A stack follows the LIFO (Last In First Out) principle.

Operations:

• Push

• Pop

• Peek

Representation:

Top

|30|

|20|

|10|

Applications:

• Function calls

• Expression evaluation

• Undo operation

--------------------------------------------------

d) Queue

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

Operations:

• Enqueue
• Dequeue

Representation:

Front → 10 20 30 40 ← Rear

Applications:

• CPU scheduling

• Printer queue

• Ticket booking systems

===================================

NON-LINEAR DATA STRUCTURES

In non-linear data structures, elements are not arranged sequentially. One element can be connected
to multiple elements.

Characteristics:

• Hierarchical relationship.

• Traversal occurs at multiple levels.

• More complex than linear structures.

Types of Non-Linear Data Structures:

a) Tree

A tree is a hierarchical data structure consisting of nodes connected by edges.

Tree Structure:

/\

B C

/\

D E

Terminology:

• A → Root node

• B, C → Child nodes

• D, E → Leaf nodes
Applications:

• File systems

• Database indexing

• XML/HTML parsing

--------------------------------------------------

b) Graph

A graph consists of vertices (nodes) and edges connecting them.

Representation:

A ----- B

\ /

\/

Applications:

• Social networks

• Maps and navigation systems

• Computer networks

====================================

DIFFERENCE BETWEEN LINEAR AND NON-LINEAR DATA STRUCTURES

Linear Data Structures:

• Elements arranged sequentially

• Traversal in single level

• Easier to implement

• Examples: Array, Stack, Queue

Non-Linear Data Structures:

• Elements arranged hierarchically

• Traversal in multiple levels

• More complex
• Examples: Tree, Graph

CONCLUSION

Data structures play an important role in organizing and managing data efficiently. They are broadly
classified into primitive and non-primitive structures. Non-primitive structures are further divided into
linear and non-linear data structures. Linear structures store data sequentially, whereas non-linear
structures represent hierarchical relationships. Choosing the appropriate data structure improves the
efficiency of programs and algorithms.

b) Define Abstract Data Type (ADT). Explain the advantages of ADTs and the factors involved in
selecting a suitable data structure.

Ans. ABSTRACT DATA TYPE (ADT)

An Abstract Data Type (ADT) is a logical model of a data structure that specifies the type of data
stored and the operations that can be performed on the data without describing how the data is
implemented.

In simple words, ADT focuses on:

• What operations are performed

• Not how they are performed

Examples of ADTs:

• Stack

• Queue

• List

• Tree

• Graph

For example, a Stack ADT performs operations such as:

• Push

• Pop

• Peek

But the implementation may use:

• Arrays

• Linked Lists

Thus, ADT hides implementation details from the user.

--------------------------------------------------

Example of Stack ADT:

Operations:

• Push() – Insert element

• Pop() – Remove top element

• Peek() – View top element

Representation:

Top

|30|

|20|

|10|

The user only knows the operations, not the internal implementation.

====================================

ADVANTAGES OF ABSTRACT DATA TYPES (ADT)

1. Data Hiding

ADT hides the internal implementation details and exposes only necessary operations.

Example:

A user can use Stack operations without knowing whether it is implemented using array or linked list.

2. Modularity

Programs become modular because implementation and usage are separated.

Different modules can work independently.

3. Reusability

The same ADT can be reused in different programs.

Example:

Queue ADT can be used in:

• CPU scheduling
• Printer management

• Ticket booking systems

4. Easy Maintenance

Changes in implementation do not affect the user program.

Example:

Changing Stack implementation from array to linked list does not change Stack operations.

5. Security and Reliability

Since data is accessed only through defined operations, accidental modification is reduced.

6. Simplifies Programming

ADT provides a simple interface to the programmer and reduces complexity.

====================================

FACTORS FOR SELECTING A SUITABLE DATA STRUCTURE

Choosing a suitable data structure is important for improving program efficiency and performance.

The following factors should be considered:

1. Time Efficiency

The data structure should perform operations quickly.

Operations include:

• Searching

• Insertion

• Deletion

• Traversal

Example:

Binary Search Tree provides faster searching compared to linked list.

2. Space Efficiency

Memory usage should be minimum.

Example:

Arrays require fixed memory, whereas linked lists use extra memory for pointers.
3. Nature of Data

The structure should suit the type of data.

Example:

• Hierarchical data → Tree

• Sequential data → Array or Linked List

• Network data → Graph

4. Frequency of Operations

Selection depends on which operations are performed more frequently.

Example:

• Frequent insertion/deletion → Linked List

• Frequent searching → Hash Table or Tree

5. Size of Data

The amount of data affects the choice.

Example:

• Small fixed data → Array

• Large dynamic data → Linked List

6. Simplicity of Implementation

The data structure should be easy to implement and maintain.

Simple structures reduce programming complexity.

7. Data Relationships

Relationship among data elements is important.

Example:

• Parent-child relationship → Tree

• Many-to-many relationship → Graph

CONCLUSION

An Abstract Data Type (ADT) is a logical representation of a data structure that defines data and
operations without showing implementation details. ADTs provide advantages such as data hiding,
reusability, modularity, and easy maintenance. Selecting a suitable data structure depends on factors
like time efficiency, space efficiency, nature of data, and frequency of operations. Proper selection
improves the performance and efficiency of programs.

Q2. a) Explain the operations performed on data structures with examples.

Ans. OPERATIONS PERFORMED ON DATA STRUCTURES

Data structures are used to organize and store data efficiently. Various operations are performed on
data structures to manipulate and process data according to user requirements.

The basic operations performed on data structures are:

1. Traversal

2. Insertion

3. Deletion

4. Searching

5. Sorting

6. Merging

====================================

1. TRAVERSAL

Traversal means visiting each element of a data structure exactly once to process or display the data.

Example:

Array:

[10, 20, 30, 40]

Traversal Output:

10 20 30 40

Representation:

Index : 0 1 2 3

Data : 10 20 30 40

Algorithm Steps:

• Start from the first element.

• Visit each element one by one.

• Continue until the last element.

Applications:

• Displaying elements

• Calculating sum or average

• Updating values

2. INSERTION

Insertion means adding a new element into a data structure at a specified position.

Example:

Original Array:

[10, 20, 40, 50]

Insert 30 at position 3:

New Array:

[10, 20, 30, 40, 50]

Steps:

• Shift elements to the right.

• Insert the new element at the desired position.

Applications:

• Adding records in databases

• Adding items in lists

3. DELETION

Deletion means removing an element from a data structure.

Example:

Original Array:

[10, 20, 30, 40, 50]

Delete 30:

New Array:

[10, 20, 40, 50]

Steps:
• Find the element to delete.

• Shift remaining elements to the left.

Applications:

• Removing unnecessary records

• Deleting files or entries

4. SEARCHING

Searching means finding the location of an element in a data structure.

Example:

Array:

[10, 20, 30, 40, 50]

Search for 30:

Result → Element found at index 2

Types of Searching:

• Linear Search

• Binary Search

Applications:

• Searching names in contact lists

• Searching records in databases

5. SORTING

Sorting means arranging elements in ascending or descending order.

Example:

Original Array:

[40, 10, 30, 20]

Ascending Order:

[10, 20, 30, 40]

Types of Sorting:

• Bubble Sort
• Selection Sort

• Insertion Sort

• Quick Sort

Applications:

• Ranking students

• Arranging files alphabetically

6. MERGING

Merging means combining two or more data structures into a single structure.

Example:

Array 1:

[10, 20]

Array 2:

[30, 40]

Merged Array:

[10, 20, 30, 40]

Applications:

• Combining sorted files

• Database management

====================================

OPERATIONS ON LINEAR DATA STRUCTURES

1. Stack Operations

A stack follows the LIFO (Last In First Out) principle.

Operations:

• Push

• Pop

• Peek

Representation:
Top

|30|

|20|

|10|

Push 40:

|40|

|30|

|20|

|10|

Applications:

• Function calls

• Undo operations

2. Queue Operations

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

Operations:

• Enqueue

• Dequeue

Representation:

Front → 10 20 30 40 ← Rear

Applications:

• CPU scheduling

• Printer queue

====================================

OPERATIONS ON NON-LINEAR DATA STRUCTURES

1. Tree Traversal

Traversal in trees includes:

• Preorder

• Inorder

• Postorder

Tree Example:

/\

B C

/\

D E

Inorder Traversal:

DBEAC

Applications:

• Expression trees

• File systems

2. Graph Traversal

Graph traversal methods:

• Breadth First Search (BFS)

• Depth First Search (DFS)

Graph Representation:

A ----- B

\ /

\/

Applications:

• Social networks

• Path finding

CONCLUSION
Operations on data structures help in organizing, processing, and managing data efficiently. Common
operations include traversal, insertion, deletion, searching, sorting, and merging. Different data
structures such as arrays, stacks, queues, trees, and graphs support various operations according to
their design and applications. Efficient use of these operations improves the performance and
reliability of computer programs.

b) Discuss the importance of data structures in problem solving and software development.

Ans. IMPORTANCE OF DATA STRUCTURES IN PROBLEM SOLVING AND SOFTWARE

DEVELOPMENT

Data structures are methods of organizing and storing data efficiently so that it can be accessed and
modified easily. They play a vital role in problem solving and software development because they
improve the performance, efficiency, and reliability of programs.

Choosing the correct data structure helps in reducing complexity and developing optimized software
applications.

====================================

IMPORTANCE OF DATA STRUCTURES IN PROBLEM SOLVING

1. Efficient Data Organization

Data structures organize data systematically, making processing easier and faster.

Example:

• Arrays store elements sequentially.

• Trees store hierarchical data.

Efficient organization reduces processing time.

2. Faster Data Access

Appropriate data structures allow quick searching, insertion, and deletion operations.

Example:

• Binary Search Tree provides faster searching.

• Hash Table allows direct access to data.

This improves overall program efficiency.

3. Reduces Time Complexity

Using suitable data structures reduces the execution time of algorithms.

Example:
• Binary Search works faster on sorted arrays.

• Queue helps in efficient scheduling.

Efficient algorithms solve problems quickly.

4. Better Memory Management

Data structures help in utilizing memory efficiently.

Example:

• Linked Lists allocate memory dynamically.

• Arrays use fixed memory allocation.

Proper memory management improves system performance.

5. Simplifies Complex Problems

Complex problems can be solved easily using suitable data structures.

Examples:

• Graphs are used in navigation systems.

• Trees are used in file systems.

• Stacks are used in expression evaluation.

Data structures provide logical ways to represent problems.

6. Supports Algorithm Design

Many algorithms depend on data structures for implementation.

Examples:

• Searching algorithms

• Sorting algorithms

• Traversal algorithms

Efficient data structures improve algorithm performance.

====================================

IMPORTANCE OF DATA STRUCTURES IN SOFTWARE DEVELOPMENT

1. Improves Software Performance

Efficient data structures increase the speed and responsiveness of software.

Example:

Database systems use trees and indexing structures for faster retrieval.

2. Helps in Large Application Development

Modern software applications handle huge amounts of data. Data structures help in managing this
data efficiently.

Examples:

• Social media applications

• Banking systems

• E-commerce websites

3. Enhances Code Reusability

Data structures such as stacks, queues, and linked lists can be reused in multiple programs.

This reduces development time.

4. Supports Data Management

Software applications require efficient storage and management of data.

Examples:

• Arrays for storing records

• Graphs for network connections

• Trees for hierarchical information.

5. Essential in Database Management Systems

Databases use data structures for:

• Searching records

• Sorting data

• Indexing

Example:

B-Trees are used in databases for efficient data retrieval.

6. Important in Operating Systems

Operating systems use data structures for:

• Memory management
• Process scheduling

• File organization

Examples:

• Queue for CPU scheduling

• Tree for directory structure

7. Used in Real-Time Applications

Data structures are essential in:

• Navigation systems

• Artificial Intelligence

• Machine Learning

• Computer Networks

Graphs are widely used in routing and network analysis.

====================================

EXAMPLES OF DATA STRUCTURES USED IN SOFTWARE DEVELOPMENT

1. Stack

A stack follows LIFO (Last In First Out).

Representation:

Top

|30|

|20|

|10|

Applications:

• Function calls

• Undo operations

2. Queue

A queue follows FIFO (First In First Out).

Representation:

Front → 10 20 30 40 ← Rear

Applications:

• CPU scheduling

• Printer queue

3. Tree

A tree stores hierarchical data.

Representation:

/\

B C

/\

D E

Applications:

• File systems

• Database indexing

4. Graph

A graph represents relationships between objects.

Representation:

A ----- B

\ /

\/

Applications:

• Social networks

• Google Maps

• Network routing
CONCLUSION

Data structures are essential for efficient problem solving and software development. They help in
organizing data, reducing execution time, improving memory usage, and simplifying complex
problems. Data structures also enhance software performance, support algorithm design, and are
widely used in operating systems, databases, networking, and real-time applications. Choosing the
appropriate data structure improves the efficiency, scalability, and reliability of software systems.

Q3. a) Define a singly linked list. Explain its structure and write algorithms for insertion and deletion
operations.

Ans. SINGLY LINKED LIST

A singly linked list is a linear dynamic data structure in which each node contains two parts:

1. Data

2. Pointer (address) to the next node

The nodes are connected sequentially, and the last node points to NULL.

====================================

STRUCTURE OF A SINGLY LINKED LIST

Node Structure:

[data | next]

Representation:

[10 | • ] → [20 | • ] → [30 | NULL]

Where:

• Data part stores the value

• Next part stores the address of the next node

Characteristics:

• Dynamic memory allocation

• Sequential access

• Efficient insertion and deletion

• No contiguous memory required

====================================

INSERTION OPERATION IN SINGLY LINKED LIST

Insertion means adding a new node into the linked list.

1. Insertion at Beginning

Original List:

[20|•] → [30|NULL]

Insert 10:

New List:

[10|•] → [20|•] → [30|NULL]

Algorithm:

Step 1: Create NEWNODE

Step 2: Insert data into NEWNODE

Step 3: NEWNODE → NEXT = HEAD

Step 4: HEAD = NEWNODE

Step 5: STOP

Pseudo Code:

NEWNODE = CREATE NODE

NEWNODE → DATA = ITEM

NEWNODE → NEXT = HEAD

HEAD = NEWNODE

--------------------------------------------------

2. Insertion at End

Original List:

[10|•] → [20|NULL]

Insert 30:

New List:

[10|•] → [20|•] → [30|NULL]

Algorithm:

Step 1: Create NEWNODE

Step 2: Insert data into NEWNODE

Step 3: Traverse till last node

Step 4: LAST → NEXT = NEWNODE

Step 5: NEWNODE → NEXT = NULL

Step 6: STOP

====================================

DELETION OPERATION IN SINGLY LINKED LIST

Deletion means removing a node from the linked list.

1. Deletion at Beginning

Original List:

[10|•] → [20|•] → [30|NULL]

Delete 10:

New List:

[20|•] → [30|NULL]

Algorithm:

Step 1: TEMP = HEAD

Step 2: HEAD = HEAD → NEXT

Step 3: DELETE TEMP

Step 4: STOP

--------------------------------------------------

2. Deletion at End

Original List:

[10|•] → [20|•] → [30|NULL]

Delete 30:

New List:

[10|•] → [20|NULL]

Algorithm:
Step 1: Traverse till second last node

Step 2: TEMP = LAST NODE

Step 3: SECONDLAST → NEXT = NULL

Step 4: DELETE TEMP

Step 5: STOP

====================================

ADVANTAGES OF SINGLY LINKED LIST

1. Dynamic size allocation

2. Efficient insertion and deletion

3. Better memory utilization

4. No memory wastage due to fixed size

====================================

DISADVANTAGES OF SINGLY LINKED LIST

1. Sequential access only

2. Extra memory required for pointers

3. Searching is slower compared to arrays

====================================

APPLICATIONS OF SINGLY LINKED LIST

1. Implementation of stacks and queues

2. Memory management

3. Polynomial representation

4. Dynamic data storage

CONCLUSION

A singly linked list is an important dynamic linear data structure consisting of nodes connected using
pointers. It allows efficient insertion and deletion operations and is widely used in computer science
applications where dynamic memory allocation is required.

b) Explain traversal and searching operations in a singly linked list with suitable examples.

Ans. TRAVERSAL AND SEARCHING OPERATIONS IN A SINGLY LINKED LIST

A singly linked list is a linear data structure in which each node contains:

1. Data

2. Pointer to the next node

The nodes are connected sequentially, and the last node points to NULL.

====================================

STRUCTURE OF A SINGLY LINKED LIST

Representation:

[10|•] → [20|•] → [30|•] → [40|NULL]

Where:

• Data part stores the value

• Pointer part stores address of next node

====================================

TRAVERSAL OPERATION

Traversal means visiting each node of the linked list exactly once in order to process or display the
data.

During traversal, the nodes are accessed one by one starting from the first node until NULL is
reached.

Example:

Linked List:

[10|•] → [20|•] → [30|•] → [40|NULL]

Traversal Output:

10 20 30 40

Algorithm for Traversal:

Step 1: START = HEAD

Step 2: Repeat while START ≠ NULL

Print START → DATA

START = START → NEXT

Step 3: STOP
Pseudo Code:

PTR = HEAD

WHILE PTR ≠ NULL

PRINT PTR → DATA

PTR = PTR → NEXT

END WHILE

Explanation:

• HEAD stores address of first node.

• START moves from one node to another.

• Traversal stops when START becomes NULL.

Applications of Traversal:

1. Displaying elements

2. Counting nodes

3. Updating node values

4. Finding maximum or minimum element

====================================

SEARCHING OPERATION

Searching means finding whether a particular element exists in the linked list.

The nodes are checked one by one until the required element is found or the end of the list is
reached.

Example:

Linked List:

[10|•] → [20|•] → [30|•] → [40|NULL]

Search Element = 30

Result:

Element Found

--------------------------------------------------

Example 2:
Search Element = 50

Result:

Element Not Found

====================================

ALGORITHM FOR SEARCHING

Step 1: START = HEAD

Step 2: Repeat while START ≠ NULL

If START → DATA = ITEM

Print "Element Found"

STOP

START = START → NEXT

Step 3: Print "Element Not Found"

Pseudo Code:

PTR = HEAD

WHILE PTR ≠ NULL

IF PTR → DATA = ITEM

PRINT "FOUND"

EXIT

PTR = PTR → NEXT

END WHILE

IF PTR = NULL

PRINT "NOT FOUND"

====================================

WORKING OF SEARCHING OPERATION

Linked List:

[10|•] → [20|•] → [30|•] → [40|NULL]

Search Item = 30
Step 1:

Compare 10 with 30 → Not Equal

Step 2:

Compare 20 with 30 → Not Equal

Step 3:

Compare 30 with 30 → Element Found

====================================

ADVANTAGES OF TRAVERSAL AND SEARCHING

1. Easy processing of nodes

2. Helpful in displaying and updating data

3. Searching helps locate required elements efficiently

====================================

DISADVANTAGES

1. Sequential access only

2. Searching takes more time for large lists

3. No direct access like arrays

====================================

APPLICATIONS OF SINGLY LINKED LIST

1. Implementation of stacks and queues

2. Memory management

3. Dynamic data storage

4. Polynomial representation

CONCLUSION

Traversal and searching are important operations in a singly linked list. Traversal helps in accessing
and processing all nodes, while searching helps in locating a required element in the list. These
operations are widely used in various computer science and software development applications.

Q4.a) What is a circular linked list? Explain its advantages and applications with neat diagrams.

Ans. CIRCULAR LINKED LIST

A circular linked list is a type of linked list in which the last node points back to the first node instead
of NULL.

Thus, all the nodes are connected in a circular form.

====================================

STRUCTURE OF CIRCULAR LINKED LIST

Node Structure:

[data | next]

Representation:

┌─────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑_____________________|

In a circular linked list:

• Each node contains data and address of next node

• The last node links back to the first node

• There is no NULL pointer at the end

==================================================

CHARACTERISTICS OF CIRCULAR LINKED LIST

1. Last node points to first node

2. Nodes form a circular chain

3. Traversal can start from any node

4. Continuous traversal is possible

5. Dynamic memory allocation is used

====================================

WORKING OF CIRCULAR LINKED LIST

Example:

┌─────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑_____________________|

Traversal:

10 → 20 → 30 → Back to 10

Unlike singly linked lists, traversal does not stop at NULL because the last node connects to the first
node.

====================================

ADVANTAGES OF CIRCULAR LINKED LIST

1. Continuous Traversal

The list can be traversed continuously without restarting from the beginning.

--------------------------------------------------

2. Efficient Memory Utilization

No NULL pointer is required for the last node.

--------------------------------------------------

3. Faster Insertion and Deletion

Insertion and deletion at beginning and end are more efficient.

--------------------------------------------------

4. Suitable for Cyclic Processes

It is ideal for applications that require repeated processing.

--------------------------------------------------

5. Easy Implementation of Circular Queues

Circular linked lists are widely used for implementing circular queues.

====================================
DISADVANTAGES OF CIRCULAR LINKED LIST

1. Complex implementation compared to singly linked list

2. Infinite loops may occur during traversal

3. Debugging is difficult

====================================

APPLICATIONS OF CIRCULAR LINKED LIST

1. CPU Scheduling

Used in Round Robin Scheduling where processes execute repeatedly in circular order.

--------------------------------------------------

2. Music and Video Playlists

Songs or videos can repeat continuously.

--------------------------------------------------

3. Multiplayer Games

Turns of players are managed in circular sequence.

--------------------------------------------------

4. Circular Queues

Used for efficient queue management.

--------------------------------------------------

5. Traffic Signal Systems

Traffic lights change repeatedly in cyclic order.

--------------------------------------------------

6. Operating Systems

Used in process management and resource sharing.

====================================

DIFFERENCE BETWEEN SINGLY LINKED LIST AND CIRCULAR LINKED LIST

Singly Linked List:

• Last node points to NULL

• Traversal stops at end node

• Sequential processing only

Circular Linked List:

• Last node points to first node

• Continuous traversal possible

• Suitable for cyclic operations

CONCLUSION

A circular linked list is a linked list in which the last node connects back to the first node, forming a
circular structure. It allows continuous traversal and efficient cyclic processing. Due to its advantages,
it is widely used in CPU scheduling, playlists, multiplayer games, and circular queue implementations.

b) Compare singly linked lists and circular linked lists. Explain insertion and deletion operations in
circular linked lists.

[Link] BETWEEN SINGLY LINKED LIST AND CIRCULAR LINKED LIST

A linked list is a dynamic linear data structure consisting of nodes connected using pointers. Singly
linked lists and circular linked lists are important types of linked lists used in data management.

====================================

SINGLY LINKED LIST

A singly linked list is a linear data structure in which each node contains data and a pointer to the next
node. The last node points to NULL.

Representation:

[10|•] → [20|•] → [30|NULL]

====================================

CIRCULAR LINKED LIST

A circular linked list is a linked list in which the last node points back to the first node instead of NULL.

Representation:

┌─────────────────────┐

↓ │
[10|•] → [20|•] → [30|•]

↑_____________________|

====================================

COMPARISON BETWEEN SINGLY LINKED LIST AND CIRCULAR LINKED LIST

1. Last Node Connection

Singly Linked List:

Last node points to NULL.

Circular Linked List:

Last node points back to first node.

--------------------------------------------------

2. Traversal

Singly Linked List:

Traversal ends when NULL is reached.

Circular Linked List:

Traversal continues circularly until starting node is reached again.

--------------------------------------------------

3. Structure

Singly Linked List:

Linear structure.

Circular Linked List:

Circular structure.

--------------------------------------------------

4. Memory Utilization

Singly Linked List:

Uses NULL pointer at end node.

Circular Linked List:

No NULL pointer required.

--------------------------------------------------

5. Applications

Singly Linked List:

Used in stacks, queues, and memory management.

Circular Linked List:

Used in CPU scheduling, playlists, and circular queues.

====================================

INSERTION OPERATION IN CIRCULAR LINKED LIST

Insertion means adding a new node into the circular linked list.

1. Insertion at Beginning

Original List:

┌─────────────────┐

↓ │

[20|•] → [30|•]

↑_______________|

Insert 10:

New List:

┌──────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑______________________|

Algorithm:

Step 1: Create NEWNODE

Step 2: Insert data into NEWNODE

Step 3: NEWNODE → NEXT = HEAD

Step 4: Traverse to last node

Step 5: LAST → NEXT = NEWNODE

Step 6: HEAD = NEWNODE

Step 7: STOP

--------------------------------------------------

2. Insertion at End

Original List:

┌─────────────────┐

↓ │

[10|•] → [20|•]

↑_______________|

Insert 30:

New List:

┌──────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑______________________|

Algorithm:

Step 1: Create NEWNODE

Step 2: Traverse to last node

Step 3: LAST → NEXT = NEWNODE

Step 4: NEWNODE → NEXT = HEAD

Step 5: STOP

====================================

DELETION OPERATION IN CIRCULAR LINKED LIST

Deletion means removing a node from the circular linked list.

1. Deletion at Beginning

Original List:

┌──────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑______________________|

Delete 10:

New List:

┌─────────────────┐

↓ │

[20|•] → [30|•]

↑_______________|

Algorithm:

Step 1: TEMP = HEAD

Step 2: Traverse to last node

Step 3: HEAD = HEAD → NEXT

Step 4: LAST → NEXT = HEAD

Step 5: DELETE TEMP

Step 6: STOP
--------------------------------------------------

2. Deletion at End

Original List:

┌──────────────────────┐

↓ │

[10|•] → [20|•] → [30|•]

↑______________________|

Delete 30:

New List:

┌─────────────────┐

↓ │

[10|•] → [20|•]

↑_______________|

Algorithm:

Step 1: Traverse to second last node

Step 2: TEMP = LAST NODE

Step 3: SECONDLAST → NEXT = HEAD

Step 4: DELETE TEMP

Step 5: STOP

====================================

ADVANTAGES OF CIRCULAR LINKED LIST

1. Continuous traversal possible

2. Efficient insertion and deletion

3. Suitable for cyclic operations

4. Better memory utilization

====================================

APPLICATIONS OF CIRCULAR LINKED LIST

1. CPU scheduling

2. Circular queues

3. Music playlists

4. Multiplayer games

5. Traffic signal systems

CONCLUSION

A singly linked list is a linear linked structure where the last node points to NULL, whereas a circular
linked list connects the last node back to the first node. Circular linked lists support continuous
traversal and are useful for cyclic applications. Insertion and deletion operations are efficiently
performed by adjusting node pointers properly.

Q5. a) Explain the structure of a doubly linked list. Write algorithms for insertion and deletion
operations.

Ans. DOUBLY LINKED LIST

A doubly linked list is a linear dynamic data structure in which each node contains:

1. Pointer to previous node

2. Data

3. Pointer to next node

It allows traversal in both forward and backward directions.

====================================

STRUCTURE OF A DOUBLY LINKED LIST

Node Structure:

[prev | data | next]

Representation:
NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

Where:

• prev stores address of previous node

• data stores the value

• next stores address of next node

Characteristics:

1. Bidirectional traversal possible

2. Dynamic memory allocation

3. Efficient insertion and deletion

4. Requires extra memory for previous pointer

====================================

INSERTION OPERATION IN DOUBLY LINKED LIST

Insertion means adding a new node into the doubly linked list.

1. Insertion at Beginning

Original List:

NULL ← [20|•|•] ⇄ [30|•|NULL]

Insert 10:

New List:

NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

Algorithm:

Step 1: Create NEWNODE

Step 2: Insert data into NEWNODE

Step 3: NEWNODE → PREV = NULL

Step 4: NEWNODE → NEXT = HEAD

Step 5: HEAD → PREV = NEWNODE

Step 6: HEAD = NEWNODE

Step 7: STOP

Pseudo Code:

NEWNODE = CREATE NODE

NEWNODE → DATA = ITEM

NEWNODE → PREV = NULL

NEWNODE → NEXT = HEAD

HEAD → PREV = NEWNODE

HEAD = NEWNODE

--------------------------------------------------

2. Insertion at End

Original List:

NULL ← [10|•|•] ⇄ [20|•|NULL]

Insert 30:

New List:

NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

Algorithm:

Step 1: Create NEWNODE

Step 2: Traverse till last node

Step 3: LAST → NEXT = NEWNODE

Step 4: NEWNODE → PREV = LAST

Step 5: NEWNODE → NEXT = NULL

Step 6: STOP

====================================

DELETION OPERATION IN DOUBLY LINKED LIST

Deletion means removing a node from the doubly linked list.

1. Deletion at Beginning

Original List:

NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

Delete 10:

New List:

NULL ← [20|•|•] ⇄ [30|•|NULL]

Algorithm:

Step 1: TEMP = HEAD

Step 2: HEAD = HEAD → NEXT

Step 3: HEAD → PREV = NULL

Step 4: DELETE TEMP

Step 5: STOP

--------------------------------------------------

2. Deletion at End

Original List:

NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

Delete 30:

New List:

NULL ← [10|•|•] ⇄ [20|•|NULL]

Algorithm:

Step 1: Traverse till last node

Step 2: TEMP = LAST NODE

Step 3: LAST → PREV → NEXT = NULL

Step 4: DELETE TEMP

Step 5: STOP

====================================

ADVANTAGES OF DOUBLY LINKED LIST

1. Traversal possible in both directions

2. Easy insertion and deletion

3. Efficient memory management

4. Useful for implementing advanced applications

====================================

DISADVANTAGES OF DOUBLY LINKED LIST

1. Requires extra memory for previous pointer

2. More complex implementation

3. Pointer handling is difficult

====================================

APPLICATIONS OF DOUBLY LINKED LIST

1. Browser forward and backward navigation

2. Undo and redo operations

3. Music playlists

4. Memory management systems

CONCLUSION

A doubly linked list is a dynamic linear data structure in which each node contains pointers to both
previous and next nodes. It supports bidirectional traversal and efficient insertion and deletion
operations. Due to its flexibility, it is widely used in browser navigation, playlists, and memory
management applications.
b) Discuss the advantages and disadvantages of doubly linked lists over singly linked lists.

Ans. ADVANTAGES AND DISADVANTAGES OF DOUBLY LINKED LISTS OVER SINGLY LINKED
LISTS

Linked lists are dynamic data structures used to store and manage data efficiently. Singly linked lists
and doubly linked lists are important types of linked lists used in computer science applications.

====================================

SINGLY LINKED LIST

A singly linked list is a linear data structure in which each node contains:

1. Data

2. Pointer to the next node

Representation:

[10|•] → [20|•] → [30|NULL]

====================================

DOUBLY LINKED LIST

A doubly linked list is a linked list in which each node contains:

1. Pointer to previous node

2. Data

3. Pointer to next node

Representation:

NULL ← [10|•|•] ⇄ [20|•|•] ⇄ [30|•|NULL]

====================================

ADVANTAGES OF DOUBLY LINKED LIST OVER SINGLY LINKED LIST

1. Bidirectional Traversal

In a doubly linked list, traversal is possible in both forward and backward directions.

Example:

NULL ← [10] ⇄ [20] ⇄ [30] → NULL

This is not possible in singly linked lists because they contain only next pointers.

--------------------------------------------------
2. Easy Deletion of Nodes

Deletion operation is easier because the previous node can be accessed directly.

In singly linked lists, traversal from the beginning is needed to find the previous node.

--------------------------------------------------

3. Efficient InsertionInsertion before or after a node is simpler and faster because both previous and
next pointers are available.

--------------------------------------------------

4. Better Navigation

Doubly linked lists support backward movement.

Applications:

• Browser back and forward buttons

• Undo and redo operations

--------------------------------------------------

5. Efficient for Dynamic Applications

Suitable for applications requiring frequent insertion and deletion.

Examples:

• Music playlists

• Navigation systems

====================================

DISADVANTAGES OF DOUBLY LINKED LIST OVER SINGLY LINKED LIST

1. Extra Memory Requirement

Each node stores two pointers:

• Previous pointer

• Next pointer

This increases memory usage.

--------------------------------------------------

2. Complex Structure

Pointer handling becomes more complicated compared to singly linked lists.

--------------------------------------------------

3. More Time for Pointer Updates

Insertion and deletion require updating multiple pointers.

--------------------------------------------------

4. Difficult Implementation

Programming and debugging are more difficult because of additional pointer operations.

====================================

COMPARISON BETWEEN SINGLY LINKED LIST AND DOUBLY LINKED LIST

1. Number of Pointers

Singly Linked List:

One pointer (next)

Doubly Linked List:

Two pointers (previous and next)

--------------------------------------------------

2. Traversal

Singly Linked List:

Only forward traversal

Doubly Linked List:

Forward and backward traversal

--------------------------------------------------

3. Memory Usage

Singly Linked List:

Less memory required

Doubly Linked List:

More memory required

--------------------------------------------------

4. Insertion and Deletion

Singly Linked List:

More difficult

Doubly Linked List:

Easier and faster

--------------------------------------------------

5. Complexity

Singly Linked List:

Simple implementation

Doubly Linked List:

Complex implementation

====================================

APPLICATIONS OF DOUBLY LINKED LIST

1. Browser history navigation

2. Undo and redo operations

3. Music and video playlists

4. Image viewers

5. Memory management systems

CONCLUSION

A doubly linked list provides several advantages over a singly linked list, such as bidirectional
traversal, easy insertion, and efficient deletion operations. However, it also has disadvantages like
extra memory usage and complex implementation. Therefore, the choice between singly and doubly
linked lists depends on the requirements of the application.

Q6. a) Define Stack ADT. Explain stack operations with algorithms and examples.

Ans. STACK ADT

A Stack Abstract Data Type (ADT) is a linear data structure that follows the LIFO (Last In First Out)
principle, where the element inserted last is removed first.

A stack allows operations only at one end called TOP.

Examples of stack in real life:

• Stack of plates

• Books piled one above another

====================================

STRUCTURE OF STACK

Representation:

Top

|40|

|30|

|20|

|10|

Where:

• TOP points to the last inserted element

• Insertion and deletion occur only at TOP

====================================

CHARACTERISTICS OF STACK

1. Follows LIFO principle

2. Insertion and deletion at one end only

3. Simple and efficient structure

4. Can be implemented using arrays or linked lists

====================================

STACK OPERATIONS

The main operations performed on a stack are:

1. PUSH

2. POP

3. PEEK (TOP)

4. DISPLAY
====================================

1. PUSH OPERATION

Push operation inserts an element into the stack.

Example:

Initial Stack:

Top

|30|

|20|

|10|

Push 40:

Top

|40|

|30|

|20|

|10|

Algorithm for PUSH:

Step 1: Check if stack is full

Step 2: If full, print "Stack Overflow"

Step 3: Otherwise increment TOP

Step 4: Insert ITEM at STACK[TOP]

Step 5: STOP

Pseudo Code:
IF TOP = MAX - 1

PRINT "STACK OVERFLOW"

ELSE

TOP = TOP + 1

STACK[TOP] = ITEM

END IF

--------------------------------------------------

2. POP OPERATION

Pop operation removes the top element from the stack.

Example:

Initial Stack:

Top

|40|

|30|

|20|

|10|

Pop Operation:

Removed Element = 40

New Stack:

Top

|30|

|20|
|10|

Algorithm for POP:

Step 1: Check if stack is empty

Step 2: If empty, print "Stack Underflow"

Step 3: Otherwise store STACK[TOP]

Step 4: Decrement TOP

Step 5: Return deleted element

Pseudo Code:

IF TOP = -1

PRINT "STACK UNDERFLOW"

ELSE

ITEM = STACK[TOP]

TOP = TOP - 1

END IF

--------------------------------------------------

3. PEEK OPERATION

Peek operation displays the top element without deleting it.

Example:

Top

|40|

|30|

|20|

Peek Element = 40
Algorithm for PEEK:

Step 1: Check if stack is empty

Step 2: If empty, print "Stack Empty"

Step 3: Otherwise display STACK[TOP]

Pseudo Code:

IF TOP = -1

PRINT "STACK EMPTY"

ELSE

PRINT STACK[TOP]

END IF

--------------------------------------------------

4. DISPLAY OPERATION

Display operation prints all elements of the stack from TOP to bottom.

Example:

Top

|40|

|30|

|20|

|10|

Display Output:

40 30 20 10

Algorithm for DISPLAY:

Step 1: Check if stack is empty

Step 2: Traverse from TOP to 0

Step 3: Print each element

====================================

ADVANTAGES OF STACK

1. Simple implementation

2. Efficient insertion and deletion

3. Useful in recursive operations

4. Memory management support

====================================

DISADVANTAGES OF STACK

1. Limited size in array implementation

2. Only top element can be accessed

3. Searching is difficult

====================================

APPLICATIONS OF STACK

1. Function call management

2. Expression evaluation

3. Undo and redo operations

4. Browser history

5. Parenthesis matching

CONCLUSION

A Stack ADT is a linear data structure that follows the LIFO principle. The main stack operations are
push, pop, peek, and display. Stacks are widely used in computer science applications such as
recursion, expression evaluation, browser navigation, and memory management.

b) Discuss array implementation and linked list implementation of stacks with suitable examples.

Ans. IMPLEMENTATION OF STACK USING ARRAY AND LINKED LIST

Definition of Stack:
A stack is a linear data structure that follows the LIFO (Last In First Out) principle, where the last
inserted element is removed first.

Operations on stack are performed only at one end called TOP.

Examples:

• Stack of plates

• Books piled one over another

====================================

ARRAY IMPLEMENTATION OF STACK

In array implementation, stack elements are stored in a linear array and a variable TOP keeps track of
the topmost element.

====================================

STRUCTURE OF ARRAY STACK

Representation:

Top

|40|

|30|

|20|

|10|

Array Representation:

Index : 0 1 2 3

Data :10 20 30 40

TOP = 3

====================================

PUSH OPERATION IN ARRAY STACK

Push inserts an element into the stack.

Example:
Initial Stack:

|30|

|20|

|10|

Push 40:

|40|

|30|

|20|

|10|

Algorithm:

Step 1: Check if TOP = MAX - 1

Step 2: If true, print "Stack Overflow"

Step 3: Otherwise increment TOP

Step 4: Insert ITEM at STACK[TOP]

Step 5: STOP

Pseudo Code:

IF TOP = MAX - 1

PRINT "OVERFLOW"

ELSE

TOP = TOP + 1

STACK[TOP] = ITEM

END IF

====================================

POP OPERATION IN ARRAY STACK

Pop removes the top element from the stack.

Example:

Initial Stack:

|40|

|30|

|20|

|10|

After POP:

|30|

|20|

|10|

Removed Element = 40

Algorithm:

Step 1: Check if TOP = -1

Step 2: If true, print "Stack Underflow"

Step 3: Otherwise store STACK[TOP]

Step 4: Decrement TOP

Step 5: STOP

====================================

ADVANTAGES OF ARRAY IMPLEMENTATION

1. Simple implementation

2. Fast access using index

3. Less memory overhead

====================================
DISADVANTAGES OF ARRAY IMPLEMENTATION

1. Fixed size

2. Memory wastage may occur

3. Stack overflow possible

====================================

LINKED LIST IMPLEMENTATION OF STACK

In linked list implementation, stack elements are stored dynamically using nodes. Each node
contains:

1. Data

2. Pointer to next node

TOP points to the first node.

====================================

STRUCTURE OF LINKED LIST STACK

Representation:

TOP

[40|•] → [30|•] → [20|•] → [10|NULL]

====================================

PUSH OPERATION IN LINKED LIST STACK

Push inserts a node at the beginning of the linked list.

Example:

Initial Stack:

[30|•] → [20|•] → [10|NULL]

Push 40:

[40|•] → [30|•] → [20|•] → [10|NULL]

Algorithm:
Step 1: Create NEWNODE

Step 2: Insert data into NEWNODE

Step 3: NEWNODE → NEXT = TOP

Step 4: TOP = NEWNODE

Step 5: STOP

Pseudo Code:

NEWNODE = CREATE NODE

NEWNODE → DATA = ITEM

NEWNODE → NEXT = TOP

TOP = NEWNODE

====================================

POP OPERATION IN LINKED LIST STACK

Pop removes the first node from the linked list.

Example:

Initial Stack:

[40|•] → [30|•] → [20|NULL]

After POP:

[30|•] → [20|NULL

Deleted Element = 40

Algorithm:

Step 1: Check if TOP = NULL

Step 2: TEMP = TOP

Step 3: TOP = TOP → NEXT

Step 4: DELETE TEMP

Step 5: STOP

====================================

ADVANTAGES OF LINKED LIST IMPLEMENTATION

1. Dynamic size

2. No stack overflow unless memory is full

3. Efficient memory utilization

====================================

DISADVANTAGES OF LINKED LIST IMPLEMENTATION

1. Extra memory required for pointers

2. More complex implementation

3. Slower access compared to arrays

====================================

COMPARISON BETWEEN ARRAY AND LINKED LIST IMPLEMENTATION

====================================

1. Memory Allocation

Array:

Static memory allocation

Linked List:

Dynamic memory allocation

--------------------------------------------------

2. Size

Array:

Fixed size

Linked List:

Flexible size
--------------------------------------------------

3. Memory Usage

Array:

Possible memory wastage

Linked List:

Efficient memory usage

--------------------------------------------------

4. Implementation

Array:

Simple

Linked List:

Complex

--------------------------------------------------

5. Overflow Condition

Array:

Occurs when stack becomes full

Linked List:

Occurs only when memory is unavailable

====================================

APPLICATIONS OF STACK

1. Function call handling

2. Expression evaluation

3. Undo and redo operations

4. Browser history

5. Parenthesis matching

CONCLUSION

Stacks can be implemented using arrays or linked lists. Array implementation is simple and faster but
has fixed size limitations. Linked list implementation provides dynamic memory allocation and efficient
memory utilization but requires extra memory for pointers. The choice of implementation depends on
application requirements.

Q7. a) Explain stack applications in detail, including recursion and expression evaluation.

Ans. APPLICATIONS OF STACK

Definition of Stack:

A stack is a linear data structure that follows the LIFO (Last In First Out) principle, where the last
inserted element is removed first.

Operations in a stack are performed only at one end called TOP.

Representation:

Top

|40|

|30|

|20|

|10|

Stacks are widely used in computer science and software development because of their efficient
insertion and deletion operations.

====================================

APPLICATIONS OF STACK

The major applications of stack are:

1. Recursion

2. Expression Evaluation

3. Parenthesis Matching

4. Undo and Redo Operations

5. Browser History

6. Backtracking

7. Memory Management

====================================

1. RECURSION

Recursion is a process in which a function calls itself repeatedly until a stopping condition is reached.

Stacks are used internally to manage recursive function calls.

Whenever a function is called:

• The current function state is pushed onto the stack

• After execution, it is popped from the stack

This mechanism is called the Call Stack.

WORKING OF RECURSION USING STACK

Example:

Factorial of 3

Factorial Formula:

3! = 3 × 2 × 1

Recursive Function:

fact(3)

fact(2)

fact(1)

Stack Representation:

Top

↓
|fact(1)|

|fact(2)|

|fact(3)|

Execution Process:

1. fact(3) is pushed

2. fact(2) is pushed

3. fact(1) is pushed

4. After execution, functions are popped one by one

Popping Order:

fact(1) → fact(2) → fact(3)

Applications of Recursion:

1. Factorial calculation

2. Fibonacci series

3. Tree traversal

4. Tower of Hanoi

ADVANTAGES OF USING STACK IN RECURSION

1. Simplifies complex problems

2. Automatic function management

3. Efficient handling of nested calls

====================================

2. EXPRESSION EVALUATION

Stacks are widely used in evaluating arithmetic expressions.

Expressions may be:

1. Infix Expression
2. Prefix Expression

3. Postfix Expression

--------------------------------------------------

a) INFIX EXPRESSION

Operator is placed between operands.

Example:

A+B

--------------------------------------------------

b) PREFIX EXPRESSION

Operator is placed before operands.

Example:

+AB

--------------------------------------------------

c) POSTFIX EXPRESSION

Operator is placed after operands.

Example:

AB+

POSTFIX EXPRESSION EVALUATION USING STACK

Example:

Expression:

53+2*

Step 1:

Push 5

Stack:

|5|

--------------------------------------------------

Step 2:
Push 3

Stack:

|3|

|5|

--------------------------------------------------

Step 3:

Operator +

Pop 3 and 5

5+3=8

Push 8

Stack:

|8|

--------------------------------------------------

Step 4:

Push 2

Stack:

|2|

|8|

--------------------------------------------------

Step 5:

Operator *

Pop 2 and 8

8 × 2 = 16

Push 16

Final Stack:

|16|

Result = 16
ALGORITHM FOR POSTFIX EVALUATION

Step 1: Scan expression from left to right

Step 2: If operand, PUSH into stack

Step 3: If operator,

POP two operands

Perform operation

PUSH result back

Step 4: Repeat until expression ends

Step 5: Final value in stack is answer

ADVANTAGES OF STACK IN EXPRESSION EVALUATION

1. Simplifies expression processing

2. Reduces complexity

3. Efficient operator handling

4. Used in compiler design

====================================

3. PARENTHESIS MATCHING

Stacks are used to check balanced parentheses.

Example:

(A + B) * (C + D)

Process:

• Opening brackets are pushed

• Closing brackets pop matching opening brackets

Applications:

• Compiler syntax checking

• Expression validation
====================================

4. UNDO AND REDO OPERATIONS

Stacks are used in text editors.

Example:

• Ctrl + Z → Undo

• Ctrl + Y → Redo

The latest action is removed first using stack operations.

====================================

5. BROWSER HISTORY

Stacks maintain previously visited web pages.

Example:

• Back button uses stack

• Forward button uses another stack

====================================

6. BACKTRACKING

Stacks help in returning to previous states.

Applications:

1. Maze solving

2. Path finding

3. Puzzle solving

====================================

7. MEMORY MANAGEMENT

Stacks are used in managing function calls and local variables in memory.

The operating system maintains a stack area for program execution.

====================================

ADVANTAGES OF STACK
1. Simple implementation

2. Efficient insertion and deletion

3. Useful in recursion and memory management

4. Supports expression evaluation

====================================

DISADVANTAGES OF STACK

1. Limited access to elements

2. Possible overflow in fixed-size stacks

3. Searching is difficult

CONCLUSION

Stacks are important linear data structures widely used in computer science applications. They are
essential in recursion, expression evaluation, parenthesis matching, browser history, undo operations,
and memory management. Due to their LIFO behavior, stacks efficiently manage nested and
sequential operations in software systems.

b) Write algorithms for PUSH and POP operations. Explain stack overflow and underflow conditions.

Ans. PUSH AND POP OPERATIONS IN STACK

Definition of Stack:

A stack is a linear data structure that follows the LIFO (Last In First Out) principle, where the last
inserted element is removed first.

All insertion and deletion operations are performed at one end called TOP.

Representation:

Top

|40|

|30|

|20|

|10|

====================================
PUSH OPERATION

PUSH operation inserts a new element into the top of the stack.

The TOP pointer is increased by one after insertion.

WORKING OF PUSH OPERATION

Example:

Initial Stack:

Top

|30|

|20|

|10|

Push Element = 40

After PUSH:

Top

|40|

|30|

|20|

|10|

====================================

ALGORITHM FOR PUSH OPERATION

Algorithm:

Step 1: Check whether stack is full

Step 2: If TOP = MAX - 1

Print "STACK OVERFLOW"

 STOP

Step 3: Otherwise increment TOP

Step 4: Insert ITEM into STACK[TOP]

Step 5: STOP

Pseudo Code:

IF TOP = MAX - 1

PRINT "STACK OVERFLOW"

ELSE

TOP = TOP + 1

STACK[TOP] = ITEM

END IF

====================================

POP OPERATION

POP operation removes the top element from the stack.

After deletion, the TOP pointer is decreased by one.

WORKING OF POP OPERATION

Example:

Initial Stack:

Top

|40|

|30|

|20|

|10|

After POP:
Top

|30|

|20|

|10|

Deleted Element = 40

====================================

ALGORITHM FOR POP OPERATION

Algorithm:

Step 1: Check whether stack is empty

Step 2: If TOP = -1

Print "STACK UNDERFLOW"

STOP

Step 3: Store STACK[TOP] into ITEM

Step 4: Decrement TOP

Step 5: Return ITEM

Step 6: STOP

Pseudo Code:

IF TOP = -1

PRINT "STACK UNDERFLOW"

ELSE

ITEM = STACK[TOP]

TOP = TOP - 1

END IF

====================================

STACK OVERFLOW CONDITION

Stack Overflow occurs when an insertion (PUSH) operation is performed on a full stack.

Condition:

TOP = MAX - 1

Example:

If stack size = 4

Top

|40|

|30|

|20|

|10|

Attempt to PUSH 50 results in:

STACK OVERFLOW

Causes:

1. Fixed stack size

2. Excessive insertion operations

Effects:

1. Program interruption

2. Memory allocation problems

====================================

STACK UNDERFLOW CONDITION

Stack Underflow occurs when a deletion (POP) operation is performed on an empty stack.

Condition:

TOP = -1
Example:

Empty Stack:

TOP = -1

Attempt to POP an element results in:

STACK UNDERFLOW

Causes:

1. Deleting from empty stack

2. Excessive POP operations

Effects:

1. Runtime errors

2. Invalid data access

====================================

ADVANTAGES OF STACK

1. Simple implementation

2. Efficient insertion and deletion

3. Useful in recursion

4. Supports expression evaluation

====================================

APPLICATIONS OF STACK

1. Function call management

2. Undo and redo operations

3. Browser history

4. Expression evaluation

5. Parenthesis matching

CONCLUSION
PUSH and POP are the fundamental operations of a stack. PUSH inserts elements into the stack,
while POP removes elements from the stack according to the LIFO principle. Stack overflow occurs
when insertion is attempted on a full stack, whereas stack underflow occurs when deletion is
attempted on an empty stack. These operations are essential in recursion, memory management,
and expression evaluation applications.

Q8. a) Define Queue ADT. Explain queue operations with algorithms and examples.

Ans. QUEUE ADT

A Queue Abstract Data Type (ADT) is a linear data structure that follows the FIFO (First In First Out)
principle, where the element inserted first is removed first.

Insertion is performed at the REAR end and deletion is performed at the FRONT end.

Examples of queue in real life:

• People standing in a ticket line

• Printer queue

• Waiting line in banks

====================================

STRUCTURE OF QUEUE

Representation:

Front → 10 20 30 40 ← Rear

Where:

• FRONT points to the first element

• REAR points to the last element

====================================

CHARACTERISTICS OF QUEUE

1. Follows FIFO principle

2. Insertion occurs at REAR

3. Deletion occurs at FRONT

4. Can be implemented using arrays or linked lists

====================================

QUEUE OPERATIONS
The main operations performed on a queue are:

1. ENQUEUE

2. DEQUEUE

3. PEEK (FRONT)

4. DISPLAY

====================================

1. ENQUEUE OPERATION

Enqueue operation inserts an element into the rear of the queue.

WORKING OF ENQUEUE

Example:

Initial Queue:

Front → 10 20 30 ← Rear

Insert 40

New Queue:

Front → 10 20 30 40 ← Rear

ALGORITHM FOR ENQUEUE

Algorithm:

Step 1: Check whether queue is full

Step 2: If REAR = MAX - 1

Print "QUEUE OVERFLOW"

STOP

Step 3: If queue is empty, set FRONT = 0

Step 4: Increment REAR

Step 5: Insert ITEM at QUEUE[REAR]

Step 6: STOP

Pseudo Code:
IF REAR = MAX - 1

PRINT "QUEUE OVERFLOW"

ELSE

IF FRONT = -1

FRONT = 0

END IF

REAR = REAR + 1

QUEUE[REAR] = ITEM

END IF

====================================

2. DEQUEUE OPERATION

Dequeue operation removes an element from the front of the queue.

WORKING OF DEQUEUE

Example:

Initial Queue:

Front → 10 20 30 40 ← Rear

Delete Element = 10

New Queue:

Front → 20 30 40 ← Rear

ALGORITHM FOR DEQUEUE

Algorithm:

Step 1: Check whether queue is empty

Step 2: If FRONT = -1 OR FRONT > REAR

Print "QUEUE UNDERFLOW"

STOP

Step 3: Store QUEUE[FRONT] into ITEM

Step 4: Increment FRONT

Step 5: Return ITEM

Step 6: STOP

Pseudo Code:

IF FRONT = -1 OR FRONT > REAR

PRINT "QUEUE UNDERFLOW"

ELSE

ITEM = QUEUE[FRONT]

FRONT = FRONT + 1

END IF

====================================

3. PEEK OPERATION

Peek operation displays the front element without deleting it.

Example:

Front → 10 20 30 ← Rear

Peek Element = 10

Algorithm:

Step 1: Check whether queue is empty

Step 2: If empty, print "QUEUE EMPTY"

Step 3: Otherwise display QUEUE[FRONT]

====================================

4. DISPLAY OPERATION

Display operation prints all elements from FRONT to REAR.

Example:

Front → 10 20 30 40 ← Rear
Display Output:

10 20 30 40

Algorithm:

Step 1: Traverse from FRONT to REAR

Step 2: Print each element

====================================

QUEUE OVERFLOW CONDITION

Queue Overflow occurs when insertion is attempted on a full queue.

Condition:

REAR = MAX - 1

====================================

QUEUE UNDERFLOW CONDITION

Queue Underflow occurs when deletion is attempted on an empty queue.

Condition:

FRONT = -1 OR FRONT > REAR

====================================

ADVANTAGES OF QUEUE

1. Efficient data processing

2. Maintains proper order of execution

3. Useful in scheduling systems

4. Easy implementation

====================================

DISADVANTAGES OF QUEUE

1. Fixed size in array implementation

2. Memory wastage may occur

3. Limited access to elements

====================================
APPLICATIONS OF QUEUE

1. CPU scheduling

2. Printer spooling

3. Ticket booking systems

4. Data buffering

5. Network packet handling

====================================

CONCLUSION

A Queue ADT is a linear data structure that follows the FIFO principle. The main operations are
enqueue, dequeue, peek, and display. Queues are widely used in scheduling, buffering, networking,
and resource management applications because they process data in the order of arrival.

b) Discuss different types of queues and their applications.

Ans. TYPES OF QUEUES AND THEIR APPLICATIONS

Definition of Queue:

A queue is a linear data structure that follows the FIFO (First In First Out) principle, where the
element inserted first is removed first.

Insertion is performed at the REAR end and deletion is performed at the FRONT end.

Representation:

Front → 10 20 30 40 ← Rear

Queues are widely used in computer science for scheduling, buffering, and resource management.

TYPES OF QUEUES

The main types of queues are:

1. Simple Queue

2. Circular Queue

3. Priority Queue

4. Double Ended Queue (Deque)

====================================

1. SIMPLE QUEUE
A simple queue is a linear queue in which insertion takes place at the REAR and deletion takes place
at the FRONT.

It follows FIFO order strictly.

====================================

STRUCTURE OF SIMPLE QUEUE

Representation:

Front → 10 20 30 40 ← Rear

Operations:

• Enqueue

• Dequeue

====================================

ADVANTAGES OF SIMPLE QUEUE

1. Easy implementation

2. Maintains order of processing

3. Efficient scheduling

====================================

APPLICATIONS OF SIMPLE QUEUE

1. Printer queue

2. Ticket booking systems

3. CPU scheduling

4. Call center systems

====================================

2. CIRCULAR QUEUE

A circular queue is a queue in which the last position is connected back to the first position, forming a
circular structure.

It efficiently utilizes memory.

====================================

STRUCTURE OF CIRCULAR QUEUE

Representation:

Front

10 20 30

↑ ↓

50 ← 40

Rear

====================================

ADVANTAGES OF CIRCULAR QUEUE

1. Efficient memory utilization

2. Reduces memory wastage

3. Faster operations

====================================

APPLICATIONS OF CIRCULAR QUEUE

1. CPU scheduling

2. Traffic signal systems

3. Multimedia streaming

4. Keyboard buffering

====================================

3. PRIORITY QUEUE

A priority queue is a queue in which elements are processed according to their priority rather than
insertion order.

Higher priority elements are removed first.

====================================

STRUCTURE OF PRIORITY QUEUE

Example:
Priority Element

1 A

2 B

3 C

Element with highest priority is processed first.

====================================

TYPES OF PRIORITY QUEUE

1. Ascending Priority Queue

2. Descending Priority Queue

====================================

ADVANTAGES OF PRIORITY QUEUE

1. Efficient priority management

2. Faster important task processing

3. Useful in real-time systems

====================================

APPLICATIONS OF PRIORITY QUEUE

1. Operating system scheduling

2. Emergency services

3. Network routing

4. Dijkstra’s shortest path algorithm

====================================

4. DOUBLE ENDED QUEUE (DEQUE)

A deque (Double Ended Queue) is a queue in which insertion and deletion can occur at both FRONT
and REAR ends.

====================================

STRUCTURE OF DEQUE
Representation:

Front ⇄ 10 20 30 40 ⇄ Rear
TYPES OF DEQUE

1. Input Restricted Deque

• Insertion allowed at one end only

• Deletion allowed at both ends

2. Output Restricted Deque

• Deletion allowed at one end only

• Insertion allowed at both ends

====================================

ADVANTAGES OF DEQUE

1. Flexible insertion and deletion

2. Efficient processing

3. Useful for complex applications

====================================

APPLICATIONS OF DEQUE

1. Browser history

2. Undo and redo operations

3. Palindrome checking

4. Task scheduling

====================================

COMPARISON OF DIFFERENT TYPES OF QUEUES

1. Simple Queue

• FIFO order

• Insertion at rear

• Deletion at front

--------------------------------------------------
2. Circular Queue

• Circular structure

• Better memory utilization

--------------------------------------------------

3. Priority Queue

• Elements processed by priority

--------------------------------------------------

4. Deque

• Insertion and deletion at both ends

====================================

ADVANTAGES OF QUEUES

1. Efficient scheduling

2. Proper data processing order

3. Useful in resource sharing

4. Supports multitasking systems

CONCLUSION

Queues are important linear data structures used for orderly processing of data. Different types of
queues such as simple queue, circular queue, priority queue, and deque are designed for different
applications. They are widely used in operating systems, scheduling, networking, buffering, and real-
time processing systems.

Q9. a) Explain array implementation of queues with enqueue and dequeue algorithms.

Ans. ARRAY IMPLEMENTATION OF QUEUE

Definition of Queue:

A queue is a linear data structure that follows the FIFO (First In First Out) principle, where the
element inserted first is removed first.

Insertion is performed at the REAR end and deletion is performed at the FRONT end.

====================================

ARRAY IMPLEMENTATION OF QUEUE

In array implementation, queue elements are stored in a linear array. Two variables are used:

1. FRONT – points to the first element

2. REAR – points to the last element

Initially:

FRONT = -1

REAR = -1

====================================

STRUCTURE OF QUEUE USING ARRAY

Representation:

Front → 10 20 30 40 ← Rear

Array Representation:

Index : 0 1 2 3

Data :10 20 30 40

FRONT = 0

REAR = 3

====================================

ENQUEUE OPERATION

Enqueue operation inserts an element into the REAR of the queue.

====================================

WORKING OF ENQUEUE

Example:

Initial Queue:

Front → 10 20 30 ← Rear

Insert 40

New Queue:
Front → 10 20 30 40 ← Rear

====================================

ALGORITHM FOR ENQUEUE

Algorithm:

Step 1: Check whether queue is full

Step 2: If REAR = MAX - 1

Print "QUEUE OVERFLOW"

STOP

Step 3: If FRONT = -1

Set FRONT = 0

Step 4: Increment REAR

Step 5: Insert ITEM into QUEUE[REAR]

Step 6: STOP

Pseudo Code:

IF REAR = MAX - 1

PRINT "QUEUE OVERFLOW"

ELSE

IF FRONT = -1

FRONT = 0

END IF

REAR = REAR + 1

QUEUE[REAR] = ITEM

END IF

====================================

DEQUEUE OPERATION

Dequeue operation removes an element from the FRONT of the queue.

====================================

WORKING OF DEQUEUE

Example:

Initial Queue:

Front → 10 20 30 40 ← Rear

Delete Element = 10

New Queue:

Front → 20 30 40 ← Rear

====================================

ALGORITHM FOR DEQUEUE

Algorithm:

Step 1: Check whether queue is empty

Step 2: If FRONT = -1 OR FRONT > REAR

Print "QUEUE UNDERFLOW"

STOP

Step 3: Store QUEUE[FRONT] into ITEM

Step 4: Increment FRONT

Step 5: Return ITEM

Step 6: STOP

Pseudo Code:

IF FRONT = -1 OR FRONT > REAR

PRINT "QUEUE UNDERFLOW"

ELSE

ITEM = QUEUE[FRONT]

FRONT = FRONT + 1

END IF
====================================

QUEUE OVERFLOW CONDITION

Queue Overflow occurs when insertion is attempted on a full queue.

Condition:

REAR = MAX - 1

Example:

Queue Size = 4

Front → 10 20 30 40 ← Rear

Attempt to insert another element results in:

QUEUE OVERFLOW

====================================

QUEUE UNDERFLOW CONDITION

Definition:

Queue Underflow occurs when deletion is attempted on an empty [Link]:

FRONT = -1 OR FRONT > REAR

Example:

Empty Queue:

FRONT = -1

REAR = -1

Attempt to delete an element results in:

QUEUE UNDERFLO

====================================

ADVANTAGES OF ARRAY IMPLEMENTATION OF QUEUE

1. Simple implementation

2. Faster access using index

3. Efficient insertion and deletion

====================================
DISADVANTAGES OF ARRAY IMPLEMENTATION OF QUEUE

1. Fixed size

2. Memory wastage may occur

3. Queue overflow possible

====================================

APPLICATIONS OF QUEUE

1. CPU scheduling

2. Printer queue

3. Ticket booking systems

4. Data buffering

5. Network packet management

====================================

CONCLUSION

In array implementation of queue, elements are stored in a linear array using FRONT and REAR
pointers. Enqueue operation inserts elements at the rear, while dequeue operation removes elements
from the front according to FIFO principle. Array queues are simple and efficient but suffer from fixed
size limitations and memory wastage.

b) Explain circular queue with suitable diagrams and algorithms.

Ans. CIRCULAR QUEUE

A circular queue is a linear data structure in which the last position is connected back to the first
position, forming a circular structure.

It follows the FIFO (First In First Out) principle and efficiently utilizes memory by reusing empty
spaces created after deletion.

====================================

STRUCTURE OF CIRCULAR QUEUE

Representation:

FRONT

10 20 30
 ↑ ↓

50 ← 40

REAR

In a circular queue:

• Insertion is performed at REAR

• Deletion is performed at FRONT

• After the last position, REAR moves to the first position

====================================

CHARACTERISTICS OF CIRCULAR QUEUE

1. Follows FIFO principle

2. Last position connects to first position

3. Efficient memory utilization

4. Prevents memory wastage

5. REAR and FRONT move circularly

====================================

WORKING OF CIRCULAR QUEUE

Example:

Queue Size = 5

Step 1: Insert Elements

FRONT = 0

REAR = 4

FRONT

10 20 30

↑ ↓
 50 ← 40

REAR

--------------------------------------------------

Step 2: Delete Two Elements

Deleted:

10 and 20

Now FRONT moves forward.

--------------------------------------------------

Step 3: Insert New Elements

New elements are inserted into freed spaces at the beginning of array.

This avoids memory wastage.

====================================

ENQUEUE OPERATION

Enqueue operation inserts an element into the circular queue at the REAR end.

====================================

ALGORITHM FOR ENQUEUE

Algorithm:

Step 1: Check if queue is full

Step 2: If (REAR + 1) % MAX = FRONT

Print "QUEUE OVERFLOW"

STOP

Step 3: If queue is empty

Set FRONT = 0 and REAR = 0

Step 4: Otherwise

REAR = (REAR + 1) % MAX

Step 5: Insert ITEM into QUEUE[REAR]

Step 6: STOP

Pseudo Code:

IF (REAR + 1) % MAX = FRONT

PRINT "QUEUE OVERFLOW"

ELSE

IF FRONT = -1

FRONT = 0

REAR = 0

ELSE

REAR = (REAR + 1) % MAX

END IF

QUEUE[REAR] = ITEM

END IF

====================================

DEQUEUE OPERATION

Dequeue operation removes an element from the FRONT end of the circular queue.

====================================

ALGORITHM FOR DEQUEUE

Algorithm:

Step 1: Check if queue is empty

Step 2: If FRONT = -1

Print "QUEUE UNDERFLOW"

STOP

Step 3: Store QUEUE[FRONT] into ITEM

Step 4: If FRONT = REAR

 Set FRONT = REAR = -1

Else

FRONT = (FRONT + 1) % MAX

Step 5: Return ITEM

Step 6: STOP

Pseudo Code:

IF FRONT = -1

PRINT "QUEUE UNDERFLOW"

ELSE

ITEM = QUEUE[FRONT]

IF FRONT = REAR

FRONT = -1

REAR = -1

ELSE

FRONT = (FRONT + 1) % MAX

END IF

END IF

====================================

ADVANTAGES OF CIRCULAR QUEUE

1. Efficient memory utilization

2. Reuses empty spaces

3. Faster insertion and deletion

4. Prevents memory wastage

5. Suitable for continuous processing

====================================

DISADVANTAGES OF CIRCULAR QUEUE

1. Complex implementation
2. Difficult pointer management

3. Overflow and underflow conditions must be handled carefully

====================================

APPLICATIONS OF CIRCULAR QUEUE

1. CPU scheduling

2. Traffic signal systems

3. Multimedia streaming

4. Keyboard buffering

5. Circular task scheduling

====================================

DIFFERENCE BETWEEN SIMPLE QUEUE AND CIRCULAR QUEUE

Simple Queue:

• Linear structure

• Memory wastage possible

• Rear cannot reuse empty spaces

Circular Queue:

• Circular structure

• Efficient memory utilization

• Rear can reuse empty spaces

CONCLUSION

A circular queue is an improved form of queue in which the last position connects back to the first
position. It efficiently utilizes memory by reusing vacant spaces and supports FIFO processing.
Circular queues are widely used in scheduling, buffering, and real-time processing applications.

Q10. a) Compare stacks and queues with examples and applications.

Ans. COMPARISON BETWEEN STACKS AND QUEUES

Stacks and queues are important linear data structures used for storing and processing data
efficiently. Both support insertion and deletion operations, but they differ in the order in which
elements are processed.
====================================

STACK

A stack is a linear data structure that follows the LIFO (Last In First Out) principle, where the last
inserted element is removed first.

Insertion and deletion take place at one end called TOP.

====================================

STRUCTURE OF STACK

Representation:

Top

|40|

|30|

|20|

|10|

Operations:

1. PUSH

2. POP

3. PEEK

Example:

Push 50:

Top

|50|

|40|

|30|

|20|

|10|

After POP:
Top

|40|

|30|

|20|

|10|

====================================

QUEUE

A queue is a linear data structure that follows the FIFO (First In First Out) principle, where the first
inserted element is removed first.

Insertion occurs at REAR and deletion occurs at FRONT.

====================================

STRUCTURE OF QUEUE

Representation:

Front → 10 20 30 40 ← Rear

Operations:

1. ENQUEUE

2. DEQUEUE

3. PEEK

Example:

Enqueue 50:

Front → 10 20 30 40 50 ← Rear

After DEQUEUE:

Front → 20 30 40 50 ← Rear

Deleted Element = 10

====================================

COMPARISON BETWEEN STACK AND QUEUE

1. Principle Followed
Stack:

Follows LIFO (Last In First Out)

Queue:

Follows FIFO (First In First Out)

--------------------------------------------------

2. Insertion and Deletion

Stack:

Insertion and deletion occur at same end (TOP)

Queue:

Insertion occurs at REAR and deletion occurs at FRONT

--------------------------------------------------

3. Order of Processing

Stack:

Last inserted element processed first

Queue:

First inserted element processed first

--------------------------------------------------

4. Main Operations

Stack:

PUSH and POP

Queue:

ENQUEUE and DEQUEUE

--------------------------------------------------

5. Pointers Used

Stack:

Uses TOP pointer

Queue:
Uses FRONT and REAR pointers

--------------------------------------------------

6. Structure Representation

Stack:

Vertical arrangement

Queue:

Linear arrangement

--------------------------------------------------

7. Complexity

Stack:

Simple implementation

Queue:

Slightly more complex due to two pointers

====================================

ADVANTAGES OF STACK

1. Simple implementation

2. Efficient recursion handling

3. Useful in expression evaluation

4. Fast insertion and deletion

====================================

ADVANTAGES OF QUEUE

1. Maintains proper processing order

2. Efficient scheduling

3. Useful in resource sharing

4. Supports buffering operations

====================================

APPLICATIONS OF STACK
1. Function call management

2. Recursion

3. Expression evaluation

4. Undo and redo operations

5. Browser history

6. Parenthesis matching

====================================

APPLICATIONS OF QUEUE

1. CPU scheduling

2. Printer queue

3. Ticket booking systems

4. Network packet processing

5. Data buffering

6. Call center systems

====================================

REAL LIFE EXAMPLES

Stack Example:

Stack of plates:

The plate placed last is removed first.

--------------------------------------------------

Queue Example:

People standing in a line:

The person who comes first leaves first.

CONCLUSION

Stacks and queues are fundamental linear data structures used for efficient data management. A
stack follows the LIFO principle and is mainly used in recursion, expression evaluation, and undo
operations. A queue follows the FIFO principle and is widely used in scheduling, buffering, and
resource management systems. The choice between stack and queue depends on the application
requirements.
b) Discuss real-life applications of stacks and queues in computer science.

Ans. REAL-LIFE APPLICATIONS OF STACKS AND QUEUES IN COMPUTER SCIENCE

Stacks and queues are important linear data structures widely used in computer science and software
development. They help in organizing, processing, and managing data efficiently according to specific
principles.

A stack follows the LIFO (Last In First Out) principle, while a queue follows the FIFO (First In First
Out) principle.

====================================

STACK

A stack is a linear data structure in which insertion and deletion occur at one end called TOP.

It follows the LIFO principle.

Representation:

Top

|40|

|30|

|20|

|10|

Main Operations:

1. PUSH

2. POP

3. PEEK

====================================

REAL-LIFE APPLICATIONS OF STACK

1. Function Call Management

Stacks are used by operating systems to manage function calls.

Whenever a function is called:

• Function details are pushed onto the stack

• After execution, they are popped

This mechanism is called Call Stack.

Example:

Recursive function execution

--------------------------------------------------

2. Recursion

Recursive functions use stacks internally.

Example:

Factorial calculation

Fibonacci series

Stack stores:

• Function calls

• Return addresses

• Local variables

--------------------------------------------------

3. Expression Evaluation

Stacks are used in:

• Infix to postfix conversion

• Postfix evaluation

• Prefix evaluation

Example:

Expression:

53+2*

Result = 16

--------------------------------------------------

4. Undo and Redo Operations

Text editors use stacks for undo and redo features.

Examples:

• Ctrl + Z → Undo

• Ctrl + Y → Redo

Latest action is removed first using LIFO order.

--------------------------------------------------

5. Browser History

Web browsers use stacks to store visited pages.

Applications:

• Back button

• Forward button

--------------------------------------------------

6. Parenthesis Matching

Stacks help in checking balanced parentheses in programs and expressions.

Example:

(A + B) * (C + D)

Used in:

• Compiler design

• Syntax checking

--------------------------------------------------

7. Backtracking Algorithms

Stacks are used for returning to previous states.

Applications:

1. Maze solving

2. Puzzle solving

3. Path finding

--------------------------------------------------

8. Memory Management
Operating systems use stacks for:

• Local variable storage

• Function execution

• Interrupt handling

====================================

QUEUE

A queue is a linear data structure in which insertion occurs at REAR and deletion occurs at FRONT.

It follows the FIFO principle.

Representation:

Front → 10 20 30 40 ← Rear

Main Operations:

1. ENQUEUE

2. DEQUEUE

3. PEEK

====================================

REAL-LIFE APPLICATIONS OF QUEUE

1. CPU Scheduling

Operating systems use queues for process scheduling.

Processes are executed in the order of arrival.

Example:

Round Robin Scheduling

--------------------------------------------------

2. Printer Queue

Documents waiting for printing are stored in a queue.

The document sent first is printed first.

--------------------------------------------------

3. Ticket Booking Systems

People waiting for tickets are processed in FIFO order.

Applications:

• Railway booking

• Movie ticket booking

--------------------------------------------------

4. Network Packet Processing

Routers and switches use queues to process network packets.

Packets are handled in arrival order.

--------------------------------------------------

5. Data Buffering

Queues are used in buffering systems.

Examples:

• Keyboard buffering

• Video streaming

• Audio streaming

--------------------------------------------------

6. Call Center Systems

Customer calls are stored in queues and answered in order.

--------------------------------------------------

7. Breadth First Search (BFS)

Queues are used in graph traversal algorithms.

Applications:

• Shortest path finding

• Social network analysis

--------------------------------------------------

8. Task Scheduling

Queues manage tasks in:

• Multitasking systems

• Operating systems

• Real-time systems

====================================

COMPARISON OF STACKS AND QUEUES

Stack:

• Follows LIFO principle

• Insertion and deletion at TOP

• Used in recursion and expression evaluation

Queue:

• Follows FIFO principle

• Insertion at REAR and deletion at FRONT

• Used in scheduling and buffering

====================================

ADVANTAGES OF STACKS AND QUEUES

1. Efficient data management

2. Faster insertion and deletion

3. Improved system performance

4. Useful in real-time applications

CONCLUSION

Stacks and queues are fundamental data structures widely used in computer science applications.
Stacks are mainly used in recursion, expression evaluation, browser history, and undo operations,
whereas queues are used in scheduling, buffering, networking, and resource management systems.
Their efficient processing methods improve the performance and reliability of software applications.

Answer the below short questions -(2 Marks)

1. Define Data Structure.

Ans. A data structure is a method of organizing and storing data in a computer so that it can be
accessed and modified efficiently.
Examples:

• Array

• Linked List

• Stack

• Queue

2. What is an Abstract Data Type (ADT)?

Ans. An Abstract Data Type (ADT) is a logical model that defines data and the operations performed
on it without specifying implementation details.

Examples:

• Stack ADT

• Queue ADT

3. Differentiate between Linear and Non-Linear Data Structures.

Ans. Linear Data Structure:

• Elements are arranged sequentially

• Traversal occurs in single level

• Examples: Array, Stack, Queue

Non-Linear Data Structure:

• Elements are arranged hierarchically

• Traversal occurs in multiple levels

• Examples: Tree, Graph

4. What is a Linked List?

Ans. A linked list is a dynamic linear data structure consisting of nodes connected using pointers.

Representation:

[10|•] → [20|•] → [30|NULL]

5. Define a Node in a Linked List.

Ans. A node is the basic unit of a linked list that contains:

1. Data

2. Pointer to the next node

Representation:

[data | next]

6. What is the Difference Between Singly Linked List and Doubly Linked List?

Ans. Singly Linked List:

• Contains one pointer

• Traversal only in forward direction

Representation:

[10|•] → [20|NULL]

Doubly Linked List:

• Contains two pointers

• Traversal in both forward and backward directions

Representation:

NULL ← [10|•|•] ⇄ [20|•|NULL]

7. Define Stack and Mention its Principle.

Ans. A stack is a linear data structure in which insertion and deletion occur at one end called TOP.

Principle:

LIFO (Last In First Out)

Representation:

Top

|30|

|20|

|10|

8. What is Stack Overflow?

Ans. Stack Overflow is a condition that occurs when insertion is attempted on a full stack.

Condition:

TOP = MAX - 1

9. Define Queue and Mention its Principle.

Ans. A queue is a linear data structure in which insertion occurs at REAR and deletion occurs at
FRONT.

Principle:

FIFO (First In First Out)

Representation:

Front → 10 20 30 ← Rear

10. What is the Difference Between Enqueue and Dequeue Operations?

Ans. Enqueue:

• Inserts an element into the queue

• Performed at REAR end

Dequeue:

• Removes an element from the queue

• Performed at FRONT end