# Algorithms

## Big Omega(Ω) Notation

Ω Notation provides the asymptotic lower bound on the function. A function needs to satisfy some conditions in order to be in Ω notation.Ω(g(n)) is the best case running time  of function g(n) within a constant factor.

Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0}.It is used to bound the best case running time of an algorithm.g(n) is an asymptotic lower bound for f(n).

Example 1

• Prove that if  f(n) = 15n3 + n2 + 4, then f(n) belongs to Ω(n3 ) for all n.
• For omega notation,c*g(n) should be less than f(n).
• Here f(n) = 15n3 + n2 + 1
• g(n) = n3
• Let c=15
•  15  n3 <=  15n3 + n2 + 1
• n=1
• f(n) belongs to Ω class.
• Ω is the lower bound.

Example 2

• Show that 2n +7 is Ω(n) .
• f(n) = 2n + 7
• g(n) = 2n
• c * g(n) <= f(n)
• c*2n <=2n+7
• Let c=2
• 4n<=2n+7
• 2n<=7
• n<=7/2
• Thus for c=2 and  n0= 7/2 f(n) belongs to Ω(n).

Short URL: http://tinyit.cc/49f498
March 4, 2016 |
Tags:

## Dijkstra’s algorithm

Dijkstra’s algorithm is way of finding shortest path from a source vertex to sink in a given connected and weighted graph.It is somewhat similar to Prim’s algorithm.It works for directed as well as undirected graphs.

• Source vertex is chosen and marked.
• Mark distances at all vertices as infinity and at source vertex as 0.
• Update the distances of adjacent vertices from infinity by given distances on the graph .
• We look for minimum distance value from source vertex to adjacent vertices.
• The minimum distance is chosen and next vertex is marked.
• Look for the adjacent vertices of marked vertex.
• Replace the distance if it is less than the mentioned value at the vertices.
• Keep on following the same procedure until shortest path to sink is obtained.

Example

Consider a weighted and undirected graph as shown in Fig 1

Fig 1 : A Graph

• Choose a source vertex.In Fig 2 ,a is chosen as the source vertex.
• Mark all the distances at vertices as infinity initially and distance of source vertex as 0

Fig 2: Mark infinity at all vertices and 0 at the source.

• Look for neighbors of source vertex a.(Fig 3).
• b and i are the adjacent vertices.
• Update the distance at b from infinity to 4 and at i to 8.
• Find the minimum distance from a.
• 4 is smaller than 8 so b is the next marked vertex.

Fig 3:Update b ,i ,mark vertex b and Edge(a,b)

• Look for the neighbors of b.
• c and i are the adjacent vertices.
• Update value at c from infinity to 12(4+8) as distance from source to c is 12.(Fig 4)
• Distance from a to i through b is 15(11+4)  and a to i directly is 8.So 8 is not updated.
• Look for next min distance  to a vertex and do not count already marked vertices and edges.
• The distance at c is 12 and at i is 8,so i  is marked.

Fig 4 : Update c to 12 and mark vertex i

• Look for neighbors of i .
• Update distance at h to 15(8+7) and at g to 9.
• Distance from source a to b is 4 and a to b through i is 19 so it is not updated.
• Look for next minimum distance from marked vertices.
• 12,15,9 are the respective distances from marked vertices.
• Mark vertex g and Edge(i,g) as 9 is the minimum distance from source a to g through i.

Fig 5 : Mark g

• Look for neighbors of g.
• The distance at h from a through i  is 15 and from a through  i and g is again 15 so it is not updated(Fig 6).
• The distance from a to f through i and g is 11.So update it by 11.

Fig 6 : Update distance at f to 11

• Look for the next minimum distance(Fig 7).
• 12,15,11 are the distances from marked vertices.
• Mark f and Edge(g,f) as distance is minimum.

Fig 7 : Mark f

• Neighbors of f are c,d,e.
• Distance at c is not required to be updated.
• Update distance at d to 25(11+14) and at e to 21(11+10)(Fig 8).
• Look for minimum distance.
• 12,15,19,21 are the distances available for consideration.
• Mark vertex c as 12 is minimum.

Fig 8 : Mark c

• Distance of neighbors of c is not required to be updated.
• Mark d and then e.(Fig 9)

Fig 9 : Mark d and e.

The following table gives the details of dijkstra’s algorithm applied on Fig 1.The shortest path from a to e is {a,b,i,g,f,c,d,e} with minimum cost of 21.

Fig 10

Short URL: http://tinyit.cc/eff02d
August 12, 2014 |
Tags:

## Big O Notation

• It gives rate of growth of step count function(f(n)) in terms of simple function(g(n)) and defines the asymptotic upper bound on function(Fig 1).
• To simplify the estimation for running time,constants and lower order terms are ignored.
• The function needs to satisfy following conditions in order to be in Big-O class.Given functions f(n) and g(n),we say f(n) is  O(g(n)) if and if
• f(n) < c * g(n)  for all n > n0
• where c  and n0 are positive constants.
• The function nis does not belong  to O(n) rather it belongs to O( n2 ) as it fails to satisfy the inequality f(n)<=cg(n).n2  cannot be less than n in any case as c is constant.
•  O(..) is worst case (upper bound) notation for an algorithm’s complexity .

Fig 1: Big O Notation

Example 1

• Consider T(n)= 3n+2
• g(n) = n
• f(n) = 3n+2
• We need to find first value of c where answer comes positive.Let c=1
• f(n)<=c * g(n)
• 3n+2 <= c *n
• 3n+2 <= 1*n
• The answer comes in negative,so we cant choose c=1.
• Let c=2
• 3n+2 <= 2n The answer again comes in negative,so we cant choose c=2.
• c=3
• 3n+2<=3n,can’t choose c=3
• c=4
• 3n+2<=4n
• n>=2
• n0=2 and c=3.This is the point where f(n) and g(n) meets.
• Hence f(n)<=c*g(n) and thus belongs to big-O class.
• Highest power of n is 1.
• So f(n) belongs to O(n).

Example 2

• Consider  T(n) = 2n2 + 4
• g(n)=n
• f(n) = 2n2 + 4
•  2n2 + 4<=c *n
• The inequality is false for c=1 and c=2.
• c=3

2n2 + 4<=3 *n

4<=n

n=2 and n=-2,negative value is neglected.

• n>=2,n0=2 ,c=3
• Thus f(n) belongs to O(n) .

Example 3

• T(n) = 3n3+20n2+ 5
• 3n3+20n2+ 5 <=c * n
• Is true for c=4 and n= 21
• Thus 3n3+20n2+ 5 belongs to O(n3).

Example 4

• T(n) = 3  log n +5
• g(n) = log n
• f(n) = 3 log n +5
• f(n) <= c *g(n),c>0 and  n > n0
• 3 log n + 5 <=c * log n
• c =8 and n= 2
• Thus 3n3+20n2+ 5 belongs to O(n3

### Complexities of algorithms

The various big 0 complexities are given in Fig 2 and Fig 3.

Fig 2: Complexities of sorting algorithms

Fig 3 : Complexities of sorting algorithms

Short URL: http://tinyit.cc/e988e7
July 26, 2014 |
Tags:

## Time and Space Complexity

Before defining the actual term complexity, let us discuss about few real life scenarios.Take an example of railway reservation counter.People go there to book their tickets.The time to book tickets will depend on  how many service windows are available, queue size and time taken by each representative.A person will either go in a lane which is very short or will stand in queue where representative is very fast.Take another example of sitting plan of 40 students.The first thing to be considered is the no. of chairs needed and second thing is their order of sitting.If they sit roll.no wise then it will be easy for teacher to take attendance and time required will be lesser.Thus every process in the real world depends on how much time it takes to execute and how much space it consumes.Complexity is defined as the running time to execute a process and it depends on space as well as time.

It is of two types:

• Space Complexity
• Time Complexity

Basic Operation

Basic operation means the main operation that will be required to solve particular problem.For example the basic operation in searching is comparison.The complexity depends on the basic operation.

The focus to determine the cost is done on running time i.e time complexity and it depends on the following factors

• Size of Input Data
• Hardware
• Operating System
• Programming Language used

## Space Complexity

The amount of computer memory required to solve the given problem of particular size is called as space complexity.The space complexity depends on two components

•  Fixed Part – It is needed for instruction space i.e byte code.variable space,constants space etc.
•  Variable Part – Instance of input  and output data.
• Space(S) = Fixed Part + Variable Part

Example 1

Algorithm sum(x,y)

{

return x+y;

}

Two computer words will be required to store variable x and y so ,

Space Complexity (S)= 2.

Example 2

Algorithm sum( a[], n)

{

sum =0;

for(i=0;i<=n;i++)

{

sum = sum + a[i];

return sum;

}

Space complexity is calculated as follows

• One computer word is required to store n.
• n space is required to store array a[].
• One space  for variable sum and one for i is required.
• Total Space(S) =1 +n +1 +1=n+3

## Time Complexity

The time required to analyze the given problem of particular size is known as the time complexity.It depends on two components

• Fixed Part – Compile time
• Variable Part – Run time dependent on problem instance.Run time is considered usually and compile time is ignored.

### Ways to measure time complexity

• Use a stop watch and  time is obtained in seconds or milliseconds.
• Step Count - Count no of program steps.
• Comments are not evaluated so they are not considered as program step.
• In while loop steps are equal to the number of times loop gets executed.
• In for loop,steps are equal to number of times an expression is checked for condition.
• A single expression is considered as a single step.Example a+f+r+w+w/q-d-f is one step.
• Rate of Growth(Asymptotic Notations)

Example of step count

Algorithm sum( a[], 5)

{

sum =0;

for(i=0;i<=5;i++)

{

sum = sum + a[i];

}

return sum;

}

Fig 1 : Step Count

Step count is a difficult approach if we need to compare results.For e.g.If we used two techniques to solve one problem and T(1) is the running time of first technique and T(2) is the running time of second technique.Say T(1) =( n+1 )and T(2) is (n2 + 1).We cannot decide which one is the better solution,so for comparisons ‘Rate of growth‘  i.e. asymptotic notations of time space complexity functions are much convenient to use.

### Asymptotic Notations

These notations gives the rate of growth.Instead of dealing with exact expressions we deal with asymptotic behavior.Asymptotic means to approach a value or curve arbitrarily closely.Focus is on the exponential behavior of equation.If we have expression like T(n)=3n3 +5 and T(n)=7 n3 +10n2+5 we will consider on highest power i.e n3.The analysis will not really change as these both equations are similar to n3.But on contrary we need to separate our results if analysis are like T(n) = 3n+5 and T(n)=10n2+5 as highest powers are different.The three asymptotic notations are:

## Cases in complexity

• Best Case
• Average Case
• Worst Case

### Best Case

It is the minimum time required to solve the given problem of particular size.For e.g.in linear search if element is found at first location then it will be the best case scenario and complexity will be O(1) as the running time is minimum.

### Average Case

It is average cost and time required for a given problem of particular size.For e.g. in linear search if there are n elements and item is found at n/2 location,then it will be a average case scenario and complexity will be O(n/2).

### Worst Case

The maximum time required to solve a given problem of particular size.For e.g in linear search the worst case will either be item is present at last location or it is not present.The complexity will be O(n).

Short URL: http://tinyit.cc/f9484
July 25, 2014 |
Tags:

## Pop operation in Stack

### POP Operation

In this  operation topmost element is deleted from the stack.Before deleting check if TOP = NULL.If yes,it means that stack is empty and no deletion can be done.If an attempt to delete element is made in this case the UNDERFLOW message will be printed on screen.If no,then element is deleted then value of TOP is decremented by 1.

For example

• We want to delete/pop 100 from this stack(Fig 9).
• TOP = 4
• TOP is not equal to null.
• 100 is popped out/deleted.
• TOP variable gets decremented to 3.

Fig 9 : Pop Operation in Stack

Program 2

#include<stdio.h>

```int main()
{
int max;
int stack[10];
int num,val,i,temp;
int top = -1;
//printf("Enter the maximum size of stack");
scanf("%d",&max);
//printf("Enter the no of elements in stack");
scanf("%d",&num);
//printf("Enter the elements of stack");
for(i=0;i<num;i++)
{
scanf("%d\n",&stack[i]);
top++;
}
temp =top;
if(top == -1)
{
printf("Underflow");
}
else
{
top =top -1;
printf("The stack after pop operation is \n");
for(i=0;i<temp;i++)
{
printf("%d\n",stack[i]);
top++;
}
}
return 0;
}```

Illustration of Program 2

• Refer Program 1 for working of for loop and consider the same values.
• top = 4
• temp = top i.e temp = 4
• if( top ==-1) i.e if no element is present in the stack then Underflow message will be printed on screen as no element is present to pop out.
• top = top -1 =4-1=3.
• for(i=0;i<temp;i++) - i would iterate till it is less than temp(4).
• Elements of stack after pop operation is printed.

Short URL: http://tinyit.cc/dd0e98
July 18, 2014 |
Tags:

## Push operation in Stack

### Push Operation

In this operation,the element is inserted at the top of stack(Fig 4).In order to insert element we need to check whether TOP = MAX-1.If  yes,then insertion  is not possible.If  element is still  tried for insertion , OVERFLOW message will be printed on screen as the stack do not have extra space to handle new element.If space is present and element is inserted,then the value of top will be incremented by 1 .

For example

• Say we want to insert/push 800 in the following stack(Fig 4).
• TOP = 4(index starts from 0)
• MAX= 13
• The value of TOP is 4 and MAX-1 is 13-1=12.TOP and MAX are not equal,thus element 800 can be pushed into the stack.
• After insertion value of TOP gets incremented t0 5.

Fig 5 : Push Operation in stack

Program 1

```#include<stdio.h>
int main()
{
int stack[10];
int max;
int num;
int top = -1;
int i;
int item;
//printf("Enter the maximum size of stack");
scanf("%d",&max);
//printf("Enter the no of elements in stack");
scanf("%d",&num);
//printf("Enter the elements of stack");
for(i=0;i<num;i++)//Fig 7
{
scanf("%d\n",&stack[i]);
top++;
}

if(top == max -1)//Fig 8
{
printf("Overflow");
}
else
{
//printf("Enter the item you want to insert\n");
scanf("%d",&item);
top = top + 1;//Fig 6
stack[top] = item;
printf("The stack after push operation is \n");
for(i=0;i<=num;i++)
{
printf("%d\n",stack[i]);
top++;
}
}

return 0;
}```

Illustration of Program 1

• Integer array of stack with size 10 is defined.
• max is the maximum capacity of stack(Say 10).
• num is the actual number of elements in stack(Say 5).
• Variable top is initialized to -1.
• i is used in for loop and item is the element we want to push in stack.
• for loop(Fig 7) and scanf are used to read the values of stack.

Fig 6 : Push Operation

Fig 7 : Working of for loop

Fig 8 : Working of if statement

Short URL: http://tinyit.cc/8c08e2
|
Tags:

## Binary Search

### Binary Search

The binary search technique works only on sorted array.It works by comparing the input element to the middle element of array.The comparison determines whether the element is less than.greater than or equal to middle element.Subsequent steps to be followed are written and explained by the following program.

#### Program

```#include <stdio.h>

int main()
{
int val[10] = {10,20,30,40,50,55,68,77,89,90};//Fig 3
int beg = 0;   //first index of array
int end = 9;  //end(last index of array)  = n-1 where n is the size of array and is 10 in this case.
int mid = (beg+end)/2; // finds middle index of array.
int i;
int element;
//printf("enter the element you want search for");
scanf("%d",&element);
for(i=0;i<10;i++) //Fig 4
{
if(val[mid] == element)	{
break;
}
else if(val[mid] < element) {
beg = mid +1;
mid = (beg +end)/2;
}
else{
end =mid -1;
mid = (beg +end)/2;
}
}
printf("Location of element is %d",mid);
return 0;
}```

##### Illustration

Fig 3:An Array

• val[10] of int type is initialized with values 10,20,30,40,50,55,68,77,89,90.
• beg variable of int type denotes the first index of array i.e. 0
• end variable of int type denotes the last index of array .It is equal to (n-1),where n is the size of array.Here it is 10 so end=10-1=9
• mid index is calculated by adding beg plus end and the dividing the result by 2.
• element variable of int type is the data item which needs to be searched for in array and is entered by user using scanf.
• Say we want to search for 68 .
• The following  figure explains the working of for loop to find 68.

Fig 4 : Explanation of Binary Search Program

Short URL: http://tinyit.cc/89edd
|
Tags:

## Kruskal’s Algorithm

Kruskal’s algorithm is a greedy technique  used to find minimum spanning tree from the graph.It works on edges rather than on vertices in connected weighted graph.MST is obtained by finding global optimal choice.

Technique

• Mark the minimum weight edge in the graph and mark the respective vertices.
• Now,mark the next minimum value in the graph.
• If there are two or more edges with same weight then select any edge at one time and then select others one by one.
• We need to mark edges according to the increasing weight of edges of different vertices.
• Do not mark any edge on the graph which makes a cycle.
• Keep on repeating the process till MST is obtained.

Example

Consider connected weighted graph in Fig 1.

Fig 1 : A Graph

• The minimum edge weight on the graph is 1.Edge(Q,R) and Edge (S,W) have same weight i.e 1.
• Choose any edge between them.
• Say we mark Edge(Q,R).(Fig 2)
• Mark vertices Q and R also.

Fig 2

• Now,mark Edge(S,W) with weight 1.
• Mark vertices S and W also.(Fig 3)

Fig 3

• Next min weight edge is 2.
• Mark Edge(Q,P) and vertex P.(Fig 4)

Fig 4

• The next min value in the graph is 3.
• Mark Edge(R,S).(Fig 5)

Fig 5

• The next min value is 4.
• Choose any edge between Edge(Q,T) or Edge(S,T).
• Say we mark Edge(S,T) with weight 4.
• The next value to be marked is 4 but if we will mark Edge(Q,T) a cycle SRQTS will be formed.
• So,do not mark this edge.
• We do  not mark Edge(P,R) with weight 5,Edge(T,W) with weight 6,Edge(P,S) with weight 13 for the same reason.(Cycle formation).
• Now,mark Edge(W,X) with weight 14 and mark vertex X.(Fig 6)

Fig 6

Minimum spanning tree is obtained as shown in Fig 7 and cost of minimum spanning tree is obtained by adding weights of all edges i.e 2+1+3+4+1+14=25

Fig 7

Short URL: http://tinyit.cc/91e90b
|
Tags:

## Prim’s algorithm

Prim’s algorithm is a greedy algorithm as it  finds the global optimum answer from collecting locally optimum choices.It finds the minimum spanning tree and works for weighted,connected and undirected graph.Minimum spanning tree is a graph is edge weighted graph whose weight is smaller than any other spanning tree.A minimum spanning tree is obtained by combining all local optimal choices to a global one.

Technique

• Put   as the weight at all vertices of the graph.
• Write null as the parent of each vertex.
• Pick any vertex from the graph.
• Mark it and replace the distance from  ∞  to 0.
• Look for adjacent vertices of marked vertex.
• Replace   by given weights from the marked vertex to other vertices.
• Replace parent null by marked vertex name.
• Choose minimum weight edge from the marked vertex.
• Mark edge and another vertex .
• Look for the adjacent vertices.
• If edge weight is smaller then replace the value as well by the parent.
• Now,look for all  edges from previous and newly marked vertex.
• Choose the unvisited  vertex which is at minimum edge weight  from marked vertices.(Do not look again at  marked vertices).
• Repeat the process till optimum solution is reached.
• Minimum spanning tree is obtained as a result.

Example

Consider graph in Fig 1.

Fig 1 : A weighted graph

• Initially,put   followed by null and separated by comma at all vertices of graph.(Fig 2)
•    is the weight and null is the parent

Fig 2

• Choose any vertex from the graph.
• Say T is chosen.
• Mark T and replace weight  by 0.(Fig 3)
• Add T to the set i.e resulting sequence.

Fig 3

• Look for adjacent vertices of T.
• R,S,W are the adjacent vertices.
• Replace weights of R,S,W by 12,4,6 respectively  they are the distances from T.
• Replace parent of all adjacent vertices by T.(Fig 4)

Fig 4

• Choose the  edge from T which has minimum weight.
• Edge(T,S) is the shortest i.e 4(compared to 12 and 6).
• So mark the edge as well the vertex S.(Fig 5).
• Add S to the set.

Fig 5

• Look for adjacent neighbors of S.
• P,R,W are the adjacent vertices.
• Replace value at P by 13 and parent by S, as 13 is the edge weight from S to P.
• Compare the edge weight betweenEdge(S, R )and  Edge(T, R).
• S to R is 3 and T to R is 12.3 is smaller than 12.
• So,replace 12 by  3 and T by S.
• Compare weights between  Edge (S , W) and Edge (T ,W).
• S to W is 1 and T to W is 6.
• 1 is smaller so replace 6,T by 1,S.(Fig 6)

Fig 6

• Look for minimum edge  from T and S respectively.
• 1 is minimum value(Edge(S,W) ).
• Mark edge(S,W) ,vertex W and add them to the set.(Fig 7)

Fig 7

• Do not look for visited vertices again.
• Look for edges of T,S,W.
• 3 is minimum edge value.
• Mark edge and vertex R.
• Add R to the set.
• Look for unmarked adjacent vertices of R.
• P is the  unmarked vertex adjacent to R.
• Replace 13 by 5 and S by R as 5 is smaller than 13.(Fig 8)

Fig 8

• The next minimum value from edges of T,S,W,R is 5.
• Mark 5 and P.
• Add P to the set.(Fig 9)

Fig 9

• Replace value at Q by 2 and parent by P.(Fig 10)

Fig 10

• Mark 2 and vertex Q.
• Add Q to the set.(Fig 11)

Fig 11

Minimum spanning tree is obtained and shown in Fig 12 and cost of minimum spanning tree is obtained by adding weights of all edges i.e.

2+5+3+4+1 = 15

Fig 12

Short URL: http://tinyit.cc/ed088
July 17, 2014 |
Tags:

## Queues

Fig 3 : A Queue

Fig 2 : A Queue

Fig 1 : A Queue

Queues are the  data structure that stores data  in an ordered way.The  first element entered  is the  first one to be  removed.It is a  FIFO(First In First Out) data structure.The elements are added at one end called REAR end and removed from other end called as  FRONT end.

In Fig 2.FRONT =0 and REAR =4

Fig 2 : A Queue(FIFO)

## Array Representation of Queue

Queues can be represented by linear arrays.It has FRONT and REAR variables.FRONT points to the position from where deletion occurs and REAR points to the position where insertion occurs.

### Insertion in Queue

Before insertion,check whether the queue has the space to accommodate the new element .If the queue is full is and still insertion in tried then “OVERFLOW” condition arises and element does not get into queue.It is checked by condition if (REAR = MAX -1) where MAX is the maximum number of elements that a queue can hold.If yes,then OVERFLOW condition arises.

Program 1

```#include <stdio.h>

int main( )
{
int queue[10];
int max,num,i,item;
int front,rear;
//printf("Enter the size of queue");
scanf("%d",&max);
//printf("Enter the no of elements in queue");
scanf("%d",&num);
//printf("Enter the elements of queue");
printf("Queue before insertion : "); //Fig3
for(i=0;i<num;i++)
{
scanf("%d",&queue[i]);
printf(" %d\t",queue[i]);
}
printf("\n");
front = 0;
rear = num -1 ;
printf("Front end : %d\n",front);
printf("Rear end : %d\n",rear);
if (rear == max-1)
{
printf("Overflow");
}
else
{
//printf("Enter the item you want to insert \n");
scanf("%d",&item);
rear = rear + 1;
front = 0;
queue[rear] = item;
printf("Queue after insertion :");//Fig 4
for(i=0;i<=rear;i++)
{
printf(" %d\t",queue[i]);
}
printf("\n");
printf("Front end : %d\n",front);
printf("Rear end : %d\n",rear);
}
return 0;
}```

Say we want to insert 15 in Queue of  Fig 3.

Fig 3 : FRONT = 0
REAR = 4

REAR would get incremented by 1(as insertions are done at REAR end) and 15 is stored at value of  5th index(Fig 4).

Fig 4 : FRONT = 0
REAR =5

### Deletion in Queue

Before deleting an element check for “UNDERFLOW” condition.It occurs when we try to delete the element from an already empty queue.

If FRONT =-1 and REAR = -1 ,it means that there is no element in the queue and it is empty since index starts from 0.

If we want to delete element from the queue,then value of FRONT is incremented(Fig 6).Deletions are done at FRONT end only.

Program 2

```#include <stdio.h>
int main( )
{
int queue[10];
int max,num,i;
int front=0,rear;
//printf("Enter the size of queue");
scanf("%d",&max);
//printf("Enter the no of elements in queue");
scanf("%d",&num);
//printf("Enter the elements of queue");
printf("Queue before deletion : ");
for(i=0;i<num;i++)
{
scanf("%d",&queue[i]);
printf(" %d\t",queue[i]);
}
printf("\n");
front = 0;
rear = num -1 ;
printf("Front end : %d\n",front);
printf("Rear end : %d\n",rear);
if (front == -1 && rear == -1)
{
printf("Underflow");
}
else
{
front = front +1;
}
printf("Queue after deletion :");
for(i=front;i<=rear;i++)
{
printf(" %d\t",queue[i]);
}
printf("\n");
printf("Front end : %d\n",front);
printf("Rear end : %d\n",rear);
return 0;
}```

Say we want to delete 25 from the queue(Fig 5)

Fig 5 : FRONT = 0
REAR = 4

The value of FRONT in incremented t0 1 and 25 is deleted from the queue(Fig 6)

REAR =5

Short URL: http://tinyit.cc/044009
April 30, 2014 |
Tags: