Module-1

Concepts of Abstract Data types:

An Abstract Data Type (ADT) is a programming concept that defines a high-level view of a data
structure, without specifying the implementation details. In other words, it is a blueprint for
creating a data structure that defines the behavior and interface of the structure, without
specifying how it is implemented.

An ADT in the data structure can be thought of as a set of operations that can be performed
on a set of values. This set of operations actually defines the behavior of the data structure,
and they are used to manipulate the data in a way that suits the needs of the program.

Abstract Data Model type:

Lists are linear data structures that hold data in a non-continuous structure. The list is made
up of data storage containers known as "nodes." These nodes are linked to one another,
which means that each node contains the address of another block.

Stacks: A stack is a linear data structure that only allows data to be accessed from the top. It
simply has two operations: push (to insert data to the top of the stack) and pop (to remove
data from the stack). (used to remove data from the stack top).

Queue: A queue is a linear data structure that allows data to be accessed from both ends.
Advantages of ADT in Data Structures are:

 Provides abstraction, which simplifies the complexity of the data structure and
allows users to focus on the functionality.
 Enhances program modularity by allowing the data structure implementation to be
separate from the rest of the program.
 Enables code reusability as the same data structure can be used in multiple
programs with the same interface.
 Promotes the concept of data hiding by encapsulating data and operations into a
single unit, which enhances security and control over the data.

Structures
Structures (also called structs) are a way to group several related variables into one place.
Each variable in the structure is known as a member of the structure.
Unlike an array, a structure can contain many different data types (int, float, char, etc.).

We can create a structure by using the struct keyword and declare each of
its members inside curly braces:

struct MyStructure { // Structure declaration

int myNum; // Member (int variable)
char myLetter; // Member (char variable)
}; // End the structure with a semicolon

Use the struct keyword inside the main () method, followed by the name of
the structure and then the name of the structure variable:

struct myStructure {
int myNum;
char myLetter;
};

int main() {
struct myStructure s1;
return 0;
}
To access members of a structure, use the dot syntax (.):

// Create a structure called myStructure

struct myStructure {
int myNum;
char myLetter;
};

int main() {
// Create a structure variable of myStructure called s1
struct myStructure s1;

// Assign values to members of s1

[Link] = 13;
[Link] = 'B';

// Print values
printf("My number: %d\n", [Link]);
printf("My letter: %c\n", [Link]);

return 0;
}

Union in C

Union can be defined as a user-defined data type which is a collection of different variables of
different data types in the same memory location. The union can also be defined as many members,
but only one member can contain a value at a particular point in time.
Union is a user-defined data type, but unlike structures, they share the same memory location.
Ex:

 struct abc
 {
 int a;
 char b;
 }
The above code is the user-defined structure that consists of two members, i.e., 'a' of
type int and 'b' of type character. When we check the addresses of 'a' and 'b', we found that
their addresses are different. Therefore, we conclude that the members in the structure do
not share the same memory location.

union is defined in the same way as the structure is defined but the difference is that union
keyword is used for defining the union data type, whereas the struct keyword is used for
defining the structure. The union contains the data members, i.e., 'a' and 'b', when we check
the addresses of both the variables then we found that both have the same addresses. It means
that the union members share the same memory location.

In union, members will share the memory location. If we try to make changes in any of the
member then it will be reflected to the other member as well.

 union abc
 {
 int a;
 char b;
 } var;
 int main()
 {
 var.a = 66;
 printf("\n a = %d", var.a);
 printf("\n b = %d", var.b);
 }

In the above code, union has two members, i.e., 'a' and 'b'. The 'var' is a variable of union abc type. In
the main () method, we assign the 66 to 'a' variable, so var.a will print 66 on the screen. Since both
'a' and 'b' share the memory location, var.b will print 'B' (ascii code of 66).

Enum in C
The enum in C is also known as the enumerated type. It is a user-defined data type that
consists of integer values, and it provides meaningful names to these values. The use of enum
in C makes the program easy to understand and maintain. The enum is defined by using the
enum keyword.

The way to define the enum in C:

enum flag{integer_const1, integer_const2,.....integter_constN};

enum fruits{mango, apple, strawberry, papaya};

 The default value of mango is 0, apple is 1, strawberry is 2, and papaya is 3. If we want
to change these default values, then we can do as given below:

 enum fruits{
 mango=2,
 apple=1,
 strawberry=5,
 papaya=7,
 };

Examples:

1. #include <stdio.h>
2. enum weekdays{Sunday=1, Monday, Tuesday, Wednesday, Thursday, Friday, Saturd
ay};
3. int main()
4. {
5. enum weekdays w; // variable declaration of weekdays type
6. w=Monday; // assigning value of Monday to w.
7. printf("The value of w is %d",w);
8. return 0;
9. }

Pointer
A pointer can be used to store the memory address of other variables, functions, or even
other pointers. The use of pointers allows low-level memory access, dynamic memory
allocation, and many other functionalities in C.

datatype * ptr;
where
 ptr is the name of the pointer.
 datatype is the type of data it is pointing to

The use of pointers in C can be divided into three steps:

1. Pointer Declaration
2. Pointer Initialization
3. Pointer Dereferencing
[Link] Declaration
In pointer declaration, we only declare the pointer but do not initialize it. To declare a
pointer, we use the ( * ) dereference operator before its name.
Example
int *ptr;

The pointer declared here will point to some random memory address as it is not initialized.
Such pointers are called wild pointers.

2. Pointer Initialization
Pointer initialization is the process where we assign some initial value to the pointer variable.
We generally use the ( & ) addressof operator to get the memory address of a variable and
then store it in the pointer variable.
Example
int var = 10;
int * ptr;
ptr = &var;

3. Pointer Dereferencing
Dereferencing a pointer is the process of accessing the value stored in the memory address
specified in the pointer. We use the same ( * ) dereferencing operator that we used in the
pointer declaration.

// C program to illustrate Pointers

#include <stdio.h>

void gs()
{
int var = 10;

// declare pointer variable

int* ptr;

// note that data type of ptr and var must be same

ptr = &var;

// assign the address of a variable to a pointer

printf("Value at ptr = %p \n", ptr);
printf("Value at var = %d \n", var);
 printf("Value at *ptr = %d \n", *ptr);
}

int main()
{
gs();
return 0;
}

Output:
Value at ptr = 0x7fff1038675c
Value at var = 10
Value at *ptr = 10

The concept of dynamic memory allocation in c language enables to allocate memory at

runtime. Dynamic memory allocation in c language is possible by 4 functions of stdlib.h header
file.
1. malloc()
2. calloc()
3. realloc()

4. free()

static memory allocation dynamic memory allocation

memory is allocated at compile memory is allocated at run time.

time.

memory can't be increased while memory can be increased while executing

executing program. program.

used in array. used in linked list.

malloc() allocates single block of requested memory.

calloc() allocates multiple block of requested memory.

realloc() reallocates the memory occupied by malloc() or calloc() functions.

free() frees the dynamically allocated memory.

 The malloc() function allocates single block of requested memory:

 It doesn't initialize memory at execution time, so it has garbage value initially.

 It returns NULL if memory is not sufficient.
 The syntax of malloc() function is given below:

ptr=(cast-type*)malloc(byte-size)
malloc example

1. #include<stdio.h>
2. #include<stdlib.h>
3. int main(){
4. int n,i,*ptr,sum=0;
5. printf("Enter number of elements: ");
6. scanf("%d",&n);
7. ptr=(int*)malloc(n*sizeof(int)); //memory allocated using malloc
8. if(ptr==NULL)
9. {
10. printf("Sorry! unable to allocate memory");
11. exit(0);
12. }
13. printf("Enter elements of array: ");
14. for(i=0;i<n;++i)
15. {
16. scanf("%d",ptr+i);
17. sum+=*(ptr+i);
18. }
19. printf("Sum=%d",sum);
20. free(ptr);
21. return 0;
22. }

Output: Enter elements of array: 3

Enter elements of array: 10
10
10
Sum=30
calloc() function in C:

 The calloc() function allocates multiple block of requested memory.

 It initially initialize all bytes to zero.
 It returns NULL if memory is not sufficient.
 The syntax of calloc() function is given below:

ptr=(cast-type*)calloc(number, byte-size)

free() function in C

The memory occupied by malloc() or calloc() functions must be released by calling free()
function. Otherwise, it will consume memory until program exit.

Module-2

Data structures using Array

Stack: Stack is a linear data structure that follows LIFO (Last In First Out) Principle, so
the last element inserted is the first to be popped out.

Basic Operations on Stack:

 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.
 isFull() returns true if the stack is full else false.
Algorithm for Push Operation:

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

Algorithm for isEmpty Operation.

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

Advantages of Stack:

 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.
Precedence rule:

Operators Symbols

Parenthesis ( ), {}, [ ]

Exponents ^

Multiplication and Division *, /

Addition and Subtraction +,-

The first preference is given to the parenthesis; then next preference is given to the
exponents. In the case of multiple exponent operators, then the operation will be
applied from right to left.

Infix expression: 2 + 3 * 4

We will start scanning from the left most of the expression. The multiplication operator
is an operator that appears first while scanning from left to right. Now, the expression
would be:

Expression = 2 + 34*

= 2 + 12

Again, we will scan from left to right, and the expression would be:

Expression = 2 12 +

Infix Postfix expression:

Infix expression: The expression of the form “a operator b” (a + b) i.e., when
an operator is in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When
every pair of operands is followed by an operator.
Prefix: It is the form of an arithmetic notation in which we fix (place) the
arithmetic operator before (pre) its two operands.
Example: * + A B – C D

Infix expression example: a+b*c

Its corresponding postfix expression: abc*+
Following steps explains how these conversion has done.
Step 1: a + bc* (Here we have two operators: + and * in which * has
higher precedence and hence it will be evaluated first).
Step 2: abc*+ (Now we have one operator left which is + so it is
evaluated)

Queue
A queue can be defined as an ordered list which enables insert operations to be performed at one end
called REAR and delete operations to be performed at another end called FRONT. Queue is referred
to be as First In First Out list.

For example, people waiting in line for a rail ticket form a queue.

Application of Queue:

1. Queues are widely used as waiting lists for a single shared resource like printer,
disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being
transferred at the same rate between two processes) for eg. pipes, file IO,
sockets.
 3. Queues are used as buffers in most of the applications like MP3 media player,
CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and
remove the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.

Operations performed on queue

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

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
o 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.
o 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.
o Queue overflow (isfull): It shows the overflow condition when the queue is
completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.

Types of Queue
There are four different types of queue that are listed as follows -
Simple Queue or Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from
another end. The end at which the insertion takes place is known as the rear end, and
the end at which the deletion takes place is known as front end. It strictly follows the
FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear
end. If the first three elements are deleted from the Queue, we cannot insert more
elements even though the space is available in a Linear Queue. In this case, the linear
Queue shows the overflow condition as the rear is pointing to the last element of the
Queue.

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear
Queue except that the last element of the queue is connected to the first element. It
is also known as Ring Buffer, as all the ends are connected to another end. The
representation of circular queue is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If
the empty space is available in a circular queue, the new element can be added in an
empty space by simply incrementing the value of rear. The main advantage of using
the circular queue is better memory utilization.

Priority Queue
It is a special type of queue in which the elements are arranged based on the priority.
It is a special type of queue data structure in which every element has a priority
associated with it. Suppose some elements occur with the same priority, they will be
arranged according to the FIFO principle. The representation of priority queue is shown
in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority
queue occurs based on the priority. Priority queue is mainly used to implement the
CPU scheduling algorithms.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends
of the queue either from the front or rear. It means that we can insert and delete
elements from both front and rear ends of the queue. Deque can be used as a
palindrome checker means that if we read the string from both ends, then the string
would be the same.