1.

Abstract Data Type (ADT) in DSA:

ADT (Abstract Data Type) is a way to describe data and the operations that can be performed on it — without worrying about how it is implemented in code or memory.

📌 Easy Definition:
ADT is a logical description of how data is organized and what operations are allowed on it.

You only care about:

 What data it stores

 What operations can be performed

You don't care about:

 How it is stored in memory

 How those operations are implemented

📦 Example 1: Stack (ADT)

Imagine a stack of plates

You can:

 Push a new plate on top

 Pop the top plate off

So, a Stack ADT allows:

 push(item)
 pop()
 peek() → See the top item
 isEmpty() → Check if the stack is empty

But you don’t care whether the stack is built using an array or a linked list. That’s implementation detail.
 📦 Example 2: Queue (ADT)

Like a queue at a movie theater

You can:

A. Enqueue (add person at the end)

B. Dequeue (remove person from front)

Queue ADT allows:

 enqueue(item)
 dequeue()
 peek()
 isEmpty()

Again, the internal structure (array, linked list, etc.) is not your concern at the ADT level.

💡 Summary Table

Concept ADT Explanation

What is ADT? Blueprint of data structure + operations

Focus What operations you can do

Ignore How it's done inside

Examples Stack, Queue, List, Set, Map, Tree

2. Stacks

A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.

Formally, a stack is an abstract data type (ADT) that supports the following two update methods:

push(e): Adds element e to the top of the stack.

pop(): Removes and returns the top element from the stack (or null if the stack is empty).

Additionally, a stack supports the following accessor methods for convenience:

top(): Returns the top element of the stack, without removing it (or null if the stack is empty).

size(): Returns the number of elements in the stack.

isEmpty(): Returns a boolean indicating whether the stack is empty.

Isfull():

A. Basic Operations on Stack

1. push()

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.

2. pop()
 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.

Algorithm for Pop Operation:

 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.

3. topElement() / peek()

Returns the top element of the stack.

Algorithm for Top Operation:

 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 .

4. isEmpty()

Returns true if the stack is empty, else false.

Algorithm for isEmpty Operation:

o Check for the value of top in stack.

o If (top == -1), then the stack is empty so return true .
o Otherwise, the stack is not empty so return false .
 5. isFull()

Returns true if the stack is full, else false.

Algorithm for isFull Operation:

 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.

6. size()

The size() is used to calculate the size of the stack, which returns the size of the stack. The size is the capacity of the stack or the number of elements a stack can have at a single
time.

Here's an algorithm of the size() operation to implement it manually:

 Create a variable ‘n’ with the value 0

 If the ‘top’ is -1, then return ‘n’ with the value 0, as there are no elements in the stack
 If the ‘top’ is greater than -1, assign ‘n’ with top + 1 and return n

Method Running Time

size O(1)

isEmpty O(1)

top O(1)

push O(1)

pop O(1)

B. Application, Advantage and Disadvantage Stack

Applications of Stacks:

 Function calls: Stacks are used to keep track of the return addresses of function calls, allowing the program to return to the correct location after a function has finished
executing.

 Recursion: Stacks are used to store the local variables and return addresses of recursive function calls, allowing the program to keep track of the current state of the recursion.

 Expression evaluation: Stacks are used to evaluate expressions in postfix notation (Reverse Polish Notation).

 Syntax parsing: Stacks are used to check the validity of syntax in programming languages and other formal languages.

 Memory management: Stacks are used to allocate and manage memory in some operating systems and programming languages.

 Used to solve popular problems like Next Greater, Previous Greater, Next Smaller, Previous Smaller, Largest Area in a Histogram and Stock Span Problems.
Advantages of Stacks:

 Simplicity: Stacks are a simple and easy-to-understand data structure, making them suitable for a wide range of applications.

 Efficiency: Push and pop operations on a stack can be performed in constant time (O(1)), providing efficient access to data.

 Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last element added to the stack is the first one removed. This behavior is useful in many scenarios,
such as function calls and expression evaluation.

 Limited memory usage: Stacks only need to store the elements that have been pushed onto them, making them memory-efficient compared to other data structures.

Disadvantages of Stacks:

 Limited access: Elements in a stack can only be accessed from the top, making it difficult to retrieve or modify elements in the middle of the stack.

 Potential for overflow: If more elements are pushed onto a stack than it can hold, an overflow error will occur, resulting in a loss of data.

 Not suitable for random access: Stacks do not allow for random access to elements, making them unsuitable for applications where elements need to be accessed in a specific
order.

 Limited capacity: Stacks have a fixed capacity, which can be a limitation if the number of elements that need to be stored is unknown or highly variable.

C. Implementation of Stack

1. Stack Implementation Using Arrays

In this approach, we declare an array of a fixed size and use two pointers: one to point to the top of the stack and the other to point to the bottom. Push and pop operations can
be performed by adding or removing elements at the top of the stack. The isEmpty and isFull operations can be implemented by checking the size of the stack against the fixed
array size.

Pros:

 Arrays are a simple and straightforward data structure to implement

 Arrays allow direct access to elements, which can be useful for certain operations
 Array-based stacks have constant time complexity for accessing elements, pushing, and popping as long as the size of the array is known

Cons:

 Array-based stacks have a fixed size, which can lead to overflow if the stack exceeds its capacity
 Resizing an array-based stack can be expensive, requiring copying all elements to a new array
 Removing an element from the middle of an array-based stack can be inefficient, requiring shifting all subsequent elements to fill the gap

Complexity:

 Time Complexity: O(N)

 Reason: The time complexity of the push, pop, and peek operations in this implementation of a stack is O(1) or constant time, which means the time taken
to perform these operations does not depend on the size of the stack.
 The overall time complexity of the code is O(N), where N is the size of the array. This is because the array is created using the new keyword, which allocates
memory dynamically.
 Space complexity: O(N)
 Reason: The space complexity of this stack implementation is O(N), where n is the size of the stack. This is because the stack is implemented as an array of
size N.
2. Stack Implementation Using Linked Lists
A stack can also be implemented using a linked list data structure. In this approach, each element in the stack is represented by a node in the linked list. The head of the
linked list points to the top of the stack. Push and pop operations can be performed by adding or removing nodes at the head of the linked list, respectively.
The isEmpty and isFull operations are unnecessary for this approach since a linked list can grow dynamically.

Note:

The sentence means that when using a linked list data structure, there is no need to check whether it is empty or full because it can dynamically adjust its size to
accommodate new elements. This is in contrast to other data structures, such as arrays, where the size is fixed and must be pre-allocated, making it necessary to keep
track of whether the structure is empty or full.

Pros:

 Linked lists can grow or shrink dynamically, allowing for efficient memory use
 Adding or removing elements from a linked list-based stack is generally faster and easier than resizing an array-based stack
 Removing an element from the middle of a linked list-based stack is straightforward, as it only requires updating a few pointers

Cons:

 Linked lists require additional memory overhead to store the pointers to the next element
 Linked list-based stacks do not allow direct access to elements and require traversal of the list to access specific elements
 Linked list-based stacks can be slower than array-based stacks for accessing elements, pushing, and popping due to the additional overhead of pointer
manipulation

Complexity:

 Time Complexity: O(1)

 Reason: The time complexity of the push, pop, peek, and isEmpty operations in this stack implementation using a linked list is O(1) in the average and
worst case. This is because these operations involve only constant-time operations on the head of the linked list.
 Space Complexity: O(n)
 Reason: Space complexity is O(n), where n is the number of elements in the stack. This is because each element in the stack requires a new Node object to
be created and stored in memory.

Feature Stack using Array Stack using Linked List

Storage Uses a fixed-size array Uses dynamically allocated nodes

Size (Capacity) Fixed (must define size beforehand) Dynamic (grows/shrinks as needed)

Overflow Possibility Yes, if array is full No, until memory is full

Underflow Check Yes (when top = -1) Yes (when head = NULL)

Memory Usage May waste space if stack is not full Uses only as much memory as needed

Insertion/Deletion Time O(1) – Constant time O(1) – Constant time

Implementation Simple and easier to implement Slightly complex due to pointer handling
Simplicity

Flexibility Less flexible More flexible

Best Used When Size is known and doesn’t change often Size is unknown or varies a lot
3. Queue

What is Queue Data Structure?

A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed
into the order, the operation is first performed on that.

Queue Representation:
Like stacks, Queues can also be represented in an array: In this representation, the Queue is implemented using the array. Variables used in this case are

 Queue: the name of the array storing queue elements.

  Front: Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue. It is also
referred as the head of the queue. The index where the first element is stored in the array representing the queue.
 Rear: Position of the last entry in the queue, that is, the one most recently added, is called the rear of the queue. It is also referred as the tail of the queue. The index
where the last element is stored in an array representing the queue.
 Size: Size refers to the current number of elements in the queue.
 Capacity: Capacity refers to the maximum number of elements the queue can hold.

FIFO Principle of Queue:

 A Queue is like a line waiting to purchase tickets, where the first person in line is the first person served. (i.e. First come first serve).

 Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue(sometimes, head of
the queue), similarly, the position of the last entry in the queue, that is, the one most recently added, is called the rear (or the tail) of the queue. See the below figure.

Characteristics of Queue:
 Queue can handle multiple data.

 We can access both ends.

 They are fast and flexible.

Representation of Queue

Queue Operations:

1. Enqueue: Adds an element to the end (rear) of the queue. If the queue is full, an overflow error occurs.
 2. Dequeue: Removes the element from the front of the queue. If the queue is empty, an underflow error occurs.

3. Peek/Front: Returns the element at the front without removing it.

4. Size: Returns the number of elements in the queue.

5. isEmpty: Returns true if the queue is empty, otherwise false.

6. isFull: Returns true if the queue is full, otherwise false.

Complexity Analysis of Operations on Queue

Operations Time Complexity Space Complexity

enqueue O(1) O(1)

dequeue O(1) O(1)

front O(1) O(1)

size O(1) O(1)

isEmpty O(1) O(1)

isFull O(1) O(1)

Types of Queues
Queue data structure can be classified into 4 types:

1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only insert the element at the back and remove the element from the front of the queue. A simple
queue is efficiently implemented either using a linked list or a circular array.

2. Double-Ended Queue (Deque): In a double-ended queue the insertion and deletion operations, both can be performed from both ends. They are of two types:

 Input Restricted Queue: This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends.

 Output Restricted Queue: This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.

3. Priority Queue: A priority queue is a special queue where the elements are accessed based on the priority assigned to them. They are of two types:

 Ascending Priority Queue: In Ascending Priority Queue, the elements are arranged in increasing order of their priority values. Element with smallest priority value is
popped first.

 Descending Priority Queue: In Descending Priority Queue, the elements are arranged in decreasing order of their priority values. Element with largest priority is popped
first.

Applications of Queue Data Structure

Application of queue is common. In a computer system, there may be queues of tasks waiting for the printer, for access to disk storage, or even in a time-sharing system, for use
of the CPU. Within a single program, there may be multiple requests to be kept in a queue, or one task may create other tasks, which must be done in turn by keeping them in a
queue.

 A Queue is always used as a buffer when we have a speed mismatch between a producer and consumer. For example keyboard and CPU.
  Queue can be used where we have a single resource and multiple consumers like a single CPU and multiple processes.

 In a network, a queue is used in devices such as a router/switch and mail queue.

 Queue can be used in various algorithm techniques like Breadth First Search, Topological Sort, etc.

4. Huffman Coding

🌟 What is Huffman Coding?

Huffman Coding is a method used to compress data. It reduces the number of bits needed to store or transmit information, especially useful in file compression (ZIP, JPEG, MP3, etc.).

It works by assigning shorter codes to more frequent characters and longer codes to less frequent characters.

🪜 Step-by-Step Example of Huffman Coding

Let’s take an example string:

MESSAGE = "AABACD"

✅ Step 1: Count Frequency of Each Character

Characte Frequency
r

A 3

B 1

C 1
 D 1

✅ Step 2: Create Leaf Nodes for Each Character

Each character is treated as a node with its frequency.

A ( 3) , B ( 1) , C ( 1) , D ( 1)

✅ Step 3: Build the Huffman Tree

We repeatedly do the following:

 Pick two nodes with the smallest frequencies

 Combine them into a new node (sum their frequencies)

 Repeat until only one node (root) remains

Step 3.1: Pick B(1) and C(1) → Combine into node BC ( 2 )

Now we have: A ( 3 ) , D ( 1 ) , BC ( 2 )

Step 3.2: Pick D(1) and BC(2) → Combine into node DBC(3)

Now we have: A ( 3 ) and DBC ( 3 )

Step 3.3: Combine: A ( 3 ) and DBC ( 3 ) → Root = ADBC ( 6 )

✅ Step 4: Assign Binary Codes

Now assign 0 to left and 1 to right at each step:

  ASCII Key:

Example 2:
LP = huf_tre( [8, 2, 2, 2, 1, 1] ) we obtain in LP[0] the list [(8, '0'), (2, '100'), (2, '101'), (2, '110'), (1, '1110'), (1, '1111')]

k=0

k=1
 k=2

k=3

k=4

k=5

Finally: