Linear Data Structure 491
14.17 REPRESENTATION OF QUEUE
The queue can be put into operation in two ways,
a) Static implementation : Static implementation means array implementation. In this
implementation, we should be assured of the number of elements we want in the queue. The
size of the array is decided before execution at compile time. Once the array is declared, its size
cannot be altered. The array at run time neither enlarged nor shrunk. The beginning of the
array, that is, Oth element is the front and the last memory location will be rear of the queue. A
queue can be declared as an array of any data type.
int queue[7];
In the above statement, an array queue [] of integer type is declared.
Front
5 4
00
7
3
00
Rear
Fig. 14.16 Queues
From Fig.14.16 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 [6] 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.
5) When we continuously insert elements in the queue the elements are shifted from front to rear.
For the first two points, it assumed that we follow the fifth point.
Consider the following program.
14.11 Write a program to implement a queue using an array.
# include <stdio.h>
# include cconio.h>
# include cprocess.h>
main ()
{
int queue[8];
int rear»0;
clrscrO ;
while(1)
{
printf ("Enter element : " );
scanf ( ”%d",& queue[rear]);
rear++;
492 Programming and Data Structures
if (rear««7)
{
printf ("
Queue is fu ll ");
break;
}
}
prin tf ("n Elements of Queue are : ");
rear«0;
while (1)
{
printf (■ %d ", queue[rear]);
rear++;
i f (re a r»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 The above is a simple example of a 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 element.
14.12 Write a program to insert elements in a queue.
# include <stdio.h>
# include <conio.h>
# include <process.h>
# define S 5
main ()
{
int queue[S];
int rsO,n;
Linear Data Structure 493
c lrs c r();
while (1)
{
i f (r>=S)
{
printf ("
Queue overflow*);
break;
}
else
printf ("Enter a number : ");
scanf ("%d",&n);
queue[r]>n;
r+ + ;
}
printf ("
Queue elements are : ”);
for (n«0;ncS;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
14.13 Write a program to perform insertion operation and show values of front and rear.
# include<stdio.h>
# include cconio.h>
main ()
{
int queue[7];
int ro- 1 , fn- 1 , j ;
c lr s c r ();
printf ( ”rear«%d front-%d Enter element : " , r , f ) ;
while (rc6)
494 Programming and Data Structures
r++;
scanf ( "%d”,&queue[r]);
i f (r==0 ) f =0;
printf ("rear=%d front=%d Enter element : n, r , f ) ;
printf ("
Queue elements are : " );
for ( j*0 ; j<7; j ++)
printf (" %d ", queue[j]);
OUTPUT:
rear= -1 front=
rear=0 front=0
rear=l front=0
rear=2 front=0
rear=3 front=0
rear=4 £ront=0
rear=51ront=0
rear=6 front=0
-1 Enter element:8
Enter element:9
Enter element:4
Enter element:5
Enter element:l
Enter element:2
Enter element:3
Enter element:
Queue elements are: 8 9 4 5 1 2 3
Explanation In the above program our aim is to concentrate only on 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 0. 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 it attains a
value ranging from 2 to 6. On the other hand, the value of front changes only once from -1 to 0 and
later its value remains the same.
1) Deletion of the element : The following programs explain insertion and deletion operations
with suitable examples.
14.14 Write a program to perform deletion operation on a queue and show values of front
and rear.
# include<stdio.h>
# include <conio.h>
main ()
{
int queue[7 ]= { l , 2,3,4,5,6,7};
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.