UNIT-1

Introduction to Data Structures

What is Data Structure?

A data structure is a particular way of organising data in a computer so that it can be used effectively.
The idea is to reduce the space and time complexities of different tasks.

Need Of Data Structure:

The structure of the data and the synthesis of the algorithm are relative to each other. Data
presentation must be easy to understand so the developer, as well as the user, can make an efficient
implementation of the operation. Data structures provide an easy way of organising, retrieving,
managing, and storing data.

Here is a list of the needs for data.

 Data structure modification is easy.

 It requires less time.

 Save storage memory space.

 Data representation is easy.

 Easy access to the large database

Classification/Types of Data Structures:

1. Linear Data Structure

2. Non-Linear Data Structure.

Linear Data Structure:

 Elements are arranged in one dimension ,also known as linear dimension.

 Example: lists, stack, queue, etc.

Non-Linear Data Structure

 Elements are arranged in one-many, many-one and many-many dimensions.

 Example: tree, graph, table, etc.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

1. Array:

An array is a collection of data items stored at contiguous memory locations. The idea is to store
multiple items of the same type together. This makes it easier to calculate the position of each element
by simply adding an offset to a base value, i.e., the memory location of the first element of the array
(generally denoted by the name of the array).

2. Linked Lists:

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a
contiguous location; the elements are linked using pointers.

3. Stack:

Stack is a linear data structure which follows a particular order in which the operations are performed.
The order may be LIFO (Last In First Out) or FILO (First In Last Out). In stack, all insertion and deletion
are permitted at only one end of the list.

Stack Operations:

 push(): When this operation is performed, an element is inserted into the stack.

 pop(): When this operation is performed, an element is removed from the top of the stack and
is returned.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  top(): This operation will return the last inserted element that is at the top without removing
it.

 size(): This operation will return the size of the stack i.e. the total number of elements present
in the stack.

 isEmpty(): This operation indicates whether the stack is empty or not.

4. Queue:
Like Stack, Queue is a linear structure which follows a particular order in which the operations
are performed. The order is First In First Out (FIFO). In the queue, items are inserted at one
end and deleted from the other end. A good example of the queue is any queue of consumers
for a resource where the consumer that came first is served first. The difference between
stacks and queues is in removing. In a stack we remove the item the most recently added; in
a queue, we remove the item the least recently added.

Queue Operations:

 Enqueue(): Adds (or stores) an element to the end of the queue..

 Dequeue(): Removal of elements from the queue.

 Peek() or front(): Acquires the data element available at the front node of the queue without
deleting it.

 rear(): This operation returns the element at the rear end without removing it.

 isFull(): Validates if the queue is full.

 isNull(): Checks if the queue is empty.

5. Binary Tree:
Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are
hierarchical data structures. A binary tree is a tree data structure in which each node has at
most two children, which are referred to as the left child and the right child. It is
implemented mainly using Links.

A Binary Tree is represented by a pointer to the topmost node in the tree. If the tree is
empty, then the value of root is NULL. A Binary Tree node contains the following parts.
 1. Data
2. Pointer to left child
3. Pointer to the right child

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

6. Binary Search Tree:

A Binary Search Tree is a Binary Tree following the additional properties:

 The left part of the root node contains keys less than the root node key.

 The right part of the root node contains keys greater than the root node key.

 There is no duplicate key present in the binary tree.

A Binary tree having the following properties is known as Binary search tree (BST).

7. Heap:

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally,
Heaps can be of two types:

 Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys
present at all of its children. The same property must be recursively true for all sub-trees in
that Binary Tree.

 Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys
present at all of its children. The same property must be recursively true for all sub-trees in
that Binary Tree.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

8. Hash Table Data Structure:

Hashing is an important Data Structure which is designed to use a special function called the Hash
function which is used to map a given value with a particular key for faster access of elements. The
efficiency of mapping depends on the efficiency of the hash function used.

Let a hash function H(x) maps the value x at the index x%10 in an Array. For example, if the list of values
is [11, 12, 13, 14, 15] it will be stored at positions {1, 2, 3, 4, 5} in the array or Hash table respectively.

9. Matrix:

A matrix represents a collection of numbers arranged in an order of rows and columns. It is necessary
to enclose the elements of a matrix in parentheses or brackets.

A matrix with 9 elements is shown below.

10. Trie:

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought
to an optimal limit (key length). If we store keys in the binary search tree, a well-balanced BST will need
time proportional to M * log N, where M is maximum string length and N is the number of keys in the
tree. Using Trie, we can search the key in O(M) time. However, the penalty is on Trie storage
requirements.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

11. Graph:

Graph is a data structure that consists of a collection of nodes (vertices) connected by edges. Graphs
are used to represent relationships between objects and are widely used in computer science,
mathematics, and other fields. Graphs can be used to model a wide variety of real-world systems, such
as social networks, transportation networks, and computer networks.

Applications of Data Structures:

Data structures are used in various fields such as:

 Operating system

 Graphics

 Computer Design

 Blockchain

 Genetics

 Image Processing

 Simulation, etc.

Abstract Data Types:

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and behaviours
for a data structure, without specifying how these operations are implemented or how data is
organized in memory. The definition of ADT only mentions what operations are to be performed but
not how these operations will be implemented. It does not specify how data will be organized in
memory and what algorithms will be used for implementing the operations. It is called "abstract"
because it provides an implementation-independent view.
Features of ADT
Abstract data types (ADTs) are a way of encapsulating data and operations on that data into a single
unit. Some of the key features of ADTs include:
 Abstraction: The user does not need to know the implementation of the data structure only
essentials are provided.
 Better Conceptualization: ADT gives us a better conceptualization of the real world.
 Robust: The program is robust and has the ability to catch errors.
 Encapsulation: ADTs hide the internal details of the data and provide a public interface for
users to interact with the data. This allows for easier maintenance and modification of the
data structure.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  Data Abstraction: ADTs provide a level of abstraction from the implementation details of the
data. Users only need to know the operations that can be performed on the data, not how
those operations are implemented.
 Data Structure Independence: ADTs can be implemented using different data structures, such
as arrays or linked lists, without affecting the functionality of the ADT.
 Information Hiding: ADTs can protect the integrity of the data by allowing access only to
authorized users and operations. This helps prevent errors and misuse of the data.
 Modularity: ADTs can be combined with other ADTs to form larger, more complex data
structures. This allows for greater flexibility and modularity in programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a structured and efficient
manner.
This image demonstrates how an Abstract Data Type (ADT) hides internal data structures (like arrays,
linked lists) using public and private functions, exposing only a defined interface to the application
program.

Why Use ADTs?

The key reasons to use ADTs in Java are listed below:
 Encapsulation: Hides complex implementation details behind a clean interface.
 Reusability: Allows different internal implementations (e.g., array or linked list) without
changing external usage.
 Modularity: Simplifies maintenance and updates by separating logic.
 Security: Protects data by preventing direct access, minimizing bugs and unintended changes.
Example of Abstraction:
For example, we use primitive values like int, float, and char with the understanding that these data
types can operate and be performed on without any knowledge of their implementation details. ADTs
operate similarly by defining what operations are possible without detailing their implementation.
Difference Between ADTs and UDTs
The table below demonstrates the difference between ADTs and UDTs.
Aspect Abstract Data Types (ADTs) User-Defined Data Types (UDTs)

Defines a class of objects and the

A custom data type created by
operations that can be performed on
combining or extending existing
them, along with their expected behavior
primitive types, specifying both
(semantics), but without specifying
structure and operations.
Definition implementation details.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Aspect Abstract Data Types (ADTs) User-Defined Data Types (UDTs)

What operations are allowed and how

How data is organized in memory
they behave, without dictating how they
and how operations are executed.
Focus are implemented.

Allows programmers to create

Provides an abstract model to define data
concrete implementations of data
structures in a conceptual way.
Purpose structures using primitive types.

Specifies how to create and

Does not specify how operations are
Implementation organize data types to implement
implemented or how data is structured.
Details the structure.

Used to implement data

Used to design and conceptualize data
structures that realize the abstract
structures.
Usage concepts defined by ADTs.

Structures, classes, enumerations,

List ADT, Stack ADT, Queue ADT.
Example records.

Examples of ADTs:
Now, let's understand three common ADT's: List ADT, Stack ADT, and Queue ADT.
1. List ADT
The List ADT (Abstract Data Type) is a sequential collection of elements that supports a set of
operations without specifying the internal implementation. It provides an ordered way to store,
access, and modify data.

Operations:
The List ADT need to store the required data in the sequence and should have the following operations:
 get (): Return an element from the list at any given position.
 insert(): Insert an element at any position in the list.
 remove(): Remove the first occurrence of any element from a non-empty list.
 removeAt(): Remove the element at a specified location from a non-empty list.
 replace(): Replace an element at any position with another element.
 size(): Return the number of elements in the list.
 isEmpty(): Return true if the list is empty; otherwise, return false.
 isFull(): Return true if the list is full, otherwise, return false. Only applicable in fixed-size
implementations (e.g., array-based lists).
2. Stack ADT

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out) principle. It allows
elements to be added and removed only from one end, called the top of the stack.

Operations:
In Stack ADT, the order of insertion and deletion should be according to the FILO or LIFO Principle.
Elements are inserted and removed from the same end, called the top of the stack. It should also
support the following operations:
 push(): Insert an element at one end of the stack called the top.
 pop(): Remove and return the element at the top of the stack, if it is not empty.
 peek(): Return the element at the top of the stack without removing it, if the stack is not
empty.
 size(): Return the number of elements in the stack.
 isEmpty(): Return true if the stack is empty; otherwise, return false.
 isFull(): Return true if the stack is full; otherwise, return false. Only relevant for fixed-capacity
stacks (e.g., array-based).
3. Queue ADT
The Queue ADT is a linear data structure that follows the FIFO (First In, First Out) principle. It allows
elements to be inserted at one end (rear) and removed from the other end (front).

Operations:
The Queue ADT follows a design similar to the Stack ADT, but the order of insertion and deletion
changes to FIFO. Elements are inserted at one end (called the rear) and removed from the other end
(called the front). It should support the following operations:
 enqueue(): Insert an element at the end of the queue.
 dequeue(): Remove and return the first element of the queue, if the queue is not empty.
 peek(): Return the element of the queue without removing it, if the queue is not empty.
 size(): Return the number of elements in the queue.
 isEmpty(): Return true if the queue is empty; otherwise, return false.
Advantages and Disadvantages of ADT
Abstract data types (ADTs) have several advantages and disadvantages that should be considered when
deciding to use them in software development. Here are some of the main advantages and
disadvantages of using ADTs:
Advantage:
The advantages are listed below:
 Encapsulation: ADTs provide a way to encapsulate data and operations into a single unit,
making it easier to manage and modify the data structure.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  Abstraction: ADTs allow users to work with data structures without having to know the
implementation details, which can simplify programming and reduce errors.
 Data Structure Independence: ADTs can be implemented using different data structures,
which can make it easier to adapt to changing needs and requirements.
 Information Hiding: ADTs can protect the integrity of data by controlling access and preventing
unauthorized modifications.
 Modularity: ADTs can be combined with other ADTs to form more complex data structures,
which can increase flexibility and modularity in programming.

Disadvantages:
The disadvantages are listed below:
 Overhead: Implementing ADTs can add overhead in terms of memory and processing, which
can affect performance.
 Complexity: ADTs can be complex to implement, especially for large and complex data
structures.
 Learning Curve: Using ADTs requires knowledge of their implementation and usage, which can
take time and effort to learn.
 Limited Flexibility: Some ADTs may be limited in their functionality or may not be suitable for
all types of data structures.
 Cost: Implementing ADTs may require additional resources and investment, which can
increase the cost of development.
Linked List Data Structure:
A linked list is a fundamental data structure in computer science. It mainly allows
efficient insertion and deletion operations compared to arrays. Like arrays, it is also used to implement
other data structures like stack, queue and deque. Here’s the comparison of Linked List vs Arrays.

What is Singly Linked List & Implementation?

A singly linked list in data structures is essentially a series of connected elements where each element,
known as a node, contains a piece of data and a reference to the next node in the sequence.
This structure allows for easy and efficient addition or removal of elements without rearranging the
entire data structure, making it a flexible choice for many applications.

Example of Singly Linked List

Consider an application like a dynamic to-do list where users can add and remove tasks. Here, a singly
linked list allows new tasks to be added or old tasks to be deleted without the need to shift other
elements.
This flexibility and efficiency make singly linked lists a popular choice for implementing other
foundational data structures, such as stacks and queues, and for applications like memory

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

management, where the allocation and deallocation of memory happen frequently and in varying
sizes.
Representation of Singly Linked List
Node:
The fundamental part of a singly linked list. Each node consists of two components:
 Data: This part of the node stores the actual data that the list is meant to hold. It can be any
type of data—numbers, characters, or even more complex data structures.
 Next: This is a pointer (or reference) to the next node in the list. It's how the list maintains its
sequence, by linking each node to the subsequent one.
Head:
The first node in a linked list is called the head. It is the entry point to the list and used as a reference
point to traverse it.

Null:
The last node of a linked list, which points to null, indicating the end of the list.

Functionality of Singly Linked List:

The list starts with a head pointer, which points to the first node in the list. The last node in the list
points to null, indicating that there are no more nodes after it. This null marking the end of the list is
crucial—it tells any process or algorithm when to stop iterating through the list.

Singly Linked List Operations in Data Structure

1. Insertion Operations

 Insertion at the Beginning: Also known as "Insertion at Head." This operation involves adding
a new node right at the start of the list. The new node then becomes the head of the list. This
operation is quick because it simply includes pointing the new node to the current head of the
list and then updating the head to this new node, making it a constant time operation, O(1).

Algorithm:

 Create a new node with the given data.

 Set the next pointer of the new node to the current head.
 Update the head to point to the new node.

Insertion at the End: Known as "Insertion at Tail." This requires traversing the entire list to find the last
node and then adding the new node after this. The new node's next pointer is set to null, indicating
the end of the list. Since you need to traverse the entire list, this operation has a time complexity of
O(n), where n is the number of nodes in the list.

Algorithm:

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  Create a new node with the given data.
 If the list is empty, set the head to the new node.
 Otherwise, traverse the list to find the last node.
 Set the next pointer of the last node to the new node.

Insertion after a specific Node: If you need to insert a new node after a specified node, you connect
the new node to the list by adjusting the pointers. The new node points to the next node of the current
node, and the current node's next pointer is updated to point to the new node. This operation
generally requires O(n) in the worst case because you might need to traverse the list to find the
specified node.

Algorithm:

 Create a new node with the given data.

 Find the specified previous_node. If previous_node is NULL, insertion is not possible.
 Set the next pointer of the new node to previous_node->next.
 Set previous_node->next to the new node.

2. Deletion Operations

 Deletion at the Beginning: Removing the first node (head) of the list can be done by simply
updating the head to point to the second node. This is also a constant time operation, O(1).

Algorithm:

 If the list is empty, return.

 Create a temporary pointer temp pointing to the head.
 Update the head to head->next.
 Deallocate the memory of temp.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Deletion from the Middle or Specific Node: To delete a node after a specific node, you update the
next pointer of the preceding node to skip the node to be deleted and point to the following node.
Depending on the position of the node to delete, this can also involve traversing the list, making it
O(n).

Algorithm:

 If the list is empty, return.

 Initialize current to head and previous to NULL.
 Traverse the list to find the node to be deleted (based on value or position).
 If the node to be deleted is found:
 If it's the head node, update head to head->next.
 Otherwise, set previous->next to current->next.
 Deallocate the memory of current.

Deletion at the End: Deleting the last node requires traversing the list to find the second last node and
updating its next pointer to null. This operation takes O(n) time as well.

Algorithm:

• Traverse the list to find the second last node (second_last).

• Delete the last node (the node after second_last).
• Set the next pointer of the second last node to NULL.
• Return the head of the linked list.

Advantages of Singly Linked Lists

 Singly linked lists in data structures can grow and shrink during runtime as needed without a
predefined size.
 They only allocate memory for nodes that are actually in use, reducing memory waste
compared to pre-allocated data structures like arrays.
 Adding or removing nodes doesn't require shifting elements, which can be a costly operation
in arrays. This is particularly beneficial at the beginning of the list.
 Unlike arrays, linked lists don’t reserve memory in advance, which can be more efficient for
certain types of applications where the size of the data structure fluctuates.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Disadvantages of Singly Linked Lists

 Accessing an element in a singly linked list requires traversal from the head to the point of
interest, which can be time-consuming.
 Each node in a singly linked list requires additional memory for the pointer alongside the actual
data.
 Implementing a singly linked list is more complex than using an array, particularly when it
comes to handling pointers, which can introduce bugs like memory leaks.

Doubly Linked List:

A doubly linked list is a more complex data structure than a singly linked list, but it offers several
advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list
in both directions. This is because each node in the list contains a pointer to the previous node and a
pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list,
as well as efficient traversal of the list in both directions.

Representation of Doubly Linked List in Data Structure

In a data structure, a doubly linked list is represented using nodes that have three fields:

1. Data

2. A pointer to the next node (next)

3. A pointer to the previous node (prev)

How to Create a Doubly Linked List

Step by Step Approach

[Link] the head node.

 Allocate a node and set head to it. Its prev and next should be null/None.

[Link] the next node and link it to head.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  [Link] = new Node(value2)

 [Link] = head

[Link] further nodes the same way.

 For the third node:

=> [Link] = new Node(value3)
=> [Link] = [Link]

 Repeat until you have the required nodes.

[Link] the tail's next is null.

The last node you created must have next == null

[Link] / keep track of head (and optionally tail).

Use head to access the list from the front. Keeping a tail pointer simplifies appends.

Doubly Linked List with Implementation:

A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with
the next pointer and data which are there in a singly linked list.

Operations of Doubly Linked List:

[Link] of a node: This can be done in three ways:

At the beginning: The new created node is insert in before the head node and head points to the
new node.

Steps to insert a node at the beginning of doubly linked list:

 Create a new node, say new_node with the given data and set its previous pointer to
null, new_node->prev = NULL.

 Set the next pointer of new_node to the current head, new_node->next = head.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  If the linked list is not empty, update the previous pointer of the current head to
new_node, head->prev = new_node.

 Return new_node as the head of the updated linked list.

 At the End: Add a new node at the end. Traverse to the last node, set the next pointer of the
last node to the new node, and set the prev pointer of the new node to the last node. Update
the tail pointer if maintained.
 After a Given Node: To insert a node after a given node, adjust the next pointer of the new
node to the next pointer of the given node, update the next pointer of the given node to the
new node, and set the prev pointer of the node that follows the new node (if any) to the new
node.

2. Deletion

Removing nodes requires adjustment of pointers from both the preceding and succeeding nodes:

 From the Beginning: Remove the head node by updating the head to the second node and
setting the prev pointer of the new head to null.
 From the End: Remove the tail node by setting the next pointer of the second last node to null
and updating the tail to this second last node.
 A Specific Node: Disconnect the node by adjusting the next pointer of the preceding node to
point to the node after the target node, and adjust the prev pointer of the succeeding node
likewise.

3. Search

Searching involves traversing through the list either from the head or the tail, depending on proximity
and potentially the direction of traversal that may optimize the search:

 Search by Value: Start from the head (or tail) and traverse through the next (or prev) pointers
to find the node containing the desired value.

4. Traversal

Traversal can be performed in both directions, which is a significant advantage of doubly linked lists:

 Forward Traversal: Start from the head and move through each node using the next pointers.
 Backward Traversal: Start from the tail (if available) and move through each node using the
prev pointers.

5. Update

Updating the value of a node can be performed directly once the node is accessed, without any specific
need for traversal if the node reference is already known.

Example of Doubly Linked List

The doubly linked list in data structure is particularly beneficial in applications where the ability to
navigate backwards is as necessary as moving forwards.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 For example, in navigation systems like web browsers, a doubly linked list can manage the user's
history, allowing easy forward (redo) and backward (undo) movements through previously visited
pages.

This example illustrates how doubly linked lists support complex sequence data management in
practical software solutions, enhancing user interface responsiveness and functionality.

Difference Between Singly and Doubly Linked List

Let’s know about the difference between singly linked list and doubly linked list:

Feature Singly Linked List Doubly Linked List

Only forwards. You can Both forwards and backwards. You

Direction of Traversal traverse from the head to can traverse from the head to the
the end of the list. tail and vice versa.

Less memory per node More memory per node (two

Memory Usage
(one pointer per node). pointers per node).

Efficient at the beginning; Efficient at both the beginning and

requires traversal from the end; easier insertions and
Insertions/Deletions
the head for other deletions in the middle without full
positions. traversal.

Simpler and requires less

More complex due to additional
code to manage
Complexity pointers, requiring more
compared to doubly
management and care in code.
linked lists.

Suitable when memory is

Preferred when frequent
a concern and only
Use Case operations require elements to be
forward traversal is
accessed from both ends.
needed.

Typically slower for

Faster for operations involving the
operations that involve
Operations end of the list due to the tail
elements at the end of
pointer.
the list.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 Both head and tail pointers are
Head and Tail
Only head pointer is used. used, providing immediate access
Management
to both ends of the list.

Advantages of Doubly Linked Lists

 Bidirectional Navigation: Allows traversal in both forward and backward directions, facilitating
easier and more flexible data manipulation.
 Easier Insertion and Deletion: Nodes can be added or removed from both ends and the
middle of the list without needing to traverse the entire list, especially if the tail pointer is
maintained.
 Efficient Operations at Both Ends: Adding or removing elements at the beginning and the end
is efficient because both head and tail pointers provide direct access to the endpoints of the
list.
 Dynamic Size: The size of the list can increase or decrease dynamically, which is efficient for
memory usage since it allocates space only as needed.

Disadvantages of Doubly Linked Lists

 Increased Memory Usage: Each node requires extra memory for an additional pointer
(previous pointer), which can be significant in memory-constrained environments.
 Complexity: Managing two pointers (next and prev) per node increases the complexity of the
operations, making the code more prone to errors such as memory leaks and pointer
corruption.
 Slower Individual Operations: The overhead of maintaining an extra pointer can slightly slow
down operations compared to singly linked lists, as more pointer operations are required.
 Overhead in Memory Management: More complex memory management is needed,
especially in languages that do not handle garbage collection automatically, due to the
additional pointers that need to be correctly handled during insertions and deletions

Uses and Applications of Doubly Linked List

Doubly linked lists find a wide range of applications in software development and system design due
to their ability to efficiently add, remove, and access elements from both ends:

 Navigation Systems: Doubly linked lists are ideal for applications where users need to navigate
both forward and backward, such as web browsers or document viewers.
 Music Players: In media playback software, doubly linked lists can manage playlists where
users might want to go to the next or previous track. This allows for seamless navigation
through the playlist.
 Undo Functionality in Applications: Many applications like text editors or graphic design
software use doubly linked lists to implement undo and redo functionalities. Each node in the
list could represent a state of the work, and navigating through the nodes allows users to undo
or redo changes in their projects.
 Gaming: In gaming, doubly linked lists can be used to manage various game states or the
inventory of items that players can cycle through both forward and backward.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  Implementing Other Data Structures: Doubly linked lists are also used to implement more
complex data structures like deque (double-ended queue) which requires adding and
removing items from both ends efficiently.
 Memory Management: In systems programming, doubly linked lists can be used to keep track
of free memory blocks or resources. This allows the system to efficiently allocate and
deallocate resources by adjusting pointers rather than moving memory blocks.

Circular Linked List:

In Circular Singly Linked List, each node has just one pointer called the "next" pointer. The next pointer
of the last node points back to the first node and this results in forming a circle. In this type of Linked
list, we can only move through the list in one direction.

Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list.
The prev pointer points to the previous node and the next points to the next node. Here, in addition
to the last node storing the address of the first node, the first node will also store the address of the
last node.

Representation of a Circular Singly Linked List

Each node has data and a pointer to the next node. When we create multiple nodes for a circular
linked list, we only need to connect the last node back to the first one.

Example of Creating a Circular Linked List

Here’s an example of creating a circular linked list with three nodes (10, 20, 30, 40, 50):

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Why have we taken a pointer that points to the last node instead of the first node?

For the insertion of a node at the beginning, we need to traverse the whole list. Also, for insertion at
the end, the whole list has to be traversed. If instead of the start pointer, we take a pointer to the last
node, then in both cases there won't be any need to traverse the whole list. So insertion at the
beginning or at the end takes constant time, irrespective of the length of the list.

Circular Linked List Operations

 Search Operation

The search operation in a circular linked list involves traversing the list from the head and checking
each node's data against the search value.

The traversal continues until the node’s data matches the search key or the list loops back to the
starting node, indicating that the entire list has been searched.

 Delete Operation

Deleting nodes from a circular linked list can be more complex, especially handling the head and
ensuring the circular nature of the list is maintained.

Deleting at the Beginning

To delete a node at the beginning of the list:

 Point a temporary variable to the head.

 Traverse the list to get to the last node (which points to the head).
 Set the last node's next pointer to the head's next node.
 Update the head to be the next node of the current head.
 Free the temporary variable.

Deleting at the End

To delete a node at the end:

 Check if the list is not empty.

 If the list has only one node, remove it and update the head to None.
 Otherwise, traverse to the second-last node.
 Set the second-last node's next pointer to the head.
 Free the last node.

Deleting in the Middle

To delete a node from the middle:

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  If the node to delete is the head, follow the steps for deleting at the beginning.
 Otherwise, traverse the list to find the node before the target node.
 Set this node’s next pointer to target node's next pointer.
 Free the target node.

Advantages of Circular Linked Lists

 Continuous Traversal: The circular nature allows for continuous traversal of the list, which is useful for
applications that require looping over the same data repeatedly.
 No Null Values: There are no null references in the nodes (for the next/previous pointers), which can
simplify certain list operations by eliminating the need to check for null as a termination condition.
 Efficient Queue Operations: Especially in a doubly circular linked list, operations such as enqueue and
dequeue can be made more efficient because both the front and rear of the queue are accessible.
 Resource Sharing: Useful in scenarios like round-robin scheduling where a circular list can manage the
allocation and cycling through resources or tasks in a repeating pattern.

Disadvantages (Limitations) of Circular Linked Lists

 Complexity in Implementation: The implementation of circular linked lists can be more

complex than simple linked lists due to the need to handle circular connections properly,
which increases the chance of errors such as infinite loops.
 Overhead in Traversing: Care must be taken to stop traversing the list properly; otherwise, it
could lead to infinite loop errors. Keeping track of the starting point is essential to avoid such
issues.
 Additional Logic for Insertion and Deletion: Inserting or deleting nodes requires more logic
to correctly adjust the links, particularly in a doubly circular linked list where both next and
previous links must be accurately maintained.
 Memory Usage: Each node in a doubly circular linked list uses additional memory for the
backward link, which can be a concern in memory-constrained environments.

Uses and Applications of Circular Linked List

Following are some common uses and applications of circular linked lists:

 Computer Networking: Circular linked lists are used in networking, particularly in

implementing algorithms for token ring networks where each computer on a network is given
a chance to transmit data in a pre-defined, circular order.
 Operating Systems: Many operating systems use circular linked lists for various management
tasks, including scheduling algorithms like round-robin scheduling. This method cycles through
processes, allocating CPU time one by one in a fair and cyclic manner.
 Multiplayer Games: In games that involve multiple players, circular linked lists can manage
player turns in a loop. After the last player takes a turn, the system automatically goes back to
the first player.
 Music Players: Media players often use circular linked lists to manage playlists, especially in
'repeat' mode. When the playlist reaches the end, it loops back to the beginning seamlessly.
 User Interface: Circular linked lists are used in applications with a circular carousel of items,
such as image sliders or navigation menus that loop back to the beginning after reaching the
end.
 Resource Allocation: They are also used in managing resources in an environment where the
resources need to be used cyclically, such as allocating CPU or memory resources in a circular
manner to various processes.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Stack Data Structure

A Stack is a linear data structure that follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the
element that is inserted last, comes out first and FILO implies that the element that is inserted first,
comes out last.

It behaves like a stack of plates, where the last plate added is the first one to be removed. Think of it
this way:

Pushing an element onto the stack is like adding a new plate on top.

Popping an element removes the top plate from the stack.

LIFO(Last In First Out)

The LIFO principle means that the last element added to a stack is the first one to be removed.

 New elements are always pushed on top.

 Removal (pop) also happens only from the top.

 This ensures a strict order: last in → first out.

Real-world examples of LIFO:

 Stack of plates – The last plate placed on top is the first one you pick up.

 Shuttlecock box – The last shuttlecock inserted is the first one taken out, since both
operations happen from the same end.

Basic Terminologies of Stack

 Top: The position of the most recently inserted element. Insertions (push) and deletions
(pop) are always performed at the top.

 Size: Refers to the current number of elements present in the stack.

Types of Stack:

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Fixed Size Stack

 A fixed size stack has a predefined capacity.

 Once it becomes full, no more elements can be added (this causes overflow).

 If the stack is empty and we try to remove an element, it causes underflow.

 Typically implemented using a static array.

Example: Declaring a stack of size 10 using an array.

Dynamic Size Stack

 A dynamic size stack can grow and shrink automatically as needed.

 If the stack is full, its capacity expands to allow more elements.

 As elements are removed, memory usage can shrink as well.

 Can be implemented using:

Common Operations on Stack:

In order to make manipulations in a stack, there are certain operations provided to us.

 push() to insert an element into the stack.

 pop() to remove an element from the stack.

 top() Returns the top element of the stack.

 isEmpty() returns true if stack is empty else false.

 size() returns the size of the stack.

Stack using Array:

Stack is a linear data structure which follows LIFO principle. To implement a stack using an
array, initialize an array and treat its end as the stack’s top. Implement push (add to
end), pop (remove from end), and peek (check end) operations, handling cases for
an empty or full stack.

Step-by-step approach:

1. Initialize an array to represent the stack.

2. Use the end of the array to represent the top of the stack.

3. Implement push (add to end), pop (remove from the end), and peek (check end) operations,
ensuring to handle empty and full stack conditions.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 Push Operation in Stack:

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

 Before pushing the element to the stack, we check if the stack is full .

 If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the
element to the stack.

 Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is inserted
at top position .

 The elements can be pushed into the stack till we reach the capacity of the stack.

Algorithm PUSH(STACK, TOP, MAX, ITEM)

Step 1: If TOP = MAX - 1 then

Print "Stack Overflow" // No space

Exit

Step 2: TOP ← TOP + 1

Step 3: STACK[TOP] ← ITEM

Step 4: Print ITEM " Inserted Successfully"

Step 5: End

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Pop Operation in Stack:

Removes an item from the stack. The items are popped in the reversed order in which they are
pushed. If the stack is empty, then it is said to be an Underflow condition.

 Before popping the element from the stack, we check if the stack is empty .

 If the stack is empty (top == -1), then Stack Underflows and we cannot remove any element
from the stack.

 Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1) and
return the stored top value.

Algorithm POP(STACK, TOP)

Step 1: If TOP = -1 then

Print "Stack Underflow" // Stack empty

Exit

Step 2: ITEM ← STACK[TOP] // Store top element

Step 3: TOP ← TOP - 1

Step 4: Print ITEM " Deleted Successfully"

Step 5: Return ITEM

Step 6: End

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Top or Peek Operation in Stack:

Returns the top element of the stack.

 Before returning the top element from the stack, we check if the stack is empty.

 If the stack is empty (top == -1), we simply print “Stack is empty”.

 Otherwise, we return the element stored at index = top .

Algorithm TOP(STACK, TOP)

Step 1: If TOP = -1 then

Print "Stack is Empty"

Exit

Step 2: Return STACK[TOP]

Step 3: End

isEmpty Operation in Stack:

Returns true if the stack is empty, else false.=

 Check for the value of top in stack.

 If (top == -1) , then the stack is empty so return true .

 Otherwise, the stack is not empty so return false.

Algorithm ISEMPTY(TOP)
Step 1: If TOP = -1 then

Return TRUE

Else

Return FALSE

Step 2: End

isFull Operation in Stack :

Returns true if the stack is full, else false.

 Check for the value of top in stack.

 If (top == capacity-1), then the stack is full so return true.

 Otherwise, the stack is not full so return false.

Algorithm ISFULL(TOP, MAX)

Step 1: If TOP = MAX - 1 then

Return TRUE

Else

Return FALSE

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Step 2: End

Implementation using Fixed Sized Array

In this implementation, we use a fixed sized array. We take capacity as argument when we create a
stack. We create an array with size equal to given capacity. If number of elements go beyond
capacity, we throw an overflow error.
#include <stdio.h>

#include <stdlib.h>

#define MAX 5 // Maximum size of stack

int stack[MAX];

int top = -1; // Initially stack is empty

int isFull() {

return top == MAX - 1;

int isEmpty() {

return top == -1;

void push(int item) {

if (isFull()) {

printf("Stack Overflow! Cannot insert %d\n", item);

} else {

top++;

stack[top] = item;

printf("%d pushed into stack\n", item);

int pop() {

if (isEmpty()) {

printf("Stack Underflow! Cannot pop\n");

return -1; // Error value

} else {

int item = stack[top];

top--;

printf("%d popped from stack\n", item);

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 return item;

int peek() {

if (isEmpty()) {

printf("Stack is empty! No top element\n");

return -1; // Error value

} else {

return stack[top];

void display() {

if (isEmpty()) {

printf("Stack is empty\n");

} else {

printf("Stack elements (top to bottom): ");

for (int i = top; i >= 0; i--) {

printf("%d ", stack[i]);

printf("\n");

int main() {

int choice, value;

while (1) {

printf("\n--- Stack Menu ---\n");

printf("1. Push\n2. Pop\n3. Peek\n4. IsEmpty\n5. IsFull\n6. Display\n7. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter value to push: ");

scanf("%d", &value);

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 push(value);

break;

case 2:

pop();

break;

case 3:

value = peek();

if (value != -1)

printf("Top element is %d\n", value);

break;

case 4:

if (isEmpty())

printf("Stack is Empty\n");

else

printf("Stack is not Empty\n");

break;

case 5:

if (isFull())

printf("Stack is Full\n");

else

printf("Stack is not Full\n");

break;

case 6:

display();

break;

case 7:

exit(0);

default:

printf("Invalid choice! Try again.\n");

return 0;

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Stack - Linked List Implementation

To implement a stack using a singly linked list, we follow the LIFO (Last In, First Out) principle by
inserting and removing elements from the head of the list, where each node stores data and a
pointer to the next node.

In the stack Implementation, a stack contains a top pointer. which is the "head" of the stack where
pushing and popping items happens at the head of the list. The first node has a null in the link field
and second node-link has the first node address in the link field and so on and the last node address
is in the "top" pointer.

Stack Operations

 push(): Insert a new element into the stack (i.e just insert a new element at the beginning of
the linked list.)

 pop(): Return the top element of the Stack (i.e simply delete the first element from the
linked list.)

 peek(): Return the top element.

 display(): Print all elements in Stack.

Push Operation

 Initialise a node

 Update the value of that node by data i.e. node->data = data

 Now link this node to the top of the linked list

 And update top pointer to the current node

Algorithm PUSH(TOP, ITEM)

Step 1: Create a new node NEW

Step 2: If memory not available then

Print "Stack Overflow"

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 Exit

Step 3: NEW → DATA ← ITEM

Step 4: NEW → NEXT ← TOP

Step 5: TOP ← NEW

Step 6: Print ITEM " Inserted Successfully"

Step 7: End

Pop Operation

 First Check whether there is any node present in the linked list or not, if not then return

 Otherwise make pointer let say temp to the top node and move forward the top node by 1 step

 Now free this temp node

Algorithm POP(TOP)

Step 1: If TOP = NULL then

Print "Stack Underflow"

Exit

Step 2: TEMP ← TOP

Step 3: ITEM ← TEMP → DATA

Step 4: TOP ← TOP → NEXT

Step 5: Free TEMP

Step 6: Return ITEM

Step 7: End

Peek Operation

 Check if there is any node present or not, if not then return.

 Otherwise return the value of top node of the linked list

Algorithm PEEK(TOP)

Step 1: If TOP = NULL then

Print "Stack is Empty"

Exit

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Step 2: Return TOP → DATA

Step 3: End

Display Operation

 Take a temp node and initialize it with top pointer

 Now start traversing temp till it encounters NULL

 Simultaneously print the value of the temp node

Algorithm DISPLAY(TOP)

Step 1: If TOP = NULL then

Print "Stack is Empty"

Exit

Step 2: Set TEMP ← TOP

Step 3: Repeat while TEMP ≠ NULL

Print TEMP → DATA

TEMP ← TEMP → NEXT

Step 4: End

Implementation using Linked Lists:

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

struct Node {

int data;

struct Node* next;

};

int isEmpty(struct Node* head) {

return head == NULL;

void push(struct Node** head, int new_data) {

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = *head;

*head = new_node;

void pop(struct Node** head) {

if (isEmpty(*head)) return;

struct Node* temp = *head;

*head = (*head)->next;

free(temp);

int peek(struct Node* head) {

if (!isEmpty(head)) return head->data;

return INT_MIN;

int main() {

struct Node* head = NULL;

push(&head, 11);

push(&head, 22);

push(&head, 33);

push(&head, 44);

printf("%d\n", peek(head));

pop(&head);

pop(&head);

printf("%d\n", peek(head));

return 0;

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Time Complexity: O(1), for all push(), pop(), and peek(), as we are not performing any kind of
traversal over the list.
Auxiliary Space: O(n), where n is the size of the stack

Applications of Stacks:

1. Recursive Functions- stack stores function calls until base case.

2. Expression Evaluation- stack used to evaluate postfix expressions.
3. Expression Conversion- stack used to manage operators in infix → postfix/prefix conversion.
4. Reversing Data- stack reverses order naturally.
5. Processing Function Calls- system call stack tracks execution order.

. Recursive Functions:

 Every function call is stored in a stack frame (activation record).

 The function call stack keeps track of local variables, parameters, and return addresses.
 When a recursive function calls itself, a new stack frame is created and pushed on the call
stack.
 When the base case is reached, stack frames are popped one by one.

Example:
Factorial using recursion fact(n) → internally uses system stack.

fact(3)→ fact(2)→ fact(1) → fact(0) (base case)

Each call is pushed into stack until base case, then popped back to calculate result.

Expression Evaluation:

An expression is a combination of operands and operators that represents some computation.

 Operands → constants, variables, or values (e.g., a, 5, x).

 Operators → symbols that specify operations (e.g., +, -, *, /).

Expressions are widely used in arithmetic calculations, logical operations, and programming
languages.

Types of Expressions:

1. Infix Expression:
Operator is between operands.
Natural way humans write expressions.
Needs precedence and associativity rules to evaluate.
Example: A + B or (A + B) * C.

[Link] Expression (Polish Notation)

 Operator is before operands.

 Example: + A B (same as A + B).
 (A + B) * C → * + A B C.
 Evaluated from right to left using a stack.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 [Link] Expression (Reverse Polish Notation – RPN)

 Operator is after operands.

 Example: A B + (same as A + B).

 (A + B) * C → A B + C *.

 Evaluated from left to right using a stack.

Infix to Postfix Conversion Using Stacks:

Rules (Using Stack)

1. Operands (A–Z, 0–9) → Directly add to postfix expression.

2. Left Parenthesis ( → Push onto stack.

3. Right Parenthesis ) → Pop from stack until ( is found. Discard both.

4. *Operators (+, -, , /, ^)

o While stack is not empty and precedence of current operator ≤ precedence of stack
top → pop stack to postfix.

o Push current operator onto stack.

5. At the end → Pop all operators from stack to postfix.

Operator Precedence & Associativity

 ^ (exponent) → Highest precedence, right to left

 *, / → Next, left to right

 +, - → Lowest, left to right

Algorithm: INFIX → POSTFIX:

Algorithm InfixToPostfix(INFIX)

Step 1: Initialize empty stack S

Step 2: Initialize empty POSTFIX string

Step 3: For each symbol ch in INFIX expression:

a) If ch is operand → Add to POSTFIX

b) If ch is '(' → Push to stack

c) If ch is ')' → Pop until '(' is found; discard '('

d) If ch is operator:

While stack not empty AND precedence(ch) ≤ precedence(top of stack):

Pop from stack → POSTFIX

Push ch onto stack

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Step 4: While stack not empty:

Pop from stack → POSTFIX

Step 5: Return POSTFIX

Example:

Infix: (A + B) * C – D

Postfix: (A + B) * C - D → AB+C*D-

Step-by-step:

1. ( → push (

2. A → operand → postfix = A

3. + → push +

4. B → operand → postfix = AB

5. ) → pop until ( → postfix = AB+

6. * → push *

7. C → operand → postfix = AB+C

8. - → lower precedence than *, so pop * → postfix = AB+C* → push -

9. D → operand → postfix = AB+C*D

10. End → pop - → postfix = AB+C*D-

Example2: convert a+b+c+(d+e+f)+g the infix expresion into postfix form

1. a → Operand → Postfix = a
2. + → Push + → Stack = +
3. b → Operand → Postfix = ab
4. + → Operator → Pop + (since precedence is equal, left-associative) → Postfix = ab+
Push new + → Stack = +
5. c → Operand → Postfix = ab+c
6. + → Pop + → Postfix = ab+c+
Push new + → Stack = +
7. ( → Push → Stack = +(
8. → Operand → Postfix = ab+c+d
9. + → Push → Stack = +( +
10. e → Operand → Postfix = ab+c+de
11. + → Pop + → Postfix = ab+c+de+
Push new + → Stack = +( +
12. f → Operand → Postfix = ab+c+de+f
13.) → Pop until ( → Pop + → Postfix = ab+c+de+f+
Remove ( → Stack = +
14. + → Pop + → Postfix = ab+c+de+f++
Push new + → Stack = +

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

15. g → Operand → Postfix = ab+c+de+f++g
16. End → Pop remaining + → Postfix = ab+c+de+f++g+

Evaluation of postfix expression steps:

Rules:

1. Operands (numbers/variables) → push onto stack.

2. *Operators (+, -, , /, ^) →

o Pop required operands from stack.

o Apply operator.

o Push result back onto stack.

3. At the end → single element in stack = result.

Example:

Expression: 23*54*+9-

Step-by-step:

Symbol Action Stack (Top → Bottom)

2 Operand → Push 2

3 Operand → Push 3, 2

* Operator → Pop 3,2 → 2*3=6 → Push 6 6

5 Operand → Push 5, 6

4 Operand → Push 4, 5, 6

* Operator → Pop 4,5 → 5*4=20 → Push 20 20, 6

+ Operator → Pop 20,6 → 6+20=26 → Push 26 26

9 Operand → Push 9, 26

- Operator → Pop 9,26 → 26-9=17 → Push 17 17

Final Result = 17

Evaluate postfix expression 6523+9*+4+*

Rules:

 Operand (number) → push onto stack.

 *Operator (+, -, , /) → pop top 2 operands, apply operation, push result back.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Expression: 6523+9*+4+*

Step 1: Read 6 → push → Stack: [6]

Step 2: Read 5 → push → Stack: [6, 5]
Step 3: Read 2 → push → Stack: [6, 5, 2]
Step 4: Read 3 → push → Stack: [6, 5, 2, 3]
Step 5: Read + → pop(3,2) → 2+3 = 5 → push → Stack: [6, 5, 5]
Step 6: Read 9 → push → Stack: [6, 5, 5, 9]
Step 7: Read * → pop(9,5) → 59 = 45 → push → Stack: [6, 5, 45]
Step 8: Read + → pop(45,5) → 5+45 = 50 → push → Stack: [6, 50]
Step 9: Read 4 → push → Stack: [6, 50, 4]
Step 10: Read + → pop(4,50) → 50+4 = 54 → push → Stack: [6, 54]
Step 11: Read * → pop(54,6) → 654 = 324 → push → Stack: [324]

Final Answer = 324

Evaluate the following expression 623+-382/+*2^3+

1. 6 → push → [6]

2. 2 → push → [6, 2]

3. 3 → push → [6, 2, 3]

4. + → pop(3,2) → 2+3=5 → push → [6, 5]

5. - → pop(5,6) → 6-5=1 → push → [1]

6. 3 → push → [1, 3]

7. 8 → push → [1, 3, 8]

8. 2 → push → [1, 3, 8, 2]

9. / → pop(2,8) → 8/2=4 → push → [1, 3, 4]

10. + → pop(4,3) → 3+4=7 → push → [1, 7]

11. * → pop(7,1) → 1*7=7 → push → [7]

12. 2 → push → [7, 2]

13. ^ → pop(2,7) → 7^2=49 → push → [49]

14. 3 → push → [49, 3]

15. + → pop(3,49) → 49+3=52 → push → [52]

Final Answer = 52

Reversing Data:

Used in problems like string reversal and palindrome checking.

A stack follows LIFO (Last In First Out).

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 If we push all characters of a string into a stack and then pop them out, we get the string in
reverse order.

Example:
Input string = "HELLO"
Push each char: H E L L O
Pop → O L L E H

Step 1: Push each character

Action Stack (Top → Bottom)

Push H H

Push E EH

Push L LEH

Push L LLEH

Push O OLLEH

Step 2: Pop each character

Action Output (Reversed String) Stack

Pop → O "O" LLEH

Pop → L "OL" LEH

Pop → L "OLL" EH

Pop → E "OLLE" H

Pop → H "OLLEH" (empty)

Final Reversed String = OLLEH

Processing Function Calls:

Just like recursion, normal function calls also use stack.

 When a function is called, its parameters, local variables, and return address are pushed on
the call stack.

 When function execution ends, the stack frame is popped and control returns to the caller.

Example:

main() {

func1();

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 func1() {

func2();

Call sequence in stack:

 main() pushed

 func1() pushed

 func2() pushed

 func2() completes → popped

 func1() completes → popped

 Back to main()

Queue using Array :

 The queue uses an array with a fixed capacity, referred to as capacity, and tracks the current
number of elements with a variable size.

 The variable front is initialized to 0 and represents the index of the first element in the array.
In the dequeue operation, the element at this index is removed.

To implement a queue of size n using an array, the operations are as follows:

 Enqueue: Adds new elements to the end of the queue. Checks if the queue has space before
insertion, then increments the size.

 Dequeue: Removes the front element by shifting all remaining elements one position to the
left. Decrements the queue size after removal.

 getFront: Returns the first element of the queue if it's not empty. Returns -1 if the queue is
empty.

 Display: Iterates through the queue from the front to the current size and prints each
element.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS
Algorithm to insert an element in a queue:

 queue[MAX] → array of size MAX

 front → index of front element

 rear → index of last element

Initially: front = rear = -1

Algorithm: Enqueue(Q, item)

Step 1: IF rear = MAX - 1

PRINT "Queue Overflow"

EXIT

Step 2: IF front = -1 AND rear = -1

front ← 0

rear ← 0

ELSE

rear ← rear + 1

Step 3: queue[rear] ← item

Step 4: PRINT "Insertion successful"

Algorithm: Enqueue(Q, item)

Step 1: Create a new node NEW with data = item and next = NULL

Step 2: IF front = NULL AND rear = NULL

front ← NEW

rear ← NEW

ELSE

[Link] ← NEW

rear ← NEW

Step 3: PRINT "Insertion successful"

Algorithm to delete an element in a queue:

queue[MAX] → array of size MAX

front → index of front element

rear → index of last element

Initially: front = rear = -1

Algorithm: Dequeue(Q)

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

Step 1: IF front = -1 OR front > rear

PRINT "Queue Underflow"

EXIT

Step 2: item ← queue[front]

Step 3: IF front = rear

front ← -1

rear ← -1

ELSE

front ← front + 1

Step 4: RETURN item

Algorithm: Dequeue(Q)

Step 1: IF front = NULL

PRINT "Queue Underflow"

EXIT

Step 2: temp ← front

item ← [Link]

front ← [Link]

Step 3: IF front = NULL

rear ← NULL

Step 4: Free(temp)

Step 5: RETURN item

In array queue, we check front > rear to detect empty condition.

In linked list queue, when front becomes NULL, we also set rear = NULL.

Queue using Array - Simple Implementation:

struct Queue {

int *arr;

int front;

int rear;

int capacity;

};

struct Queue* createQueue(int capacity) {

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

queue->capacity = capacity;

queue->front = 0;

queue->rear = -1;

queue->arr = (int*)malloc(capacity * sizeof(int));

return queue;

int isEmpty(struct Queue* queue) {

return queue->front > queue->rear;

void enqueue(struct Queue* queue, int x) {

if (queue->rear < queue->capacity - 1) {

queue->arr[++queue->rear] = x;

void dequeue(struct Queue* queue) {

if (!isEmpty(queue)) {

queue->front++;

int getFront(struct Queue* queue) {

return isEmpty(queue) ? -1 : queue->arr[queue->front];

void display(struct Queue* queue) {

for (int i = queue->front; i <= queue->rear; i++) {

printf("%d ", queue->arr[i]);

printf("\n");

int main() {

struct Queue* q = createQueue(100);

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 enqueue(q, 1);

enqueue(q, 2);

enqueue(q, 3);

printf("%d\n", getFront(q));

dequeue(q);

enqueue(q, 4);

display(q);

return 0;

Output

234

Time Complexity: O(1) for Enqueue (element insertion in the queue) as we simply increment pointer
and put value in array, O(n) for Dequeue (element removing from the queue).
Auxiliary Space: O(n), as here we are using an n size array for implementing Queue

Advantages:

 Simplicity and Ease of Implementation:

Array-based queues are relatively straightforward to understand and implement, especially for basic
linear queues.

 Efficient Memory Access:

Arrays store elements in contiguous memory locations, leading to better cache performance and
potentially faster access times compared to linked lists, particularly when the queue is small.

 Constant Time Operations (for Circular Queues):

In a circular array implementation, both enqueue (insertion at the rear) and dequeue (removal from
the front) operations can be achieved in O(1) constant time, assuming no resizing is required.

Disadvantages:

 Fixed Size Limitation:

The most significant drawback is the fixed size of arrays. If the queue exceeds its declared capacity, it
can lead to overflow errors. Resizing an array is a costly operation as it involves creating a new, larger
array and copying all existing elements.

 Memory Inefficiency (for Linear Queues):

In a linear array-based queue, when elements are dequeued from the front, the space they occupied
becomes empty but cannot be reused until the entire queue is emptied and potentially reset. This

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

can lead to inefficient memory utilization. Circular queues mitigate this issue by allowing reuse of
vacated front spaces.

 Shifting Elements (for Non-Circular Queues):

If a linear queue is implemented without a circular approach, dequeuing an element from the front
would require shifting all subsequent elements to fill the vacant spot, resulting in an O(n) time
complexity for dequeue operations, which is inefficient for large queues.

Queue - Linked List Implementation

we maintain two pointers, front and rear. The front points to the first item of the queue and rear
points to the last item.

 enQueue(): This operation adds a new node after the rear and moves the rear to the next
node.

 deQueue(): This operation removes the front node and moves the front to the next node.

Follow the below steps to solve the problem:

 Create a class Node with data members integer data and Node* next
o A parameterized constructor that takes an integer x value as a parameter and sets
data equal to x and next as NULL

 Create a class Queue with data members Node front and rear

 Enqueue Operation with parameter x:

o Initialize Node* temp with data = x

o If the rear is set to NULL then set the front and rear to temp and return(Base Case)

o Else set rear next to temp and then move rear to temp

 Dequeue Operation:

o If the front is set to NULL return(Base Case)

o Initialize Node temp with front and set front to its next

o If the front is equal to NULL then set the rear to NULL

o Delete temp from the memory

Types of Queues:

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

1. Circular Queue: Circular Queue is a linear data structure in which the operations are performed
based on FIFO (First In First Out) principle and the last position is connected back to the first position
to make a circle. It is also called ‘Ring Buffer’. This queue is primarily used in the following cases:

o Memory Management: The unused memory locations in the case of ordinary queues
can be utilized in circular queues.
o Traffic system: In a computer-controlled traffic system, circular queues are used to
switch on the traffic lights one by one repeatedly as per the time set.
o CPU Scheduling: Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur.

o The time complexity for the circular Queue is O(1).

2. Input restricted Queue: In this type of Queue, the input can be taken from one side only(rear) and
deletion of elements can be done from both sides(front and rear). This kind of Queue does not follow
FIFO(first in first out). This queue is used in cases where the consumption of the data needs to be in
FIFO order but if there is a need to remove the recently inserted data for some reason and one such
case can be irrelevant data, performance issue, etc.

Input Restricted Queue

Advantages of Input restricted Queue:

 Prevents overflow and overloading of the queue by limiting the number of items added

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

  Helps maintain stability and predictable performance of the system

Disadvantages of Input restricted Queue:

 May lead to resource wastage if the restriction is set too low and items are frequently
discarded

 May lead to waiting or blocking if the restriction is set too high and the queue is full,
preventing new items from being added.

3. Output restricted Queue: In this type of Queue, the input can be taken from both sides(rear and
front) and the deletion of the element can be done from only one side(front). This queue is used in
the case where the inputs have some priority order to be executed and the input can be placed even
in the first place so that it is executed first.

4. Double ended Queue: Double Ended Queue is also a Queue data structure in which the insertion
and deletion operations are performed at both the ends (front and rear). That means, we can insert
at both front and rear positions and can delete from both front and rear positions. Since Deque
supports both stack and queue operations, it can be used as both. The Deque data structure
supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain
applications. Also, the problems where elements need to be removed and or added both ends can be
efficiently solved using Deque.

Double Ended Queue

5. Priority Queue: A priority queue is a special type of queue in which each element is associated
with a priority and is served according to its priority. There are two types of Priority Queues. They
are:

1. Ascending Priority Queue: Element can be inserted arbitrarily but only smallest element can
be removed. For example, suppose there is an array having elements 4, 2, 8 in the same order.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 So, while inserting the elements, the insertion will be in the same sequence but while deleting,
the order will be 2, 4, 8.

2. Descending priority Queue: Element can be inserted arbitrarily but only the largest element
can be removed first from the given Queue. For example, suppose there is an array having
elements 4, 2, 8 in the same order. So, while inserting the elements, the insertion will be in
the same sequence but while deleting, the order will be 8, 4, 2.

The time complexity of the Priority Queue is O(logn).

Applications of a Queue:

The queue is used when things don’t have to be processed immediately, but have to be processed in
First In First Out order like Breadth First Search. This property of Queue makes it also useful in the
following kind of scenarios.

1. When a resource is shared among multiple consumers. Examples include CPU

scheduling, Disk Scheduling.
2. When data is transferred asynchronously (data not necessarily received at the same rate as
sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
3. Linear Queue: A linear queue is a type of queue where data elements are added to the end
of the queue and removed from the front of the queue. Linear queues are used in
applications where data elements need to be processed in the order in which they are
received. Examples include printer queues and message queues.

4. Circular Queue: A circular queue is similar to a linear queue, but the end of the queue is
connected to the front of the queue. This allows for efficient use of space in memory and can
improve performance. Circular queues are used in applications where the data elements
need to be processed in a circular fashion. Examples include CPU scheduling and memory
management.

5. Priority Queue: A priority queue is a type of queue where each element is assigned a priority
level. Elements with higher priority levels are processed before elements with lower priority
levels. Priority queues are used in applications where certain tasks or data elements need to
be processed with higher priority. Examples include operating system task scheduling and
network packet scheduling.

6. Double-ended Queue: A double-ended queue, also known as a deque, is a type of queue

where elements can be added or removed from either end of the queue. This allows for
more flexibility in data processing and can be used in applications where elements need to
be processed in multiple directions. Examples include job scheduling and searching
algorithms.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS

 7. Concurrent Queue: A concurrent queue is a type of queue that is designed to handle
multiple threads accessing the queue simultaneously. Concurrent queues are used in multi-
threaded applications where data needs to be shared between threads in a thread-safe
manner. Examples include database transactions and web server requests.

Mrs. G. KRISHNA KEERTHANA Assistant Professor Dept of CSM - SITS