Applications of Queue

Applications of Queue

AU: Dec.-19, Marks 15

There are various applications of queues such as,

1. Job Scheduling

• In the operating system various programs are getting executed.

• We will call these programs as jobs. In this process, some programs are in executing state.

• The state of these programs is called as 'running' state.

• Some programs which are not executing but they are in a position to get executed at any time such programs are in the 'ready' state.

• And there are certain programs which are neither in running state nor in ready state. Such programs are in a state called as 'blocked' state.

• The operating system maintains a queue of all such running state, ready state, blocked state programs. Thus use of queues help the operating system to schedule the jobs.

• The jobs which are in running state are removed after complete execution of each job, then the jobs which are in ready state change their state from ready to running and get entered in the queue for running state.

• Similarly the jobs which are in blocked state can change their state from blocked to ready state.

• These jobs then can be entered in the queue for ready state jobs.

• Thus every job changes its state and finally get executed. Refer Fig. 4.12.1.

• Thus queues are effectively used in the operating system for scheduling the jobs.

Categorizing Data

• The queue can be used to categorize the data.

• The typical example for categorizing the data is our college library.

• The college can have several departments such as Computer Engineering, Information Technology, Mechanical Engineering, Electronics Engineering and so on. The library has various sections in which the books from each stream are arranged.

• These sections are like multiple queues in which appropriate data (books) are stored. Thus categorization of data can be possible using multiple queues.

 

Ex. 4.12.1: There are 'N' numbers of balls in the box. The colors of the balls are red and blue. You are requested to stack the balls in the bottom sealed basket one by one. The order of placing the balls is two consecutive red balls followed by two consecutive blue balls. Later create two empty queues Q1 and Q2. Remove the last inserted balls from the basket and place it in Q1. Similarly remove the next inserted balls from the basket and insert it in Q2. Develop a program to repeat this process until the basket is empty and also print the color of the balls in both queues. AU: Dec.-19, Marks 15

Sol. :

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 25

/* stack structure*/

struct stack

{

char s[size];

int top;

}st;

struct queue

{

char que[size];

int front,rear;

}Q1, Q2;

int stfull()

{

if(st.top>=size - 1)

return 1;

else

return 0;

}

void push()

{

for(int i=0;i<2;i++)

{

st.top++;

st.s[st.top]='r';

}

for(int i=0;i<2;i++)

{

st.top++;

st.s[st.top]='b'; tex

}

printf("\n Balls are Pushed !!!");

}

int stempty()

{

if(st.top== -1)

return 1;

else

return 0;

}

char pop()

{

char item;

item=st.s[st.top];

st.top--;

printf("\n Ball is popped");

return(item);

}

void insert_Queue1 (char item)

{

printf("\n Inserting ball in Q1");

if(Q1.front == -1)

Q1.front++;

Q1.que[++Q1.rear] = item;

}

void insert_Queue2(char item)

{

printf("\n Inserting ball in Q2");

if(Q2.front == -1)

Q2.front++;

Q2.que[++Q2.rear] = item;

}

void display_queue(struct queue Q)

{

int i;

for(i=Q.front;i<=Q.rear;i++)

printf("%c",Q.que[i]);

}

void display_stack()

{

int i;

if(stempty())

printf("\n Stack Is Empty!");

else

{

for(i=st.top;i>=0;i - -)

printf("\n%c", st.s[i]);

}

}

int main(void)

{

int choice;

char ans,item;

st.top = -1;

Q1.front= -1;

Q1.rear= -1;

Q2.front= -1;

Q2.rear =1;

do

{

printf("\n Main Menu");

printf("\n1.Push the balls\n2.Pop\n3.exit");

printf("\n Enter Your Choice: ");

scanf("%d", &choice);

switch(choice)

{

case 1:if(stfull())

printf("\n Stack is Full!");

void display_queue(struct queue Q)

{

int i;

for(i=Q.front;i<=Q.rear;i++)

printf("%c",Q.que[i]);

}

void display_stack()

{

int i;

if(stempty())

printf("\n Stack Is Empty!");

else

{

for(i=st.top;i>=0;i — −)

printf("\n%c", st.s[i]);

}

}

int main(void)

{

int choice;

char ans,item;

st.top = -1;

Q1.front = -1;

Q1.rear = -1;

Q2.front = -1;

Q2.rear = -1;

do

{

printf("\n Main Menu");

printf("\n1.Push the balls\n2.Pop\n3.exit");

printf("\n Enter Your Choice: ");

scanf("%d", &choice);

switch(choice)

{

case 1:if(stfull())

printf("\n Stack is Full!");

else {

push();

display_stack();

}

break;

case 2:if(stempty())

printf("\n Empty stack!Underflow !!");

else

{

while(!stempty())

{

item=pop();

insert_Queue1(item);

item=pop();

insert_Queue2(item);

printf("\n Displaying Queue1...\n");

display_queue(Q1);

printf("\n Displaying Queue2...\n");

display_queue(Q2);

printf("\n----------------------\n");

}

}

display_stack();

break;

case 3:exit(0);

}

printf("\n Do You want To Continue? ");

ans=getche();

} while(ans == 'Y' || ans =='y');

getch();

return 0;

Output

Main Menu

1.Push the balls

2.Pop

3.exit

Enter Your Choice: 1

Balls are Pushed !!!!

b

b

r

r

Do You want To Continue? y

Main Menu

1.Push the balls

2.Pop

3.exit

Enter Your Choice: 2

Ball is popped

Inserting ball in Q1

Ball is popped og r

Inserting ball in Q2

Displaying Queue1...

b

Displaying Queue2...

b

------------------------

Ball is popped

Inserting ball in Q1

Ball is popped

Inserting ball in Q2

Displaying Queue1...

b r

Displaying Queue2...

b r

--------------------------

Stack Is Empty!