5 Queues – Introduction to Data Structures in C

Chapter 5

Queues

Chapter Outline

5.1 INTRODUCTION

A queue is one of the simplest data structures and can be implemented with different methods on a computer. Queue of tasks to be executed in a computer is analogous to the queue that we see in our daily life at various places. The theory of a queue is common to all. Queue of people in a bank, students queue in school, a travellers' queue for tickets at railway station are few examples of queue. It is necessary to wait in a queue for obtaining the service. In the same fashion, in a computer there may be a queue of tasks waiting for execution, few others for printing, and some are for inputting the data and instructions through the keyboard. Unless the task turns and comes on front, it will not be executed. This data structure is very useful in solving various real life problems. One can simulate the real life situations with this data structure. This chapter describes the queue and its types.

A queue is a non-primitive, linear data structure, and a sub-class of list data structure. It is an ordered, homogenous collection of elements in which elements are appended at one end called rear end and elements are deleted at other end called front end. The meaning of front is face side and rear means back side. The first entry in a queue to which the service is offered is to the element that is on front. After servicing, it is removed from the queue. The information is manipulated in the same sequence as it was collected. Queue follows the rule first-in-first- out (FIFO). Fig. 5.1 illustrates a queue.

Figure 5.1 Queue

Figure 5.1 shows that insertion of elements is done at the rear end and deletion at the front end.

Figure 5.2 Queues

The Fig. 5.2 illustrates the queue containing elements. The queue (Fig. 5.2(a)) contains four elements P, Q, R and S. The element P is at the front end and element S is at the rear end. In the Fig. (b), an element P has been deleted from the queue. Now, the element Q is the first element and it is on the front. In Fig. (c), element T is inserted from the rear end. Thus, the elements are inserted from the rear end of queue. The element T is inserted after S. As far as removal operation is concerned, the S is to be removed before T.

In other words, the service is provided to the element, which is at front and this element is to be removed first. We call this entry front of the queue. The entry of element that is recently added is done from rear of the queue or it can be called as tail end of the queue.

Two operations are frequently carried on queue. They are insertion and deletion of elements. These two operations depend upon the status of the queue. The insertion operation is possible, only when the queue contains elements less than the capacity it can hold. The deletion operation is only possible when the queue contains at least one element. The queue containing no elements is called underflow as shown in Fig. 5.3.

Figure 5.3 Empty queue (underflow)

5.2 VARIOUS POSITIONS OF QUEUES

Consider the following figures:

Figure 5.4(a) Empty queue

In Fig. 5.4(a) the queue is empty, hence value of rear = −1 and front = −1. The above queue is called as empty queue. Initially, the status of queue is always empty.

Figure 5.4 (b) One element in the queue

In Fig. 5.4(b), the queue holds one element. The value of rear = 0 and front = 0. Both front and rear end are on same element because the queue contains only one element. The next element appended will be stored followed by 5. Then, the front will remain at 5 but rear will be shifted on to the new element. The value of front is changed only once when the first element is inserted in the queue. Later, for every insertion of element, the front remains same but the value of rear changes.

Figure 5.4(c) Two elements in the queue

In Fig. 5.4(c), another element is inserted from the rear side and it is stored behind 5. Whenever we insert an element in the queue the value of rear is incremented, i.e. the rear end is shifted towards the right. At this step the value of front = 0 and rear = 1.

Figure 5.4(d) Three elements in the queue

In Fig. 5.4(d), the value of rear is 2.

Figure 5.4(e)

In Fig. 5.4 (e), one element is deleted from the queue. Now, the front is shifted towards bottom. Thus, the front will be on element 3 now. The value of the front will be increased when an element is removed. The value of front = 1 and rear = 2. The programs on above discussion are explained in queue implementation.

5.3 QUEUE IMPLEMENTATION

Queue can be put into operation in two ways:

  1. Static implementation (array)
  2. Dynamic implementation (pointers).

5.3.1 Static Implementation

The static implementation is done with an array. In this implementation, we should know the exact number of elements to be stored in the queue. The size of array is decided before execution at compile time. Once the array is declared, its size cannot be altered during the run time of the program. The beginning of the array, i.e. 0th element is the front and the last memory location will be rear of the queue. A queue can be created by declaring an array that hold the entries. Here, we should keep the track of both front as well as rear of the queue. Assume an array of integer data types as declared below.

int queue[8];

In the above statement, an array queue [] of integer type is declared.

From the Fig. 5.5 we can say that first six locations of a queue are filled and the remaining two are vacant. The element 5 is at front and 8 is at rear.

  1. If the value of front element is zero, then queue is empty.
  2. If the value of queue [8] is non-zero then the queue is full.
  3. When an element is inserted, the position of rear increases.
  4. When an element is deleted from the queue the value of front increases by one.

Figure 5.5 Queues

The above operation can be shown with few programs as described below. Consider the following program,

Example 5.1

Write a program to implement a queue using an array

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

main ()

{

int queue[8];

int rear=0;

clrscr();

while(1)

  {

printf ("Enter element: ");

scanf ("%d",&queue[rear]);

rear++;

if (rear==7)

{

printf ("\n Queue is full ");

break;

}

}

printf ("\n Elements of Queue are: ");

rear=0;

while (1)

{

printf (" %d ", queue[rear]);

rear++;

if (rear==7) break;

}

}

OUTPUT

Enter element: 1

Enter element: 2

Enter element: 3

Enter element: 4

Enter element: 5

Enter element: 6

Enter element: 7

Queue is full

Elements of Queue are: 1 2 3 4 5 6 7

Explanation This a simple example of queue. All the elements are entered and stored in the queue. Of course, the queue is implemented by declaring an array. The while loop and scanf () statement read elements through the keyboard. The variable rear is incremented to get successive position in the queue. In the same way, the second while loop displays the elements.

5.4 OPERATIONS ON QUEUES

Two operations can be carried out on queue.

5.4.1 Insertion of Element

 

Table 5.1 Algorithm for insertion in queue

Algorithm for Insertion of Element in a Queue
1.
Initialize front = 0 rear = −1, queue[SIZE] Initialization of queue
2.
If rear ≥ size
(Display queue overflow message and exit) Else
<enter element>
Test for overflow condition
3.
Queue[rear] = element
Rear++
Element is stored in an array
Rear is incremented
4.
Go to step 2 Loop rotated to beginning

A program based on algorithm, which is shown in Table 5.1, is described below.

Example 5.2

Write a program to insert elements in a queue.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

# define S 5

main ()

{

int queue[S];

int r=0,n;

clrscr();

while (1)

{

if (r>=S)

{

printf ("\n Queue overflow");

break;

}

else

printf ("Enter a number: ");

scanf ("%d",&n);

queue[r]=n;

r++;

}

printf ("\n Queue elements are: ");

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

printf (" %d ",queue[n]);

}

OUTPUT

Enter a number: 3

Enter a number: 4

Enter a number: 5

Enter a number: 6

Enter a number: 7

Queue overflow

Queue elements are: 3 4 5 6 7

Explanation This a simple example of queue that contains maximum 5 elements. All the elements are entered and stored in the queue. The queue is implemented by declaring array[s]. The while loop and scanf () statement read elements through the keyboard. The variable rear is incremented to get successive position in the queue. The for loop displays the elements.

Example 5.3

Write a program to perform insertion operation and show value of front and rear.

Solution

# include<stdio.h>

# include <conio.h>

main ()

{

int queue[7];

int r=−1,f=−1j;

clrscr();

 

while (r<6)

{

r++;

printf ("rear=%d front=%d Enter element:",r,f);

scanf ("%d",&queue[r]);

if (r==0 ) f=0;

}

printf ("\n Queue elements are: ");

for ( j=0;j<7;j++)

printf (" %d ",queue[j]);

}

OUTPUT

rear=−1 front=−1 Enter element:8

rear=0 front=0 Enter element:9

rear=1 front=0 Enter element:4

rear=2 front=0 Enter element:5

rear=3 front=0 Enter element:1

rear=4 front=0 Enter element:2

rear=5 front=0 Enter element:3

Queue elements are: 8 9 4 5 1 2 3

Explanation In this program our aim is to concentrate only at element insertion operation and the values of front and rear ends displayed after insertion of every element. Initially, rear and front are initialized to −1. Conceptually, it is not necessary to initialize these variables to −1. The user can also initialize them to zero. The values of rear start from −1 to 6. Here, −1 is the value before insertion operation. When one element is added the value of rear is increased to 1 and later the value reaches up to 6. On the other hand the value of front changes only once from −1 to 0 and then its value remains same.

5.4.2 Deletion of Element

The following program explains insertion and deletion operations.

Example 5.4

Write a program to perform deletion operation on queue and show value of front and rear.

Solution

# include<stdio.h>

# include <conio.h>

main ()

{

int queue[7]={11,12,13,14,15,16,17};

int i,r=6,f=0,n;

clrscr();

printf("\nThe Elements of queue are as follows:-\n");

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

printf("%2d ",queue[i]);

printf ("\nInitial values rear=%d front=%d",r,f);

printf ("\n\nHow many elements u want to delete: ");

scanf ("%d",&n);

while (f<n)

{

queue[f]=NULL;

f++;

printf ("\nrear=%d front=%d",r,f);

}

printf ("\n Queue elements are: ");

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

printf (" %d ",queue[n]);

}

OUTPUT

The Elements of queue are as follows:-

11 12 13 14 15 16 17

Initial values rear=6 front=0

How many elements u want to delete: 3

rear=6 front=1

rear=6 front=2

rear=6 front=3

Queue elements are: 0 0 0 14 15 16 17

Explanation This program is the second part of the first program. We have started exactly from where we ended the last program. The output of the last program is starting of this program. The array is initialized with entered values and rear and front are initialized to six and zero, respectively.

The user is asked to enter number of elements to be deleted. The loop is executed for n times and zero to n elements of the array are nullified. At every deletion operation the front is shifted to inside. It is shifted from 0 to 3 when three elements are deleted. The output of the program is easy to understand.

5.5 DISADVANTAGES OF SIMPLE QUEUES

In the previous sections we have studied implementation of queues using arrays and pointers. There are some disadvantages in simple queue implementation using arrays. In the following example, it is considered that the elements after deletion are not shifted to beginning of an array. Consider the following example:

Queue [5] is a simple queue declared. The queue is initially empty. In the following figures insertion and deletion operations will be performed.

The above figure is an empty queue. Initially the queue is always empty. Here, rear = −1 and front = −1. The user can also assign 0 instead of −1. However, the −1 is suitable because we are implementing this problem with arrays and an array element counting begins always with zero. Thus, it is suitable for problem logic.

In the above figure, one element is inserted. So, the new values of front and rear are increased and reaches to 0 (zero). This is the only stage where front and rear have same values.

In the above figure, two elements are appended in the queue. At this moment, the value of rear = 2 and front = 0.

In the above figure one element is deleted and the value of rear = 2 and f = 1. The value of front is increased due deletion of one element.

In the above figure, two more elements are appended to queue. The value of rear = 4 and front = 1.

If more elements are deleted, the value of front will be increased and as a result, the beginning portion of queue will be empty. In such a situation if we try to insert new elements to queue, no elements can be inserted in the queue. This is because, new elements are always inserted from the rear and if the last location of queue (rear) holds an element, even though the space is available at the beginning of queue, no elements will be inserted. The queue will be treated as overflow.

To overcome this problem, we have to update the queue. Let us take an example, suppose we have allocated n number of bytes to pointer using either malloc () (c) or new (c++) function. After successful allocation of memory (though the program is not utilizing the memory), memory will be part of the program and cannot be used by other program or cannot be allocated to other program. To utilize this memory, memory must be released using free or delete functions. Thus, whatever the portion of memory is not in use, can be used. In our example of queue the beginning portion of queue which is empty due to delete operations, can be filled by shifting following element to beginning of the array. Thus, the space will be available at the rear end and new elements can be inserted at the end. Thus, entire queue can be used to store the element. This approach also has a problem when the queue contains more elements. The solution to this problem is circular queue, which is discussed separately in this chapter.

Here, a program is provided with menu driven with different choices such as insertion, deletion, display, etc.

Example 5.5

Write a program to perform different operations with queue such as insert, delete and display of elements.

Solution

# include <stdio.h>

# include <conio.h>

int queue[8];

int r;

void insert(void);

void del ();

void show (void);

main ()

{

int c;

clrscr();

printf ("\n 1] Insert Element ");

printf ("\n 2] Delete Element ");

printf ("\n 3] Display element/s");

printf ("\n 4] Exit");

printf ("\n Enter your choice:- ");

scanf ("%d",&c);

switch (c)

{

case 1: insert(); break;

case 2: del(); show();break;

case 3: show(); break;

default: exit(0);

}

main ();

}

void insert ()

{

char ans='Y';

if (r>=7)

{

printf ("\n Queue is full \n\n\n");

main();

}

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

{

printf ("\n Enter element:- ");

scanf ("%d",&queue[r]);

if (r==7)

{

clrscr();

printf ("\n Queue is Full");

getch();

break;

}

else

r++;

printf ("\nContinue [Y/N]:-");

ans=getche();

}

}

void show()

{

int j;

for (j=0;j<r;j++)

printf (" %d ",queue[j]);

getch();

}

void del ()

{

int j;

if (r==0)

{

clrscr();

printf ("\n Queue is empty \n\n\n");

main();

}

for (j=0;j<r;j++)

queue[j]= queue[j+1];

queue[r]=0;

r--;

}

OUTPUT

1] Insert element

2] Delete element

3] Display element/s

4] Exit

Enter your choice:- 1

Enter element:- 23

Continue [Y/N]:-y

Enter element:- 45

Continue [Y/N]:-

Explanation In this program, the different tasks such as insert, delete and display of elements are performed using individual functions. A menu appears on the screen and user is required to enter choice. When user enters 1, the insert () function is executed. The integers entered by the user are stored in the queue one after another.

When the choice is 2, the element at the front is deleted. In queue, the elements are inserted from the rear side and deleted from the front side. The display option displays the elements presently stored in the queue. When del () function is executed, the element present at front is deleted. Here, the elements are shifted to front side. This is accomplished by the statement queue [j] = queue [j+1]; the next element is shifted to the previous location and the last element is replaced with zero.

In the above program, necessary care is taken to prevent overflow and underflow. When queue is full with the elements, a message will be displayed “Queue is Full” and further no elements can be added. When queue is empty user cannot delete any element. The function show () is used to display elements, this is achieved by using for loop and printf () statement.

Figure 5.6 Queues with elements

Figure 5.7 Queues (After delete operation)

Figure 5.8 Queue (After insert operation)

As shown in the Fig. 5.6, element 1 is at front side and seven is at rear side. When delete operation is performed one is deleted first and the element two is shifted at front as shown in the Fig. 5.7. When an element is inserted, it is inserted after seven as shown in the Fig. 5.8. When eight is inserted, it is inserted after seven. Consider another program that explains the operation insertion and deletion.

Example 5.6

Write a program to perform different operations with queue such as insert, delete and display of elements.

Solution

# include <stdio.h>

# include <process.h>

# include <conio.h>

create ();

void insert ();

void del();

void show ();

int m,n=10,fr=0, queue[11],re=0,num,cur;

main ()

{

int choice;

clrscr();

puts("1] Create");

puts("2] Insert");

puts("3] Delete");

puts("4] Show");

puts("5] End");

puts("\nEnter Your choice: ");

scanf("%d",&choice);

switch(choice)

{

case 1: create (); break;

case 2: insert (); break;

case 3: del (); break;

case 4: show(); break;

case 5: puts("Bye"); exit(0);

}

main();

}

create ()

{

puts ("Insert number of elements <11 in the queue: ");

scanf ("%d",&cur);

puts ("Enter elements: ");

if ( fr==0)

{

    fr++;

    scanf ("%d",&num);

    if (num==0) return 0;

    queue[fr]=num;

    re=fr;

}

do

{

++re;

if (re>cur) break;

scanf ("%d",&num);

if (num==0) break;

queue[re]=num;

}while(re<cur);

return 0;

}

void insert ()

{

if (re<cur)

{

puts ("Queue is full");

exit (0);

}

puts ("Enter a number to be inserted ");

scanf ("%d",&num);

queue[re]=num;

}

void del ()

{

if (fr==re)

{

puts("The queue is empty"); exit(0); }

fr++;

num=queue[fr];

if (fr==n)

{

    fr=1;

    re=1;

}

}

void show ()

{

for (m=fr;m<=re;++m)

printf (" %d ",queue[m]);

getch();

}

OUTPUT

1] Create

2] Insert

3] Delete

4] Show

5] End

Enter Your choice:

4

2 3 0

Explanation We are already familiar with the operation create, insert and delete in the previous program. In this program, separate functions are defined for different tasks such as create, insert, and delete operation. Now, we will discuss one by one.

In the create function, user has to enter number of elements to be entered in the queue. User also needs to enter elements. If zero is inserted the control exits from the function. The zero will not be considered as an element, it is entered to exit from the function. If elements entered are less than the capacity entered, the remaining portion remains vacant.

The insert () function is used to insert elements if the space is available. If the queue is already filled, this function will not work. The del () function is used to delete element. To display the element show () function is used. You might have noticed that the function main () is invoked recursively by itself. This is to enable the user to enter choice of operation.

5.6 DYNAMIC IMPLEMENTATION (POINTERS)

Dynamic implementation is carried out using pointers. By applying increment operation on pointer successive locations of memory can be accessed and an element can be stored in that location. Thus, the series of elements can be contiguously stored up to any number of elements. The programmer has to keep the starting address of the pointer in which first element is stored. Thus, in the same way the numbers can be viewed or altered. Here is the simple example.

Example 5.7

Write a program to implement queue using pointers.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

main ()

{

int *q;

int rear=0;

clrscr();

while(1)

{

printf ("Enter element: ");

scanf ("%d",q);

q++;

rear++;

if (rear==7)

{

printf ("\n Queue is full ");

break;

}

}

q=q-rear;

printf ("\n Elements of Queue are: ");

rear=0;

while (rear<7)

{

printf ("\n Element: %d rear=%d", *(q+rear),rear);

rear++;

}

}

OUTPUT

Enter element: 4

Enter element: 2

Enter element: 3

Enter element: 4

Enter element: 7

Enter element: 8

Enter element: 9

Queue is full

Elements of Queue are:

Element: 4 rear=0

Element: 2 rear=1

Element: 3 rear=2

Element: 4 rear=3

Element: 7 rear=4

Element: 8 rear=5

Element: 9 rear=6

Explanation In this program, pointer *q and integer rear are declared. The variable rear is initialized with zero. Using scanf (), statement elements are entered. In the while loop pointer q and rear are increased. If the rear reaches to seven, the break statement terminates the loop. After the execution of while loop, the pointer q points to last memory location of the queue. The starting address of the queue is again set by the statement q = q− rear. Finally, using second while loop and continuous increment operation with rear, successive memory locations are accessed and elements are displayed.

5.7 INSERTION AND DELETION OPERATION

The insertion and deletion operations can also be performed with the queue. The following program explains both the insertion and deletion operation with the queue. Queue implementation is done with an array.

Example 5.8

Write a program to perform insert and delete operation with queue.

Solution

# include <stdio.h>

# include <conio.h>

void create ();

insert ();

erase ();

void show ();

int kj=10,f=0, queue[11],r=0, e_ment, crn,s;

main ()

{

int option;

clrscr();

do

{

puts ("\n\n QUEUE OPERATIONS\n");

puts ("1: Create");

puts ("2: Insertion");

puts ("3: Erase");

puts ("4: Show");

puts ("5: Exit");

puts ("Enter your option: ");

scanf ("%d",&option);

switch(option)

{

    case 1: create (); continue;

    case 2: s=insert (); continue;

    case 3: erase(); continue;

    case 4: show (); continue;

    case 5:

    printf ("\n s=%d",s);

    return 0;

}

getche();

clrscr();

} while (option!=5);

}

void create ()

{

puts ("Insert number of elements<11 in the queue: ");

scanf ("%d",&crn);

puts("Enter elements: ");

if (f==0)

{

    f++;

    scanf ("%d",&e_ment);

    queue[f]=e_ment;

    r=f;

}

do

{

++r;

if(r>crn) break;

scanf ("%d",&e_ment);

queue[r]=e_ment;

} while(r<crn);

}

insert ()

{

r++;

if (r>j)

{

puts("Queue is full "); return (1); }

puts("Enter number to be inserted: ");

scanf ("%d",&e_ment);

queue[r]=e_ment;

return 0;

}

erase()

{

if ( f==r)

{

puts("The queue is empty "); return (0); }

f++;

e_ment=queue[f];

if (f==j)

{

f=1;

r=1;

}

return 0;

}

void show ()

{

for (k=f;k<=r;++k)

printf (" %d ",queue[k]);

}

OUTPUT

1 2 2 4 5

QUEUE OPERATIONS

1: Create

2: Insertion

3: Erase

4: Show

5: Exit

Enter your option:

4

1 2 2 4 5

Explanation In this program, required variables and function prototypes are declared before main (). The user can perform different operations and they are displayed. Program will ask the user to enter a choice. The option entered by user is passed to switch () case statement where appropriate case statement is executed. Actually, the case statement body invokes function and operation gets started.

The create function is used to insert numbers into the queue. In this function user has to enter number of elements to be inserted and followed by this user has to enter numbers. The if block is executed if the value off (front) is zero. The element entered is stored in the queue. Using while loop repeatedly elements are entered and stored in the queue. The variable r is incremented in every loop. The insert () function is used to insert an element at the given position in the queue. The variable j has value 10 and it shows maximum number which the queue can hold. If the value of r (rear) is greater than j its simple meaning is that queue is full and the return statement suspends the function execution. If the queue is empty and in the next available location, the entered element is stored.

In the erase () function, first value of r (rear) and f (front) are compared and if they are same its meaning is that queue is empty. Because value of front and rear are same means the queue has no element. If f and j (maximum number) are same, both these variables are set to one.

The show() function is used to display the element as output. The loop is executed from value of front variable to rear. In the erase () function, the elements are not actually erased, just position of front is increased. The same value of front is used to display the elements. Before the fth position, the elements exist physically. We can also erase them physically, but then we have to move the elements to the beginning of the array.

5.8 TYPES OF QUEUES

In the last few topics, we have studied simple queue and already seen the disadvantages. When rear pointer reaches to the end of the queue (array), no more elements can be added in the queue, even if beginning memory locations of array are empty. To overcome the above disadvantage, different types of queues can be applied. Different types of queues are:

5.8.1 Circular Queue

The simple or in a straight line queue there are several limitations we know, even if memory locations at the beginning of queue are available, elements cannot be inserted as shown in the Fig. 5.9. We can efficiently utilize the space available of straight-line queue by using circular queue.

Figure 5.9 Simple queues with empty spaces

In the above discussion, it is supposed that front is not shifted to the beginning of the queue. As shown in the Fig. 5.10 a circular queue is like a wheel or a perfect ring. Suppose, c [4] is an array declared for implementation of circular queue. However, logically elements appear in circular fashion but physically in computer memory, they are stored in successive memory locations.

Figure 5.10 Circular queue

In the circular queue, the first element is stored immediately after last element. If last location of the queue is occupied, the new element is inserted at the first memory location of queue implementing an array (queue). For example, C[n], C is queue of n elements. After inserting, storing an element in the last memory location [(n−1th) element], the next element will be stored at the first location, if space is available. It is like a chain of where starting and ending points are joined and a circle is formed. When an element is stored in the last location wrapping takes place and element inserting routine of the program pointed to beginning of the queue.

Recall that a pointer (stack and queue pointer) plays an important role to know the position of the elements in the stack and queue. Here, as soon as last element is filled, the pointer is wrapped to the beginning of the queue by shifting the pointer value to one.

A circular queue overcomes the limitation of the simple queue by utilizing the entire space of the queue. Like a simple queue, the circular queue also have front and rear ends. The rear and front ends help us to know the status of the queue after the insertion and deletion operations. In the circular queue implementation, the element shifting operation of queue that we apply in the simple queue is not required. The pointer itself takes care to move at vacant location of the queue and element is placed at that location. In order to simulate the circular queue a programmer should follow the following points:

  1. The front end of the queue always points to the first element of the queue.
  2. If the values of front and queue are equal, the queue is empty. The values of front and rear pointers are only increased / decreased after insertion/deletion operation.
  3. Like simple queue, rear pointer is incremented by one when a new element is inserted and front pointer is incremented by one when an element is deleted.

Insertion

Figure 5.11(a) Insertion in a queue

As per Fig. 5.11(a), the insertion of an element in a queue will be same as in a linear queue. The programmer must have to trace the values of front and rear variables.

In Fig. 5.11 (a), only two elements are there in the queue. If we continue to add elements, the queue would be as shown in Fig. 5.11 (b). The new element is always inserted from the rear end. The position where the next element is to be placed can be calculated by the following formula.

REAR = (1+REAR) % MAXSIZE

C[REAR] = NUMBER

Figure 5.11(b) Full queue

From the Fig. 5.11(b), the value of rear is three and the capacity to store maximum element of queue is four. Therefore,

REAR = (1+REAR) % MAXSIZE

REAR = (1+3)%4

REAR = 4%4 = 0.

The operator % is modular divisor operator and returns remainder. Thus, in the above equation the remainder obtained is zero. The value of front as well as rear is zero, it means stack is full. Any attempt to insert new element will display the “queue full” message.

Consider, the following Fig. 5.11 (c),

Figure 5.11(c) Circular queue

Example 5.9

Write a program to perform insert, delete operations with circular queue and display elements.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

int queue[8];int r,f=0,x=0;

void insert(void);

void del ();

void show (void);

main ()

{

 int c;

 clrscr();

 printf ("\n 1] Insert Element ");

 printf ("\n 2] Delete Element ");

 printf ("\n 3] Display element");

 printf ("\n 4] Exit");

 printf ("\n Enter your choice: ");

 scanf ("%d",&c);

switch (c)

{

 case 1: insert(); break;

 case 2: del(); show();break;

 case 3: show(); break;

 default: exit(0);

}

  main ();

  }

  void insert ()

  {

  int n;

  char ch,ans='Y';

  if (r>=7)

  {

 while (queue[x]==0)

 {

  printf ("\n Enter a Number: ");

  scanf ("%d",&n);

  queue[x]=n;

  x++;

  puts("\n Continue Y/N: ");

  ch=getch();

  if (ch!='Y') break;

 }

printf ("\n Queue is full \n\n\n");

main();

}

printf ("\n Enter elements: ");

while (ans=='Y')

{

scanf ("%d",&queue[r]);

if (r==7)

{

clrscr();

printf ("\n Queue is Full");

getch();

break;

}

else

r++;

printf ("\n Continue Y/N: ");

ans=getche();

}

}

void show()

{

int j;

for (j=0;j<8;j++)

printf (" %d ",queue[j]);

getch();

}

void del ()

{

int j;

if (r==0)

{

clrscr();

printf ("\n Queue is empty \n\n\n");

main();

}

if (f==8) f=0;

queue[f]=0;

f++;

}

OUTPUT

1] Insert Element

2] Delete Element

3] Display element

4] Exit

Enter your choice: 2

0 2 0 0 0 0 0 0

Explanation In this program, various operations such as insert, delete and display are performed. When an insert operation is performed and elements are inserted, elements appear one after another in sequence. If we remove element, the beginning location remains empty. If the last location holds an element and if insertion request is made by the user, the new element inserted is stored at the starting location. If we go on continuously performing remove operation, the elements at the beginning are not removed first (see Fig. 5.12).

Figure 5.12 Circular queue (before deletion)

In the above program, assume the elements inserted are 1,2,3,4,5 and 6 and consider their position in the array is from 0th to 5th. The status of the queue is full. If we keep on removing elements, the elements would be removed one by one. On deletion of element of the 0th location, this location remains empty. Now, if an element is inserted, suppose seven, it will be stored in the 0th location as in Fig. 5.13.

Due to circular queue mechanism, if last location is occupied and the beginning locations are empty, the element is inserted at the empty location. If we keep on removing elements, the elements will be removed in the order from 2,3,4,5,6 and 7. However, the seven is stored at 0th location of the array but it was the last element inserted.

5.8.2 Double Ended Queues

Till now, we have studied stack and queue. The stack has only one end and can be used alternately to insert and delete elements. On the other hand, the double-ended queue has two ends, front and rear. The front end is used to remove element and rear end is used to insert elements. Here, in the double-ended queues, insertion and deletion can be performed from both the ends and therefore, it is called as double-ended queue and in short deque. It is a homogenous list of elements. The deque is a general representation of both stack and queue and can be used as stack and queue. There are various methods to implement deque. Linked list and array can be used to perform the deque. The array implementation is easy and straightforward.

Figure 5.13 Circular queue (after deletion and insertion)

Consider the following Fig. 5.14:

Figure 5.14 Deque

In deque, it is necessary to fix the type of operation to be performed on front and rear ends. The deque can be classified into two types:

Input Restricted Deque In the input restricted deque, insertion and deletion operation are performed at rear end whereas only deletion operation is performed at front end. The Fig. 5.15 represents the input restricted deque.

The following operations are possible in the input restricted deque:

  1. Insertion of an element at the rear end.
  2. Deletion of element at both front and rear ends.

Figure 5.15 Input restricted deque

Thus, input restricted deque allows insertion at one and deletion at both ends.

Example 5.10

Write a program to demonstrate input restricted deque.

Solution

# include <stdio.h>

# include <conio.h>

int ird[5];

main ()

{

int r=0,c=1,op,f=−1;

int insert(int);

void deleter(int,int);

void deletef(int,int);

void show(void);

while (1)

{

clrscr();

printf ("\n (1) Insert ");

printf ("\n (2) Delete from rear");

printf ("\n (3) Delete from front");

printf ("\n (4) Display ");

printf ("\n (0) Exit");

printf ("\n Enter Your choice:- ");

scanf ("%d",&op);

switch(op)

{

case 1: while (c && r<5)

{

c=insert(r);

r++;

}

if (c==0 )

{

c=1;

r−−;

}

else

if (f<0)

printf ("\n Deque is full ");

getch();

break;

case 2: deleter(−r,f);break;

case 3: deletef(r,++f); break;

case 4: show (); break;

default: exit(0);

}

}

}

void show ()

{

int j;

printf ("\n Elements of deque are: ");

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

printf (" %d ",ird[j]);

getche();

}

int insert (int h)

{

int k;

printf ("\n Enter an element (enter 0 to exit): ");

scanf ("%d",&k);

ird[h]=k;

return (k);

}

void deleter(int m,int n)

{

if(m<=n)

printf("Deque is empty");

else

{

printf ("\n %d The element deleted: %d",m,ird[m]);

ird[m]=0;

}

getch();

}

void deletef(int f,int j)

{

if(f<j)

printf("Deque is empty");

else

{

printf("\n %d The element deleted:- %d"j,ird[j]);

ird[f]=NULL;

}

getch();

}

OUTPUT:

(1) Insert

(2) Delete from rear

(3) Delete from front

(4) Display

(0) Exit

Enter Your choice:- 1

Enter an element (enter 0 to exit): 2

Enter an element (enter 0 to exit): 3

Enter an element (enter 0 to exit): 5

Enter an element (enter 0 to exit): 8

Enter an element (enter 0 to exit): 6

Deque is full

(1) Insert

(2) Delete from rear

(3) Delete from front

(4) Display

(0) Exit

Enter Your choice:- 4

Elements of deque are: 2 3 5 8 6

Explanation The output of the program is not fully displayed here. User can see it by executing it. Recall that in input restricted queue, insertion can be done only from rear end and it is carried out by the function insert (). The while loop is executed for continuous execution of the insert () function. User can enter element and when zero is entered, the loop is terminated. Thus, insertion of elements is carried out. The variable r (rear) is incremented and its value should not exceed the maximum capacity of the array, i.e. 5 and the same is done in the while loop condition.

We have a choice to remove the elements. We can remove elements from both the ends. If we go for second choice, elements from rear side are removed. The variable r (rear) is decremented and the rth element of the deque is erased. This option has a side effect. The empty locations generated by the deletion operation can be filled using insertion operation. However, if we go for option 3 the case is different. In this case, the elements are deleted from front and vacant space is created at the beginning of the deque. If we want to insert the element in that place, the insert option will fail here. This is because it is programmed in circular fashion. This is the drawback of input restricted deque.

Output Restricted Deque In the output restricted deque insertion of an element can be done at both front and rear end and deletion operation can be done only at front end. The output restricted deque is shown in Fig. 5.16.

Figure 5.16 Output restricted deque

The following operations are possible in the output restricted deque:

  1. Insertion at both front and rear end.
  2. Deletion at only front end.

An example to demonstrate output restricted deque is illustrated below.

Example 5.11

Write a program to demonstrate output restricted deque

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

int ird[5];

main ()

{

int r=0,c=1,op,f=−1;

int insertr(int);

int insertf(int);

void deletef(int);

void show(void);

clrscr();

while (1)

{

printf ("\n 1 Insert from rear: ");

printf ("\n 2 Insert from front");

printf ("\n 3 Delete from front");

printf ("\n 4 Display ");

printf ("\n 0 Exit");

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

scanf ("%d",&op);

switch(op)

{

case 1:

    while (c && r<5)

    {

    c=insertr(r);

    r++;

    }

    if (c==0 )

    {

    c=1;

    r−;

    }

    else if (f<0)

    printf ("\n Deque is full ");

    getch();

    break;

case 2: f=insertf(f); break;

case 3: deletef(++f); break;

case 4: show (); break;

default: exit(0);

}

}

}

void show ()

{

int j;

printf ("\n Elements of deque are: ");

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

printf (" %d ",ird[j]);

getche();

}

int insertr (int h)

{

int k;

printf ("\n Enter a Element (enter 0 to exit): ")

scanf ("%d",&k);

ird[h]=k;

return (k);

}

int insertf(int m)

{

int h;

if (ird[m]==0 && m>=0)

{

printf ("\n Enter a element: ");

scanf ("%d",&h);

ird[m]=h;

}

else

printf ("\n no space available ");

return −−m;

}

void deletef(int f) { ird[f]=NULL; }

OUTPUT

1 Insert from rear:

2 insert from front

3 Delete from front

4 Display

0 Exit

Enter Your choice: 1

Enter a Element (enter 0 to exit): 1

Enter a Element (enter 0 to exit): 2

Enter a Element (enter 0 to exit): 3

Enter a Element (enter 0 to exit): 0

1 Insert from rear:

2 insert from front

3 Delete from front

4 Display

0 Exit

Enter Your choice: 4

Elements of deque are: 1 2 3 0 0

Explanation In the output restricted queue, insertion can be done at both the ends and deletion can be done only at front end. The deletion procedure is same as the last program. In addition, insertion from rear end follows the same instruction as described in the previous program. The newly introduced function is insertf (), which performs insertion of elements from front of the deque. First, the space availability is checked. If space is available and request is made, the user has to insert the element and the same is stored in the empty location. The variable f is decremented. This is because while performing deletion operation the front is shifted forward and to reverse it, the value of f is decremented.

5.8.3 Priority Queues

We know that queue is based on the technique first come first out (FIFO). The element inserted first will be deleted first. A priority queue is another type of queue. Here, the priority is determined according to the position of the queue, which is to be entered. Various real life problems are based on priority queues. For example, in the buses few seats are reserved for ladies and handicapped; if a company is providing any scheme, the employees of the same company are given second priority.

Priority queue is a data structure in which prioritized insertion and deletion operations on elements can be performed according to their priority values.

There are two types of priority queues:

Ascending Priority Queue In this queue elements can be inserted randomly. The smallest element of the queue is deleted first.

Example 5.12

Write a program to create ascending priority queue. Insert and remove the element.

Solution

# include <stdio.h>

# include <conio.h>

 

int prq[5]={0};

int insert();

void remove1();

void show();

main()

{

int j,c=1;

while (c!=0)

{

clrscr();

printf ("\n 1. Insert");

printf ("\n 2. Remove");

printf ("\n 3. Display");

printf ("\n 0. Exit");

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

scanf ("%d",&c);

switch(c)

{

case 1: insert(); break;

case 2: remove1(); break;

case 3: show(); break;

default: exit(0);

}

}

}

int insert()

{

int nj;

printf ("\n Enter the position: ");

scanf ("%d",&n);

n−−;

if (n>4 || prq[n]!=0 )

{

printf ("\n Location is not available");

return 0;

}

printf ("\n Enter Element: ");

scanf ("%d",&j);

prq[n]=j;

return 0;

}

void remove1()

{

int j,k,min=0,s=0;

for (j=0;j<=4;j++)

s=s+prq[j];

for (j=s;j>0;j−−)

{

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

{

if (j==prq[k])

min=prq[k];

}

}

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

{

if (prq[j]==min)

{

prq[j]=0;

break;

}

}

}

void show()

{ int h;

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

printf (" %d ",prq[h]);

getch();

}

OUTPUT

1. Insert

2. Remove

3. Display

0. Exit

Enter Your choice: 1

Enter the position: 1

Enter Element: 3

Explanation In this program an array prq [] is defined. The array prq[] is used to implement priority queue. The insert () function is used to insert an element in the queue. The position and element number are to be provided by the user. According to user entered values, the process is executed. User can randomly insert position numbers from 1 to 5. If the user repeats the same location number in which the element is already stored, the insertion will be terminated. The replacement of element is not allowed here. If the location is empty then only insertion of element is possible.

The show () function is used to display elements only. The remove1() function is used to remove the element. Before the removal of an element, it must be sorted first (in ascending or descending order). We know that in ascending order queue, the smallest element is deleted first. Hence, instead of arranging all the elements of the queue in ascending order, here the smallest element of the queue is searched and it is removed. In the priority queue, we can insert an element anywhere in the queue. Hence, it may not be compulsory to arrange the numbers in ascending order. If we arrange the elements in ascending order and then begin the removal operation, it will also change the exact position of the element. The user can also implement this program by sorting the queue elements, storing elements temporarily and then the smallest element can be erased. The program for descending priority queue can be done in the same fashion.

Descending Priority Queue In this queue also, elements can be inserted randomly but the largest element is deleted first.

Example 5.13

Write a program to create descending priority queue. Insert and remove the element.

Solution

# include <stdio.h>

# include <conio.h>

int prq[5]={0};

int insert (void);

void remove1(void);

void show (void);

main ()

{

int j,c=1;

clrscr();

while (c!=0)

{

printf ("\n 1. Insert");

printf ("\n 2. Remove");

printf ("\n 3. Display");

printf ("\n 0. Exit");

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

scanf ("%d",&c);

switch(c)

{

case 1: insert(); break;

case 2: remove1 (); break;

case 3: show (); break;

}

}

}

int insert ()

{

int nj;

printf ("\n Enter the position: ");

scanf ("%d",&n);

n−−;

if (n>4 || prq[n]!=0 )

{

printf ("\n Location is not avaliable");

return 0;

}

printf ("\n Enter Element: ");

scanf ("%d",&j);

prq[n]=j;

return 0;

}

void remove1 ()

{

int j,k,max=0,s=0;

for (j=0;j<=4;j++)

s=s+prq[j];

for (j=0;j<s;j++)

{

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

{

if (j==prq[k]) max=prq[k];

}

}

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

{

if (prq[j]==max)

{

    prq[j]=0;

    break;

}

}

}

void show ()

{

int h;

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

printf (" %d ",prq[h]);

}

OUTPUT

1. Insert

2. Remove

3. Display

0. Exit

Enter Your choice: 3

8 3 1 10 9

1. Insert

2. Remove

3. Display

0. Exit

Enter Your choice: 2

1. Insert

2. Remove

3. Display

0. Exit

Enter Your choice: 3

8 3 1 0 9

Explanation This program is same as previous one. Here, only the largest element is deleted first. It is an example of descending order queue.

In both the above types, if elements with equal priority are present, the FIFO technique is applied. In case the queue elements are sorted, the deletion of an element will be quick and easy because elements will appear either in ascending or descending order. However, the insertion operation will be easier said than done because empty locations will have to be searched and only then elements can be placed at that location.

In case the queue elements are not in order, i.e. not sorted, insertion operation will be quick and easy. However, the deletion operation will take place after the priority value set.

Therefore, we can say that in both the above types insertion operation can be carried out easily. However, the deletion operation, which is, based on certain priority, i.e. the smallest or largest is first searched out and later it is removed from the queue. The locations of that element do not matter. In stack and queues deletion operation is performed at the ends. Conceptually, there is no provision for deleting an element, which is neither first nor last element of the list.

In the above program, we have not arranged the elements in an ascending or descending order. Just smallest or largest element is searched and erased.

In deletion operation the element may not be physically removed from the queue and it can be kept inaccessible in the program. Alternatively, special character called empty indicator such as #, $ can be placed at that place. Both the insertion and deletion operation perform scanning of the queue elements. While performing deletion operation the element must be deleted physically. It is possible to make its access denied. However, for other computation operation, the element logically deleted but physically existing will be taken into account and will change the result. So, for sure result, the element must be removed.

The elements of the queue can be number, character or any complex object which is a composition of one or more basic data types.

In priority queue every element has been assigned with a priority value called priority. The elements can be inserted or deleted randomly anywhere in the queue. Consider the following points of queue:

  1. An element of upper priority is processed prior to an element of lower priority.
  2. If two elements have the same priority, they are processed depending on the order they are inserted in the queue, i.e. FIFO.

Figure 5.17 Priority queue

As shown in Fig. 5.17, the element 7 is deleted first. However, the element 1 is nearer to the front as compared to 7, but 7’s priority value is nine, which is higher, and hence it is deleted first. Though the queue is based on FIFO technique, the priority queue is not based on FIFO operation firmly. A program on priority queue is provided below for detailed understanding.

Example 5.14

Write a program to demonstrate priority queue. Enter number and priority value. Perform insert and deletion operation.

Solution

#include<stdio.h>

#include <conio.h>

int pq[2][5]={0};

main ()

{

int c=1;

int insert (void);

void show(void);

void remove1(void);

clrscr();

do

{

printf ("\n1 Insert ");

printf ("\n2 Remove ");

printf ("\n3 Display");

printf ("\n0 Exit");

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

scanf ("%d",&c);

switch(c)

{

case 1: insert (); break;

case 2: remove1(); break;

case 3: show(); break;

case 0: c=0;

}

}

while (c!=0);

}

int insert ()

{

int p,e,r;

printf ("\n Position: ");

scanf ("%d",&p);

if (p>5 || p<0)

{

printf ("\n Invalid Argument ");

return 0;

}

p−−;

printf ("\n Element: ");

scanf ("%d",&e);

if (pq[0][p]==0)

pq[0][p]=e;

printf ("\n Priority: ");

scanf ("%d",&r);

pq[1][p]=r;

return 0;

}

void show ()

{

int j,k;

for (j=0;j<2;j++)

{

if (j==0)

printf ("\n Elements: ");

else

printf ("\n Priority: ");

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

printf (" %d ",pq[j][k]);

printf ("\n");

}

}

void remove1 ()

{

int j,maxp=0;

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

{

if (pq[1][j]>maxp)

maxp=pq[1][j];

}

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

{

if (pq[1][j]==maxp)

{

pq[0][j]=pq[1][j]=0;

break;

}

}

}

OUTPUT

Elements: 1 2 8 9 4

Priority: 1 3 9 8 3

1 Insert

2 Remove

3 Display

0 Exit

Enter Your Choice: 2

1 Insert

2 Remove

3 Display

0 Exit

Enter Your Choice: 3

Elements: 1 2 0 9 4

Priority: 1 3 0 8 3

Explanation This program is the same as the last few programs. Here, in this program two-dimensional array is defined. Using insert function, elements position number, element and its priority value are entered. Replacement of element is not allowed. When remove function is executed, the element with higher priority is detected and removed. The show () function is used to display the elements and priority value.

5.9 APPLICATIONS OF QUEUES

There are various applications of computer science, which are performed using data structure queue. This data structure is usually used in simulation, various features of operating system, multiprogramming platform systems and different type of scheduling algorithm are implemented using queues. Round robin technique is implemented using queues. Printer server routines, various applications software are also based on queue data structure.

5.9.1 Round Robin Algorithm

Round Robin (RR) algorithm is an important scheduling algorithm. It is used especially for the time-sharing system. The circular queue is used to implement such algorithms.

For example, there are N procedures or tasks such as P1, P2, P3PN. All these tasks are to be executed by the central processing unit (CPU) of the computer system. The execution times of the tasks or processes are different. The tasks are executed in sequence P1, P2, P3 and PN.

In time, sharing mode the tasks are executed one by one. The algorithm forms a small unit of time, say, from 10 to 100 milliseconds for each task. This time is called time slice or time quantum of a task. The CPU executes tasks from P1 to PN allocating fixed amount of time for each process. On allocating time to all tasks, CPU resumes the first task. That is, when all tasks are completed, it returns to P1. In the time-sharing system, if any task is completed before the estimated time, the next task is taken up for execution immediately. Consider the following table:

Tasks Expiry Time (Units)
P1
10
P2
19
P3
8
P4
5

There are total four tasks and the total time to complete all the tasks would be (10+19+8+5) 42 units. Suppose, the time slice is of 7 minutes. The RR scheduling for the above case would be

In the first pass each task takes seven units of time-task P4 is executed in the first pass whereas task P1, P2, P3 requires more than 7 units of time. Hence, in the second round task P1 and P3 are executed. At last, P2 is executed.

5.9.2 Simulation

It is an extremely powerful tool used for experimentation purpose. Without performing real experiments simulation permits to take the results and if necessary modification can be done as per expected results. One of the standard applications of queue can be implemented with simulation. Simulation is a method of managing a theoretical illustration of a real life problem with the purpose of understanding the effect of modification, concern factors and implementing some approaches to get reliable solution. The main goal of simulation is to help the user or to guess for obtaining the output of the program after implementing some approaches. It permits the user to make several trials for getting the actual results and planned situations without disturbing the real situation.

There are few disadvantages in the simulation. Lengthy simulation creates execution overhead on computer. For solving a real life problem, various assumptions are made to find out the key solution. If the assumption is straightforward, the outcome will be less reliable. In contrast, if the assumption is having more particulars, the outcome will be reliable and better. If the primary assumptions are wrong, even though, the program source code is given in detail, the guess obtained will be incorrect. In this situation, the program developed becomes futile.

5.10 TYPES OF SYSTEMS

A system may be isolated or continuous. The continuous system has some arguments, which can receive any real value in some gaps. Simulation of this system runs on these continuous arguments. In the discrete system, the method is different, it takes only selected set of values. The moving of a fan at home is a discrete system and its speed can be controlled. The motion of earth or sun is an example of continuous system and its motion is out of our control. The input and output parameters also defines system. The system can be either deterministic or stochastic. The input and output parameters also have a relationship. The various systems are descried in Fig. 5.18.

Deterministic System In this case if input values and initial state are available the result can be determined.

Stochastic System This system necessitates efforts for simulation. There is no standard clarification for this system.

Figure 5.18 Types of systems

To simulate a system a model is formed. It is a body of detailed particulars and applied to represent the system in various forms. There are various models as event-driven, simulation and time-simulation model and selection of model depends upon particulars of information available. The first step in solving the problem is selecting structure of model because the model indicates the system and it is easier than the problem. The model should be restricted and should not provide information out of the system. To facilitate the formation of model for a state, the characteristics, entities, activities and operations of the system must be determined. Activity refers to change of system state. The entities indicate the mechanism of the system and serves as an object in the simulation. The objects have characteristics. The characteristics of objects denote the state of the system and association between various entities at that particular movement. The program must execute given steps and activities (change of state) must occur in sequence.

Summary
  1. A queue is a non-primitive, linear data structure and a sub-class of list data structure. It is an ordered, homogenous collection of elements in which elements are appended at one end called rear end and elements are deleted at other end called front end.
  2. The static implementation means the array implementation. In this implementation, we should be assured about the number of elements we want to have in the queue.
  3. Two operations can be carried out on queue:
    1. insertion of element
    2. deletion of element.
  4. Dynamic implementation is carried out using pointers. By applying increment, operation on pointer successive locations of memory can be accessed and an element can be stored in that location.
  5. There are three types of queue, i.e. circular queue, deque and priority queue.
  6. In the circular queue, the first element is stored immediately after last element. If last location of the queue is occupied then the new element is inserted at the first memory location of queue implementing array (queue).
  7. In the double-ended queue, insertion and deletion can be performed from both the ends and therefore, it is called double-ended queues and in short called deque. It is a homogenous list of elements.
  8. In the input restricted deque, insertion and deletion operation are performed at rear end whereas only deletion operation is performed at front end.
  9. In the output restricted deque, insertion of an element can be done at both front and rear end and deletion operation can be done at only front end.
  10. Priority queue is a data structure in which prioritized insertion and deletion operations on elements can be performed according to their priority value.
  11. Ascending priority queue: In this, queue elements can be inserted randomly. The smallest element of the queue is deleted first.
  12. Descending priority queue: In this queue also, elements can be inserted randomly and the largest element is deleted first.
  13. Simulation is a method of organizing a theoretical representation of a real life problem with the purpose of understanding the effect of alteration, concern factors and implementing some approaches to get reliable solution.
Exercises
  1. Answer the following questions:
    1. What is queue? Explain it with real life examples.
    2. Explain the terms front and rear with relevance to queue. Which operations are to be performed at these ends?
    3. Explain different types of queues.
    4. How is implementation of queue done?
    5. What are the limitations of simple queue?
    6. Explain the insertion and deletion operations of queue.
    7. Differentiate between simple and circular queues.
    8. Differentiate between stack and queue.
    9. Distinguish between FIFO and LIFO.
    10. Give the definition of priority queue. Explain its types.
    11. Explain types of deque.
    12. Explain types of priority queues.
    13. Explain system and types of systems.
  2. Attempt the following programs:
    1. Write a program to insert and display the eight alphabetic characters in a queue.
    2. Write a program to declare a priority queue using two-dimensional array, store elements and priority. Display the elements according to priority from higher to lower.
    3. Write a program to implement circular queue with the pointers.
    4. Write a program to insert and display the elements of deque, with the array and pointers.
    5. Write a program to insert five elements in the ascending priority queue. Sort the elements in ascending order. Perform the deletion operation and shift the empty location at the end of array.
    6. Write a program to create a priority queue. Store element and priority value. Assume square root of entered number as its priority value. Insert and delete the elements.
    7. Write a program to implement a circular queue containing eight elements and perform the insertion and deletion operation.
  3. Select the appropriate option for each of the following questions:
    1. Queue follows the rule
      1. FIFO
      2. LIFO
      3. LILO
      4. FILO.
    2. The rear end of the queue is used
      1. to insert an element
      2. to remove an element
      3. both (a) and (b)
      4. none of the above.
    3. The front end of the queue is used
      1. to insert an element
      2. both (a) and (b)
      3. to remove an element
      4. none of the above.
    4. When an element is inserted in queue, the position of rear
      1. increases
      2. remains constant
      3. decreased
      4. none of the above.
    5. When an element is inserted in queue, the position of front
      1. increments
      2. unchanged
      3. decrements
      4. none of the above.
    6. Which one of the following is not a type of queue?
      1. output restricted deque
      2. deque
      3. circular queue
      4. priority queue.
    7. In this queue elements can be inserted randomly
      1. priority queue
      2. simple queue
      3. circular queue
      4. none of the above.
    8. In the input restricted queue
      1. deletion of element at both front and rear ends is done
      2. insertion of element at both front and rear ends is done
      3. deletion at only front end
      4. all of the above.
    9. In this queue, smallest element of the queue is deleted first.
      1. ascending priority queue
      2. descending priority queue
      3. circular queue
      4. simple queue.
    10. When the circular queue is full, and if one element is removed the next inserted element is stored at
      1. first location
      2. last location
      3. intermediate location
      4. none of the above.
  4. Find the output
    1. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int que[8];

      int r=0;

      clrscr();

      while(r<7)

      {

      printf ("Enter element: ");

      scanf ("%d",&que[r]);

      r++;

      }

      printf ("\n Elements of Queue are: ");

      r=0;

      while (r<7)

      {

      printf (" %d ", que[r]);

      r++;

      }

      }

    2. # include<stdio.h>

      # include <conio.h>

      main ()

      {

      int q[7];

      int r=0,f=0j;

      clrscr();

      while (r<6)

      {

      printf ("rear=%d front=%d Enter element:",r,f);

      scanf ("%d",&q[r]);

      r++;

      }

      printf ("\n Queue elements are: ");

      for (j=0;j<6;j++)

      printf (" %d ",q[j]);

      }

    3. # include<stdio.h>

      # include <conio.h>

      main ()

      {

      int q[7];

      int r=0,f=0j;

      char ch;

      clrscr();

      while (r<6)

      {

      printf ("rear=%d front=%d Enter element:",r,f);

      scanf ("%d",&q[r]);

      r++;

      }

      printf ("\nQueue elements are: ");

      for (j=0;j<6;j++)

      printf (" %d ",q[j]);

      printf("\nWould you like to delete one element

      from queue?[Y/N]:-");

      scanf("%s",&ch);

      if(ch=='y'||ch=='Y')

      {

      q[f]=0;

      f++;

      printf ("\nAfter deletion of one element

      rear=%d front=%d\n ",r,f);

      printf("\nQueue elements are:- ");

      for (j=f;j<6;j++)

      printf (" %d ",q[j]);

          }

      }

    4. # include<stdio.h>

      # include <conio.h>

      main ()

      {

      int q[6];

      int i,r=6,f=0,n;

      clrscr();

      printf("Enter the seven elements of a queue:- ");

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

      scanf("%d",&q[i]);

      printf("\nThe queue element are as:-\n");

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

      printf("%2d ",q[i]);

      printf ("\nValues of at start rear=%d

      front=%d",r,f);

      printf ("\n\nHow many elements you want to

      delete: ");

      scanf ("%d",&n);

      while (f<n)

      {

      q[f]=NULL;

      f++;

      printf ("\nrear=%d front=%d",r,f);

      }

      printf ("\n Queue elements are: ");

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

      printf (" %d ",q[n]);

      }

    5. # include <stdio.h>

      # include <conio.h>

      # include <process.h>

      int qe[8];

      int r=0j;

      char ans='Y';

      void insert();

      void del ();

      void show ();

      main ()

      {

      int c; while(1)

      {

      clrscr();

      printf ("\n 1] Insert Element ");

      printf ("\n 2] Delete Element ");

      printf ("\n 3] Display element");

      printf ("\n 4] Exit");

      printf ("\n Enter your choice: ");

      scanf ("%d",&c);

      switch (c)

      {

      case 1: insert(); break;

      case 2: del(); show();break;

      case 3: show(); break;

      default: exit(0);

      }

      }

      }

      void insert ()

      {

      if (r>=7)

      printf ("\n Queue is full \n\n\n");

      else

      {

      ans='y';

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

      {

      printf ("\n Enter element:- ");

      scanf ("%d",&qe[r]);

      if (r==7)

      {

      clrscr();

      printf ("\n Queue is Full");

      getch();

      break;

      }

      else

      r++;

      printf ("\n Continue Y/N: ");

      ans=getch();

      }

      }

      }

      void show()

      {

      int j;

      for (j=0;j<r;j++)

      printf (" %d ",qe[j]);

      getch();

      }

      void del ()

      {

      if (r<=0)

      {

      clrscr();

      printf ("\n Queue is empty \n\n\n");

      }

      for (j=0;j<r;j++)

      qe[j]= qe[j+1];

      qe[r]=0;

      r--;

      }

    6. # include <stdio.h>

      # include <conio.h>

      void insert ();

      void del();

      void show ();

      int m,n=10,fr=0, queue[11],re=0,num,cur;

      main ()

      {

      int ch;

      do

      {

      clrscr();

      printf("\n[1] Insert");

      printf("\n[2] Delete");

      printf("\n[3] Show");

      printf("\n[4] Exit");

      printf("\nEnter Your choice: ");

      scanf("%d",&ch);

      switch(ch)

      {

      case 1: insert (); break;

      case 2: del (); break;

      case 3: show(); break;

      default: exit(0);

      }

      }

      while(1);

      }

      void insert ()

      {

      if (re<cur)

      {

      printf("\nQueue is full");

      exit (0);

      }

      printf("\nEnter a number to be inserted ");

      scanf ("%d",&queue[re]);

      re++;

      }

      void del ()

      {

      if (fr==re)

      {

      printf("\nThe queue is empty");

      exit(0);

      }

      fr++;

      if (fr==n)

      {

      fr=1;

      re=1;

      }

      }

      void show ()

      {

      for (m=fr;m<re;++m)

      printf (" %d ",queue[m]);

      getch();

      }

    7. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int *q;

      int re=0,r;

      clrscr();

      printf("\nEnter zero for exit\n");

      while(1)

      {

      printf ("Enter element: ");

      scanf ("%d",q);

      if(*q==0)

      { break; }

      q++;

      re++;

      if (re==7)

      {

      printf ("\n Queue is full ");

      break;

      }

      }

      q=q-re;

      printf ("\n Elements of Queue are: ");

      r=0;

      while (r<re)

      {

      printf ("\n Element: %d rear=%d", *(q+r),r);

      r++;

      }

      return 0;

      }

    8. # include <stdio.h>

      # include <conio.h>

      int qu[8],r,f=0,x=0;

      void insert();

      void del ();

      void show ();

      void main ()

      {

      int c;

      clrscr();

      printf ("\n [1] Insert Element ");

      printf ("\n [2] Delete Element ");

      printf ("\n [3] Display element");

      printf ("\n [4] Exit");

      printf ("\n Enter your choice:- ");

      scanf ("%d",&c);

      switch (c)

      {

      case 1: insert(); break;

      case 2: del(); show();break;

      case 3: show(); break;

      default: exit(0);

      }

      main ();

      }

      void insert ()

      {

      int n;

      char ch,ans='Y';

      if (r>=7)

      {

      while (qu[x]==0)

      {

      printf ("\n Enter a Number: ");

      scanf ("%d",&n);

      qu[x]=n;

      x++;

      puts("\n Continue Y/N: ");

      ch=getch();

      if (ch!='Y'||ch!='y')

      break;

      }

      printf ("\n Queue is full \n\n\n");

      main();

      }

      printf ("\n Enter elements: ");

      while (ans=='Y')

      {

      scanf ("%d",&qu[r]);

      if (r==7)

      {

      clrscr();

      printf ("\n Queue is Full");

      getch();

      break;

      }

      else

      r++;

      printf ("\n Continue Y/N: ");

      ans=getche();

      }

      }

      void show()

      {

      int j;

      for (j=0;j<8;j++)

      printf (" %d ",qu[j]);

      getch();

      }

      void del ()

      {

      int j;

      if (r==0)

      {

      clrscr();

      printf ("\n Queue is empty \n\n\n");

      main();

      }

      if (f==8)

      f=0;

      qu[f]=0;

      f++;

      }