 Define the data structure? Different types of data structure.

A data structure is a way of organizing and storing data to efficiently access and manipulate it. It defines the
relationship between the data elements and facilitates operations like insertion, deletion, searching, and sorting.

Various types of data structures include:

1. Arrays: A collection of elements stored in contiguous memory locations, accessed by index.

2. Linked Lists: Elements stored in nodes with pointers to the next node, enabling dynamic memory allocation.

3. Stacks: Follows Last-In-First-Out (LIFO) principle, with operations restricted to the top.

4. Queues: Follows First-In-First-Out (FIFO) principle, with operations restricted to both ends.

5. Trees: Hierarchical structure with nodes connected by edges, including binary trees, binary search trees, etc.

6. Graphs: Non-linear data structures consisting of nodes and edges that connect them, representing relationships.

7. Hash Tables: Utilizes a hash function to map keys to values, enabling fast retrieval.

- Each data structure has unique characteristics suited for specific applications and computational tasks.

 Compare and contrast between Linear & Non Linear data structure

S.NO Linear Data Structure Non-linear Data Structure

In a linear data structure, data elements are arranged in a In a non-linear data structure, data
linear order where each and every element is attached to elements are attached in hierarchically
1. its previous and next adjacent. manner.

Whereas in non-linear data structure,

2. In linear data structure, single level is involved. multiple levels are involved.

Its implementation is easy in comparison to non-linear While its implementation is complex in

3. data structure. comparison to linear data structure.

While in non-linear data structure, data

In linear data structure, data elements can be traversed in a elements can’t be traversed in a single
4. single run only. run only.

While in a non-linear data structure,

In a linear data structure, memory is not utilized in an memory is utilized in an efficient way.
5. efficient way.

6. Its examples are: array, stack, queue, linked list, etc. While its examples are: trees and graphs.

Applications of non-linear data structures

Applications of linear data structures are mainly in are in Artificial Intelligence and image
7. application software development. processing.
 Explain the stack? Types of Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning that the last
element added to the stack is the first one to be removed. It operates on two main operations: push
(adding an element to the top of the stack) and pop (removing the top element from the stack).
Additionally, stacks typically support operations like peek (viewing the top element without removing it)
and isEmpty (checking if the stack is empty).

Types of stacks include:

1. **Array-based stack**: Implemented using arrays, where elements are stored sequentially, and a
pointer keeps track of the top element. This type has a fixed size and may require resizing if the capacity is
exceeded.

2. **Linked list-based stack**: Implemented using linked lists, where each node contains data and a
pointer to the next node. It offers dynamic memory allocation, allowing for a flexible size.

3. **Dynamic stack**: This type of stack grows or shrinks dynamically as elements are added or removed,
respectively, without requiring manual resizing.

4. **Recursive Stack:** Utilized implicitly by programming languages during recursive function calls. Each
function call creates a new stack frame, storing local variables and return addresses until the function
completes execution.

 Discuss the different operation of stack and Justify?

The stack data structure supports several fundamental operations that facilitate efficient data
manipulation:

1. **Push:** This operation adds an element to the top of the stack. It is crucial for building the stack by
inserting new elements, and it ensures that the most recently added item becomes the top element. Push
operation allows for constant-time insertion, making it efficient and suitable for scenarios where
elements need to be added frequently.

2. **Pop:** The pop operation removes the top element from the stack. It's essential for accessing and
removing the most recent item added to the stack, adhering to the Last-In-First-Out (LIFO) principle. Pop
operation also works in constant time, providing quick retrieval of elements.

3. **Peek (or Top):** Peek operation allows accessing the top element of the stack without removing it.
It's useful for inspecting the element at the top of the stack without altering the stack's contents. This
operation is efficient, requiring constant time, enabling quick examination of the stack's current state.

These operations collectively offer versatility and efficiency in managing data within the stack, making it
suitable for various applications, including expression evaluation, function call management, and
backtracking algorithms.
 Define the queue? different types of queue.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first
element added to the queue is the first one to be removed. It operates with two primary operations:
enqueue (adds an element to the rear or tail of the queue) and dequeue (removes an element from the
front or head of the queue). Additionally, queues may support other operations such as peek (or front) to
retrieve the element at the front without removing it and isEmpty to check if the queue is empty.

Types of queues include:

1. **Array-based Queue:** Implemented using an array where elements are enqueued at the rear and
dequeued from the front. It may require resizing if the array becomes full, potentially leading to
inefficient memory management.

2. **Linked List-based Queue:** Implemented using a linked list where each node points to its successor.
Operations like enqueue and dequeue manipulate the pointers accordingly, allowing dynamic resizing and
efficient memory usage.

3. **Priority Queue:** A specialized queue where elements are dequeued based on their priority. Higher-
priority elements are dequeued before lower-priority ones, allowing for applications requiring
prioritization, such as task scheduling.

4. **Double-ended Queue (Deque):** Supports insertion and deletion at both ends, functioning as both a
queue and a stack. It provides more flexibility in data manipulation.
 Differentiate Between Stack and Queue Data Structures.

Stacks Queues

A stack is a data structure that stores a A queue is a data structure that stores a collection of
collection of elements, with operations to push elements, with operations to enqueue (add) elements at the
(add) and pop (remove) elements from the top back of the queue, and dequeue (remove) elements from
of the stack. the front of the queue.

Stacks are based on the LIFO principle, i.e., the Queues are based on the FIFO principle, i.e., the element
element inserted at the last, is the first element inserted at the first, is the first element to come out of the
to come out of the list. list.

Stacks are often used for tasks that require Queues are often used for tasks that involve processing
backtracking, such as parsing expressions or elements in a specific order, such as handling requests or
implementing undo functionality. scheduling tasks.

Insertion and deletion in queues takes place from the

opposite ends of the list. The insertion takes place at the
Insertion and deletion in stacks takes place only rear of the list and the deletion takes place from the front of
from one end of the list called the top. the list.

Insert operation is called push operation. Insert operation is called enqueue operation.

Stacks are implemented using an array or linked Queues are implemented using an array or linked list data
list data structure. structure.

Delete operation is called pop operation. Delete operation is called dequeue operation.

Stack is used in solving problems works Queue is used in solving problems having sequential
on recursion. processing.

Queue is of three types – 1. Circular Queue 2. Priority

Stack does not have any types. queue 3. double-ended queue.

Can be considered as a vertical collection

visual. Can be considered as a horizontal collection visual.

Examples of stack-based languages include Examples of queue-based algorithms include Breadth-First

PostScript and Forth. Search (BFS) and printing a binary tree level-by-level.
 Define Array and Its Types?

An array can be defined as a group of elements containing a collection of variables stored

under a similar name. An array can be categorized in the following ways-

1. Indexed Array

An index array can be determined as an array that consists of the numeric key. I t is
fundamentally an array in which each key is connected to its own particular value.

2. Associative Array

An associative array can be termed as an array in which the key can be presented either in
numeric or string format. This particular array is kept in the form of key-value pair.

3. One-Dimensional Array

A one-dimensional array is a list of variables consisting of datatypes that come under the same
name. In this array, we access all the components just by using their index numbers. A one -
dimensional array contains a fixed size.

4. Multidimensional Array :- A multi-dimensional array is an array of arrays that holds

equivalent data in a table-like form. It is also known as Matrix. Here in the multi-dimensional
array, the data is put down in row-major order.

 Explain the different types of link list?

Linked lists are linear data structures where elements, called nodes, are connected via pointers. There are
several types of linked lists, each with its own characteristics:

1. **Singly Linked List:** In a singly linked list, each node contains data and a single pointer that points to
the next node in the sequence. The last node's pointer points to null, indicating the end of the list. Singly
linked lists allow traversal only in one direction, from the head (first node) to the tail (last node).

2. **Doubly Linked List:** Doubly linked lists contain nodes with two pointers: one pointing to the next
node and another pointing to the previous node. This bidirectional linkage allows traversal in both
forward and backward directions, providing more flexibility compared to singly linked lists.

3. **Circular Linked List:** In a circular linked list, the last node's pointer points back to the first node,
forming a circular structure. This type of linked list can be either singly or doubly linked. Circular linked
lists are useful in applications where elements need to be accessed in a loop or rotation.

4. **Sorted Linked List:** Sorted linked lists maintain elements in sorted order, typically in ascending or
descending order based on a specified criterion. Insertion into a sorted linked list requires maintaining the
sorted order, making searches efficient but potentially slowing down insertions.
 Explain the circular link list and double link list?

 What are the different advantages & disadvantages of stack?

**Advantages:**
1. **Simple and Efficient Operations:** Stacks offer efficient operations for adding (pushing) and
removing (popping) elements, typically with constant time complexity. This makes them suitable for
applications requiring quick insertion and deletion of elements.
2. **Memory Management:** Stacks utilize a small, fixed amount of memory, making them memory-
efficient compared to other data structures like dynamic arrays or linked lists. They are particularly
useful in memory-constrained environments.
3. **Function Call Management:** Stacks are widely used in programming languages for managing
function calls and maintaining information about active function calls. Each function call creates a stack
frame, facilitating the process of function invocation and return.
4. **Expression Evaluation:** Stacks play a crucial role in evaluating arithmetic expressions, postfix, and
infix expressions by storing operands and operators and facilitating their evaluation in a systematic
manner.
**Disadvantages:**
1. **Fixed Size Limitation:** Most stack implementations have a fixed size, which can lead to stack
overflow errors if the maximum capacity is exceeded. This limitation restricts the amount of data that
can be stored in a stack at any given time.
2. **Limited Access:** Stacks support only restricted access to elements. Unlike arrays or linked lists,
where elements can be accessed at arbitrary positions, stacks allow access to only the topmost
element. This limitation can be problematic for certain applications that require random access to
elements.
3. **Lack of Flexibility:** Stacks have a limited set of operations compared to other data structures.
While they excel in certain scenarios like function call management and expression evaluation, they may
not be the optimal choice for all data storage and manipulation tasks.
 Explain the operation of queue?

The fundamental operations that can be performed on queue are listed as follows -

 Enqueue: The Enqueue operation is used to insert the element at the rear end of the queue. It returns void.

 Dequeue: It performs the deletion from the front-end of the queue. It also returns the element which has
been removed from the front-end. It returns an integer value.
 Peek: This is the third operation that returns the element, which is pointed by the front pointer in the queue
but does not delete it.
 Queue overflow (isfull): It shows the overflow condition when the queue is completely full.
 Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e., no elements
are in the Queue.

 Explain the different application of stack.

Stacks have numerous applications across various domains due to their Last-In-First-Out (LIFO) nature and
efficient push and pop operations. Here are some common applications:
1. **Function Call Stack:** Programming languages use a stack to manage function calls. When a function
is called, its parameters, return address, and local variables are pushed onto the stack. When the function
returns, its stack frame is popped, and control returns to the calling function.
2. **Expression Evaluation:** Stacks are used in evaluating expressions, including infix, postfix, and prefix
expressions. They facilitate the conversion of infix expressions to postfix or prefix notation, making
evaluation more efficient.
3. **Undo Mechanisms:** Many applications, such as text editors, maintain a stack of actions performed
by the user. This allows for easy undoing of actions by popping them from the stack in reverse order.
4. **Browser History:** Web browsers use a stack to maintain the history of visited web pages. Each time a
user visits a new page, it is pushed onto the stack. Navigating back through pages pops them from the
stack.
5. **Backtracking Algorithms:** Backtracking algorithms, like depth-first search (DFS) and recursive
backtracking, use stacks to keep track of the current path or state. When exploring a solution space,
choices are pushed onto the stack, and when backtracking, choices are popped.
6. **Parentheses Matching:** Stacks are used to check the validity of expressions containing parentheses,
braces, and brackets. Each opening symbol is pushed onto the stack, and when a closing symbol is
encountered, it is matched with the top of the stack.
7. **Memory Management:** Stacks are used in memory allocation and deallocation, especially in systems
with limited memory. The stack segment of memory is used for storing local variables and function call
information.
8. **Syntax Parsing:** Compilers and interpreters use stacks in syntax analysis phases, such as parsing and
interpreting source code. Stacks are used to track the current state of the parsing process.
 Define Single link list? Discuss the different operation on single link list and Justify?

A singly linked list is a linear data structure consisting of nodes where each node contains a data element
and a reference (or pointer) to the next node in the sequence. The last node typically points to null,
indicating the end of the list.

**Operations on a Single Linked List:**

1. **Insertion (at the beginning):** This operation involves adding a new node at the beginning of the list.
It requires updating the next pointer of the new node to point to the current head of the list and then
updating the head to point to the new node. This operation has a time complexity of O(1) since it only
involves a constant number of pointer assignments.

2. **Insertion (at the end):** Adding a new node at the end of the list involves traversing the entire list to
find the last node, then updating its next pointer to point to the new node. This operation has a time
complexity of O(n), where n is the number of nodes in the list.

3. **Insertion (at a specific position):** Inserting a new node at a specific position requires traversing the
list to find the node before the desired position, then updating its next pointer to point to the new node
and updating the new node's next pointer to point to the node after the desired position. This operation
has a time complexity of O(n).

4. **Deletion (at the beginning):** Removing the first node in the list involves updating the head pointer
to point to the second node in the list. This operation has a time complexity of O(1) since it only involves a
constant number of pointer assignments.

5. **Deletion (at the end):** Deleting the last node in the list requires traversing the list to find the
second-to-last node, then updating its next pointer to point to null. This operation has a time complexity
of O(n) since it requires traversing the list.

6. **Deletion (at a specific position):** Removing a node at a specific position involves traversing the list
to find the node before the desired position, then updating its next pointer to skip over the node to be
deleted. This operation has a time complexity of O(n).

**Justification:**

 Single linked lists are efficient for insertion and deletion at the beginning, as they require only
constant time to update the head pointer.
 While insertion and deletion at the end require traversing the list, they are still valuable operations
and widely used.
 Traversal and search operations are necessary for accessing and manipulating data within the list
and are achievable with linear time complexity.
 Overall, the operations on a singly linked list provide a balance between efficiency and
functionality, making it a versatile data structure for various applications.
 What are the different advantages & disadvantages of single link list?

Single linked lists offer several advantages and disadvantages:

**Advantages:**

1. **Dynamic Size:** Single linked lists can dynamically grow and shrink in size as elements are
inserted or removed, unlike arrays, which have a fixed size. This flexibility allows for efficient memory
utilization and scalability.

2. **Insertion and Deletion:** Insertion and deletion operations at the beginning of a single linked list
are fast and efficient, requiring only constant time complexity, O(1), as they involve updating only a
few pointers.

3. **Memory Efficiency:** Single linked lists allocate memory dynamically for each node, making them
memory-efficient. They utilize memory more effectively than arrays, especially when the size of the
list is unknown or varies over time.

4. **Ease of Implementation:** Implementing a single linked list is relatively straightforward,

requiring only a basic understanding of pointers and memory allocation. It is a fundamental data
structure commonly taught in computer science courses.

**Disadvantages:**

1. **Limited Access:** Single linked lists support only sequential access to elements. Random access
to elements (accessing elements by index) is not efficient and requires traversing the list from the
beginning, resulting in a time complexity of O(n).

2. **Memory Overhead:** Each node in a single linked list requires additional memory overhead for
storing the next pointer, increasing the overall memory usage compared to arrays, especially for large
lists with many nodes.

3. **No Backward Traversal:** Single linked lists do not support backward traversal (traversing the list
in reverse order) without additional pointers or modifications. This limitation can be problematic for
certain applications that require backward traversal.

4. **No Constant-Time Access to Tail:** Unlike doubly linked lists, which maintain a reference to the
last node (tail), single linked lists do not provide constant-time access to the tail. To access the last
element, the entire list must be traversed, resulting in a time complexity of O(n).
 Explain the different types of queue?

Queues are linear data structures that adhere to the First-In-First-Out (FIFO) principle, where the
first element added to the queue is the first one to be removed. Several types of queues exist, each
with unique characteristics:

1. **Linear Queue:** Also known as a simple queue, it maintains a linear sequence of elements.
Elements are enqueued at the rear and dequeued from the front. Linear queues can be
implemented using arrays or linked lists.

2. **Circular Queue:** Circular queues address the limitation of linear queues by reusing empty
spaces at the beginning after dequeuing elements, effectively forming a circular structure. This
prevents wastage of space and allows continuous insertion and deletion without shifting elements.

3. **Priority Queue:** Priority queues prioritize elements based on their assigned priority.
Elements with higher priority are dequeued before elements with lower priority, regardless of their
arrival order. Priority queues are commonly implemented using binary heaps or self-balancing
binary search trees.

4. **Double-ended Queue (Deque):** A deque supports insertion and deletion operations at both
ends, front and rear. This versatility allows for efficient implementations of algorithms requiring
simultaneous access to both ends, such as implementing a stack or a queue.

 Explain the circular queue ? with suitable example.

A circular queue, also known as a circular buffer or a ring buffer, is a type of queue data structure
that operates on a fixed-size array and uses modulo arithmetic to wrap around when reaching the
end of the array, effectively forming a circular structure. This allows for efficient use of memory
and enables continuous insertion and deletion operations without shifting elements.

Here's how a circular queue works:

1. Initialize a fixed-size array to hold the elements of the queue and maintain two pointers, `front`
and `rear`, to track the front and rear positions of the queue.

2. When enqueuing (adding) an element, increment the `rear` pointer and insert the element at
the corresponding index in the array. If the `rear` pointer reaches the end of the array, wrap it
around to the beginning using modulo arithmetic (`rear = (rear + 1) % capacity`).

3. When dequeuing (removing) an element, increment the `front` pointer to mark the element as
dequeued. If the `front` pointer reaches the end of the array, wrap it around to the beginning using
modulo arithmetic (`front = (front + 1) % capacity`).
4. To check if the circular queue is empty, compare the `front` and `rear` pointers. If they are equal,
the queue is empty. To check if the circular queue is full, check if `(rear + 1) % capacity == front`.

Example:

Let's consider implementing a circular queue to simulate a printer spooler, where multiple print
jobs are queued for printing. Suppose the printer spooler has a capacity of 5 print jobs.

Initially, the circular queue is empty: Enqueuing two print jobs:

Front = 0 Front = 0

Rear = 0 Rear = 2

Queue: [] Queue: [Job1, Job2, _, _, _]

Dequeuing one print job: Enqueuing three more print jobs:

Front = 1 Front = 1

Rear = 2 Rear = 0

Queue: [_, Job2, _, _, _] Queue: [Job5, Job2, Job3, Job4, Job1]