This function helps to see the data at the front of the queue.

The algorithm of peek() function is

as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer
to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a
circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull

if rear equals to MAXSIZE

return true
else
return false
endif

end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty

if front is less than MIN OR front is greater than rear

return true
 else
return false
endif

end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence
empty.
Here's the C programming code −
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively
difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
 Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
Algorithm for enqueue operation
procedure enqueue(data)

if queue is full
return overflow
 endif

rear ← rear + 1
queue[rear] ← data
return true

end procedure
Implementation of enqueue() in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;

rear = rear + 1;
queue[rear] = data;

return 1;
end procedure
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is
pointing and remove the data after access. The following steps are taken to
perform dequeue operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
 Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.

Algorithm for dequeue operation

procedure dequeue
 if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure
Implementation of dequeue() in C programming language −
Example
int dequeue() {
if(isempty())
return 0;

int data = queue[front];

front = front + 1;

return data;
}
 Lecture-07
LINKED LIST
A linked list is a sequence of data structures, which are connected together via links.
Linked List is a sequence of links which contains items. Each link contains a connection
to another link. Linked list is the second most-used data structure after array. Following
are the important terms to understand the concept of Linked List.
 Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called Next.
 LinkedList − A Linked List contains the connection link to the first link called
First.
Linked List Representation
Linked list can be visualized as a chain of nodes, where every node points to the next
node.

As per the above illustration, following are the important points to be considered.
 Linked List contains a link element called first.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 Last link carries a link as null to mark the end of the list.
Types of Linked List
Following are the various types of linked list.
 Simple Linked List − Item navigation is forward only.
 Doubly Linked List − Items can be navigated forward and backward.
 Circular Linked List − Last item contains link of the first element as next and
the first element has a link to the last element as previous.
Basic Operations
Following are the basic operations supported by a list.
 Insertion − Adds an element at the beginning of the list.
 Deletion − Deletes an element at the beginning of the list.
 Display − Displays the complete list.
 Search − Searches an element using the given key.
 Delete − Deletes an element using the given key.
Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this
with diagrams here. First, create a node using the same structure and find the location
where it has to be inserted.
Imagine that we are inserting a node B (NewNode), between A (LeftNode)
and C (RightNode). Then point B.next to C −
NewNode.next −> RightNode;
It should look like this −

Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list.
While inserting it at the end, the second last node of the list should point to the new
node and the new node will point to NULL.
Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial
representation. First, locate the target node to be removed, by using searching
algorithms.

The left (previous) node of the target node now should point to the next node of the
target node −
LeftNode.next −> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following
code, we will remove what the target node is pointing at.
TargetNode.next −> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can
simply deallocate memory and wipe off the target node completely.

Reverse Operation
This operation is a thorough one. We need to make the last node to be pointed by the
head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall
make it point to its previous node −

We have to make sure that the last node is not the lost node. So we'll have some temp
node, which looks like the head node pointing to the last node. Now, we shall make all
left side nodes point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their
predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf("\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//mark next to first link as first

head = head->next;

//return the deleted link

 return tempLink;
}

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key

struct node* find(int key) {

//start from the first link

struct node* current = head;

//if list is empty

if(head == NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}
 //if data found, return the current Link
return current;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link

struct node* current = head;
struct node* previous = NULL;

//if list is empty

if(head == NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}

return current;
}
void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length();

k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {

current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}
 *head_ref = prev;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
 } else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
If we compile and run the above program, it will produce the following result −
Output
Original List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56)
Deleted value:(5,40)
Deleted value:(4,1)
Deleted value:(3,30)
Deleted value:(2,20)
Deleted value:(1,10)
List after deleting all items:
[]
Restored List:
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1)
List after deleting an item:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data:
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data:
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
 Lecture-08
Polynomial List
A polynomial p(x) is the expression in variable x which is in the form (ax n + bxn-1 + …. +
jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.
An important characteristics of polynomial is that each term in the polynomial
expression consists of two parts:
 one is the coefficient
 other is the exponent
Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value.
Points to keep in Mind while working with Polynomials:
 The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself
 Additional terms having equal exponent is possible one
 The storage allocation for each term in the polynomial must be done in
ascending and descending order of their exponent

Representation of Polynomial
Polynomial can be represented in the various ways. These are:
 By the use of arrays
 By the use of Linked List
Representation of Polynomials using Arrays
There may arise some situation where you need to evaluate many polynomial
expressions and perform basic arithmetic operations like: addition and subtraction with
those numbers. For this you will have to get a way to represent those polynomials. The
simple way is to represent a polynomial with degree 'n' and store the coefficient of n+1
terms of the polynomial in array. So every array element will consists of two values:
 Coefficient and
 Exponent
Representation of Polynomial Using Linked Lists
A polynomial can be thought of as an ordered list of non zero terms. Each non zero
term is a two tuple which holds two pieces of information:
  The exponent part
 The coefficient part
Adding two polynomials using Linked List
Given two polynomial numbers represented by a linked list. Write a function that add
these lists means add the coefficients who have same variable powers.
Example:

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0
struct Node

int coeff;

int pow;

struct Node *next;

};

void create_node(int x, int y, struct Node **temp)

struct Node *r, *z;

z = *temp;

if(z == NULL)

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

r->coeff = x;

r->pow = y;

*temp = r;

r->next = (struct Node*)malloc(sizeof(struct Node));

r = r->next;

r->next = NULL;

else

r->coeff = x;

r->pow = y;
 r->next = (struct Node*)malloc(sizeof(struct Node));

r = r->next;

r->next = NULL;

void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)

while(poly1->next && poly2->next)

if(poly1->pow > poly2->pow)

poly->pow = poly1->pow;

poly->coeff = poly1->coeff;

poly1 = poly1->next;

else if(poly1->pow < poly2->pow)

poly->pow = poly2->pow;

poly->coeff = poly2->coeff;

poly2 = poly2->next;

else

poly->pow = poly1->pow;

poly->coeff = poly1->coeff+poly2->coeff;
 poly1 = poly1->next;

poly2 = poly2->next;

poly->next = (struct Node *)malloc(sizeof(struct Node));

poly = poly->next;

poly->next = NULL;

while(poly1->next || poly2->next)

if(poly1->next)

poly->pow = poly1->pow;

poly->coeff = poly1->coeff;

poly1 = poly1->next;

if(poly2->next)

poly->pow = poly2->pow;

poly->coeff = poly2->coeff;

poly2 = poly2->next;

poly->next = (struct Node *)malloc(sizeof(struct Node));

poly = poly->next;

poly->next = NULL;

}
}

void show(struct Node *node)

while(node->next != NULL)

printf("%dx^%d", node->coeff, node->pow);

node = node->next;

if(node->next != NULL)

printf(" + ");

int main()

struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;

// Create first list of 5x^2 + 4x^1 + 2x^0

create_node(5,2,&poly1);

create_node(4,1,&poly1);

create_node(2,0,&poly1);

// Create second list of 5x^1 + 5x^0

create_node(5,1,&poly2);

create_node(5,0,&poly2);

printf("1st Number: ");

show(poly1);

printf("\n2nd Number: ");

show(poly2);
 poly = (struct Node *)malloc(sizeof(struct Node));

// Function add two polynomial numbers

polyadd(poly1, poly2, poly);

// Display resultant List

printf("\nAdded polynomial: ");

show(poly);

return 0;

Output:

1st Number: 5x^2 + 4x^1 + 2x^0

2nd Number: 5x^1 + 5x^0
Added polynomial: 5x^2 + 9x^1 + 7x^0
 Lecture-09
Doubly Linked List
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer,
together with next pointer and data which are there in singly linked list.

Following is representation of a DLL node in C language.

/* Node of a doubly linked list */
struct Node {
int data;
struct Node* next; // Pointer to next node in DLL
struct Node* prev; // Pointer to previous node in DLL
};
Following are advantages/disadvantages of doubly linked list over singly linked list.
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is
given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get
this previous node, sometimes the list is traversed. In DLL, we can get the previous
node using previous pointer.
Disadvantages over singly linked list
1) Every node of DLL Require extra space for an previous pointer. It is possible to
implement DLL with single pointer though
2) All operations require an extra pointer previous to be maintained. For example, in
insertion, we need to modify previous pointers together with next pointers. For
example in following functions for insertions at different positions, we need 1 or 2 extra
steps to set previous pointer.
Insertion
A node can be added in four ways
1) At the front of the DLL
2) After a given node.
3) At the end of the DLL
4) Before a given node.
1) Add a node at the front: (A 5 steps process)
The new node is always added before the head of the given Linked List. And newly
added node becomes the new head of DLL. For example if the given Linked List is
10152025 and we add an item 5 at the front, then the Linked List becomes 510152025.
Let us call the function that adds at the front of the list is push(). The push() must
receive a pointer to the head pointer, because push must change the head pointer to
point to the new node

2) Add a node after a given node.: (A 7 steps process)

We are given pointer to a node as prev_node, and the new node is inserted after the
given node.

3) Add a node at the end: (7 steps process)

The new node is always added after the last node of the given Linked List. For example
if the given DLL is 510152025 and we add an item 30 at the end, then the DLL becomes
51015202530. Since a Linked List is typically represented by the head of it, we have to
traverse the list till end and then change the next of last node to new node.

4) Add a node before a given node:

Steps
Let the pointer to this given node be next_node and the data of the new node to be
added as new_data.