Data Structures using „C‟ - Overview of Queues

Data Structures using „C‟ Unit 4
Unit 4 Overview of Queues
Structure:
4.0 Introduction
4.1 Queues and its Operations
Self assessment Questions
4.2 Different types of queues
4.2.1 Ordinary queue
4.2.2 Disadvantage of ordinary queue
4.2.3 Double ended queue (Deque)
4.2.4 Circular queue
Self assessment Questions
4.3 Sample C programs to represents the Queue Implementation:
4.4 Summary
4.5 Terminal Questions
4.0 Introduction
A queue is a pile in which items are added an one end and removed from the other. In this respect, a queue is like the line of customers waiting to be served by a bank teller. As customers arrive, they join the end of the queue while the teller serves the customer at the head of the queue. As a result, a queue is used when a sequence of activities must be done on a first-come, first-served basis.
Queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end. (FIFO)
Objectives
At the end of this unit, you will be able to understand the:
 Brief introductions of Queues and its operations
 Different types of queues and its implementation in C
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 93
 Ordinary queue
 Double ended queue
 Circular queue
 Priority queue
4.1 Queues and its Operations
A queue is defined as a special type of data structure where elements are
inserted from one end and elements are deleted from the other end. The
end from where the elements are inserted is called „rear end ’(r) and the
end from where elements are deleted is called „front end’(f). In a queue.
always elements are inserted from the rear end and elements are deleted
from the front end. The pictorial representation of the queue is shown in
below figure.
Here, the front end is denoted by f and rear end is denoted by r. So, the first
item inserted into the queue is 10, the second item inserted is 20 and the
last item inserted is 30. Any new element to be inserted into this queue has
to be inserted towards right of 30 and that item will be the last element in the
queue. The first item to be deleted from the queue is the item which is at the
front of the queue i.e. 10. So it is very clear from the operations performed
on queues that First item Inserted is the First item to be deleted Out from
the queue. So queue is also called First In First Out (FIFO) data structure.
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 94
This data structure is useful in time-sharing systems where many user jobs will be waiting in the system queue for processing. These jobs may request the services of CPU, main memory or external devices such as printer etc. All these jobs will be given a fixed time for processing and are allowed to use one after the other. This is the case of an ordinary queue where priority is same for all the jobs and whichever job is submitted first, that job will be processed. The primitive operations that can be performed on queues are: nsert an item into queue
 Delete an item from queue
 Display the contents of queue
Other useful operations can be qempty( ) which returns true if queue is empty else returns false and the function qfull() which returns true if queue is full, therwise it returns false. Sometimes, based on the preference, jobs may have to be processed. Such a queue where a job is processed based on the priority is called a priority queue. Let us see the various types of queues in the next section.
Self Assessment Questions
1. Define Queue.
2. Discuss the representation of Queue with neat diagram.
4.2 Different types of queues
The different types of queues are:
 Ordinary queue
 Double ended queue
 Circular queue
 Priority queue
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 95
4.2.1 Ordinary queue
This queue operates on first come first serve basis. Items will be inserted from one end and they are deleted at the other end in the same order in which they are inserted. Here first element inserted is the first element to go out of the queue. A queue can be represented using an array as shown in fig. The operations that can be performed on these queues are
 Insert an item at the rear end
 Delete an item at the front end
 Display the contents of the queue
Let us discuss how these operations can be designed and implemented.
a) Insert at the rear end
Consider a queue, with QUEUE_SIZE as 5 and assume 4 items are present as shown in below fig. a.
Here, the two variables f and r are used to access the elements located at the front end and rear end respectively. It is clear from this figure that at most 5 elements can be inserted into the queue. Any new item should be to be inserted to the right of item 40 i.e., at q[4]. It is possible if we increment r by 1 so as to point to next location and then insert the item 50. The queue after inserting an item 50 is shown in above fig. b. So, the formal version of the function can be written as:
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 96
void insert_rear()
{
q[++ r] = item;
}
Note that as we insert an element, r is incremented by 1 and finally the queue may be full. When queue is full, it is not possible to insert any element into queue and this condition is called overflow i.e., when r reaches QUEUE_SIZE-l, queue becomes full. The function shown in below example, returns 1 if queue is full; otherwise, the function returns 0.
Example 1 : Function to check whether queue is full
int qfull(int r)
{ /* returns true if queue is full otherwise false */
return ( r == QUEUE_SIZE-1 ) ? 1: 0;
}
Once the function qfull() returns true, it is not possible to insert an item; otherwise, an item can be inserted and the function insert_rear() can be modified as shown in below example.
Example 2: Function to insert an item at the rear end of queue
void insert_rear (int item, int q[], int *r)
{
if ( qfull(*r) ) /* Is queue full ? */
{
printf("Queue overflow\n");
return;
}
/* Queue is not full */
q[+ +(*r)] = item; /* Update rear pointer and insert a item */
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 97
b) Delete from the front end
The first item-'to be deleted from the queue is the item, which is at the front
end of the queue. It is clear from the queue shown in below fig. (a) that the
first item to be deleted is 10. Once this item is deleted, next item i.e., 20 in
the queue will be the first element and the resulting queue is of the form
shown in fig. (b).
So, the variable f should point to 20 indicating that 20 is at the front of the
queue. This can be achieved by accessing the item 10 first and then
incrementing the variable f. The formal version of the program can be
written as:
void delete_front()
{
printf("The deleted item is %d\n",q[f+ +]);
}
But, as we delete an item one after the other, finally queue will be empty.
Consider the queue shown in fig. (C). Once the item 40 is deleted, f points
to the next location and queue is empty i.e., whenever the front end
identified by f is greater than the rear end identified by r, then queue is
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 98
empty. This condition is called underflow of queue. The function to check for an underflow of queue is shown in below example.
Example 3: Function to check for underflow of queue
int qempty(int f, int r)
{
return ( f > r) ? 1 : 0; /* returns true if queue is empty otherwise returns false */
}
The function qempty( ) returns true when queue is empty and returns false when queue is not empty. If queue is empty, it is not possible to delete an element from queue and this condition is called underflow of queue. So, the formal version of the function delete_front( ) can be modified so as to check for underflow and the modified version is shown in below example.
Example 4: Function to delete an item from the front end
void delete_front(int q[], int *f, int *r)
{
if ( qempty(*f, *r) )
{
printf("Queue underflow\n");
return;
}
printf("The element deleted is %d\n", q[(*f)+ +]);
if(*f> *r)
{
*f=O,*r=-l;
}
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 99
Consider the situation shown in above fig. (d). Deleting an item 50 from queue results in an empty queue. At this stage, suppose an item has to be inserted. Observe that the function insert_rear( ) shown in above examples displays the message "Queue overflow", because the rear pointer r reaches QUEUE_SIZE-l. It is clear from the queue (shown in figure (d)) that queue is not full and even then, an item can not be inserted. For this reason, whenever queue is empty, we reset the front end identified by f to 0 and rear end identified by r to -1. So, the initial values of front pointer f and rear pointer r should be 0 and -1 respectively.
c) Display queue contents
The contents of queue can be displayed only if queue is not empty. If queue is empty an appropriate message is displayed. The function display is shown in below example.
Example 5: Function to display the contents of queue
void display(int q[], int f, int r)
{
int i;
if ( qempty(f,r) )
{
printf("Queue is empty\n");
return;
}
printf("Contents of queue is\n");
for(i=f;i<= r; i+ +)
printf(" %d\n",q[i]);
}
The complete C program to implement different operations on an ordinary queue is shown in example .
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 100
Example : C program to implement an ordinary queue
#include <stdio.h>
#include <process.h>
#define QUEUE_SIZE 5
/* Include function to check for overflow shown in example 4.2.1- Eg. 1 */
/* Include function to check for underflow shown in example 4.2.1- Eg. 3 */
/* Include function to insert an item at the rear end shown in example 4.2.1- Eg. 2 */
/* Include function to delete an item at the front end shown in example 4.2.1- Eg. 4 */
/* Include function to display the contents of queue shown in example 4.2.1- Eg. 5 */
void main()
{
int choice,item,f,r,q[10];
/* Queue is empty */
f = 0; /* Front end of queue*/
r = -1; /* Rear end of queue*/
for (;;)
{
printf(" 1 :Insert 2: Delete\n");
printf("3: Display 4: Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d", &item);
insert_rear(item, q, &r};
break;
case 2:
delete_front(q, &f, &r);
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 101
break;
case 3:
display(q, f, r);
break;
default:
exit(0);
}
}
}
Output
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 2
Queue underflow
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 3
Queue empty
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 1
Enter the item to be inserted 10
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 1
Enter the item to be inserted 20
1: Insert 2: Delete
3: Display 4: Exit
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 102
Enter the choice 1
Enter the item to be inserted 30
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 3
Contents of queue is
10
20
30
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 2
The element deleted is 10
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 2
The element deleted is 20
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 2
The element deleted is 30
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
3 Queue is empty
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 4
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 103
4.2.2 Disadvantage of ordinary queue
Consider the queue shown in fig. This situation arises when 5 elements say 10,20,30,40 and 50 are inserted and then deleting first four items.
If we try to insert an element say 60, since r has the value QUEUE_SIZE-1 (where QUEUE_SIZE is the maximum number of elements that can be stored in a queue), we get an overflow condition and it is not possible to insert any element. Even though queue is not full, in this case, it is not possible to insert any item into the queue. This disadvantage can overcome if we use the circular queue, which will be discussed in Circular queue.
4.2.3 Double ended queue (Deque)
Another type of queue called double-ended queue also called Deque is discussed in this section. Deque is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue. The operations that can be performed on deques are
 Insert an item from front end
 Insert an item from rear end
 Delete an item from front end
 Delete an item from rear end
 Display the contents of queue
The three operations insert rear, delete front and display and the associated operations to check for an underflow and overflow of queue have already
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 104
been discussed in „ordinary queue‟. In this section, other two operations i.e.,
insert an item at the front end and delete an item from the rear end are
discussed.
a) Insert at the front end
Consider queue shown in above fig (a). Observe that, the front end
identified by f is 0 and rear end identified by r is -1. Here, an item can be
inserted first by incrementing r by 1 and then insert an item. If the front
pointer f is not equal to 0 as shown in above fig. (b), an item can be inserted
by decrementing the front pointer .f by 1 and then inserting an item at that
position. Except for these conditions, it is not possible to insert an item at
the front end. For example, consider the queue shown in above figure (c).
Here, an item 10 is already present in the first position identified by f and so,
it is not possible to insert an item. The complete C function to insert an item
is shown in below example.
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 105
Example 1: Function to insert an item at the front end
void insert_front(int item, int q[ ], int *f, int *r)
{
if( *f= = 0 && *r = = -1)
q[++(*r)] = item;
else if ( *f ! = 0)
q[--(*f)]=item;
else
printf("Front insertion not possible\n");
}
b) Delete from the rear end
To delete an element from the rear end, first access the rear element and then decrement rear end identified by r. As an element is deleted, queue may become empty. If the queue is empty, reset the front pointer f to 0 and rear pointer r to -1 as has been done in an ordinary queue. We delete an element only if queue is not empty. The complete C function to delete an item from the rear end is shown in below example.
Example 2: Function to delete an item from the rear end of queue
void delete_rear(int q[],int *f, int *r)
{
if ( qempty(*f,*r) )
{
printf("Queue underflow\n");
return;
}
printf("The element deleted is %d\n".q[(*r)--]);
if (*f > *r)
{
*f = 0, *r = -1 ;
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 106
}
}
Example : C program to Implement double-ended queue
#include <stdio.h>
#include <process.h>
#define QUEUE_SIZE 5
/* Include function to check for overflow 4.2.1 Eg.-1*/
/* Include function to check for underflow 4.2.1 Eg -3*/
/* Include function to insert an item at the front end 4.2. 3 Eg.-1*/
/* Include function to insert an item at the rear end 4.2.1 Eg -2*/
/* Include function to delete an item at the front end 4.2.1 Eg -4*/
/* Include function to delete an item at the rear end 4.2. 3 Eg.-2*/
/* Include function to display the contents of queue 4.2.1 Eg -5*/
void main()
{
int choice,item,f,r,q [10];
f=0; r = -1;
for (;;)
{
printf(" 1:Insert_front 2:lnsert_rear\n");
printf("3: Delete_front 4: Delete_rear\n" );
printf("5: Display 6:Exit\n");
printf("Enter the choice\n");
scanf("%d" ,&choice );
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 107
scanf("%d",& item);
insert_ front(item, q, &f, &r);
break;
case 2:
printf("Enter the item to be inserted\n");
scanf("%d",& item);
insert_rear(item, q, &r);
break; case 3:
delete _front(q, &f, &r);
break;
case 4:
delete_rear(q, &f, &r);
break;
cases 5:
display(q, f, r);
break;
default: .
exit(0);
}
}
}
4.2.4 Circular queue
In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE -1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-l, item cannot be inserted. Pot details refer in Disadvantage of ordinary queue. This disadvantage is overcome using circular queue. The pictorial representation of a circular
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 108
queue and its equivalent representation using an array are given side by side in below fig in next page.
Assume that circular queue contains only one item as shown in below fig. (a). In this case, the rear end identified by r is 0 and front end identified by f is also 0. Since rear end is incremented while insertion, just before inserting the first item, the value 'of r should be -1 (Note: An item is inserted only at the rear end and so, only r is incremented by 1 and not f) so that after insertion, f and r points to an item 10. So, naturally, the initial values of f and r should be 0 and -1.
The configuration shown in below fig. (b) is obtained after inserting 20 and 30. To insert an item, the rear pointer r has to be incremented first. For this, any of the two statements shown below can be used.
r = r + l or r = (r + 1) %QUEUE_SIZE
Both statements will increment r by 1. But, we prefer the second statement. We see why this method is preferred instead of a simple statement
r= r+1
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 109
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 110
The queue shown in fig.(c) is obtained after inserting 40 and 50. Note that at this point, the queue is full. Suppose we delete two items 10 and 20 one after the other. The resulting queue is shown in fig. (d). Now try to insert an item 60. If the statement
r= r+1
is used to increment rear pointer, the value of r will be 5. But because this is a circular queue r should point to 0. This can be achieved using the statement
r = (r + 1) % QUEUE_SIZE
After execution of the above statement r will be 0. If this approach is used to check for overflow or underflow, we use a variable count that contains the number of items in the queue at any instant. So as an item is inserted, increment count by 1 and as an item is deleted decrement count by 1. By this it is ensured that at any point of time, count always contains the total number of elements in the queue. So, if queue is empty, count will be 0 and if queue is full, count will be QUEUE_SIZE. Thus we can easily implement the two functions qfull( ) and qempty( ) and these functions are shown in below examples 1 and 2 respectively.
Example 1 : Function to check queue overflow
int qfull(int count)
{
return ( count = = QUEUE_SIZE ) ? I: 0; /* return true if Q is full; otherwise false */
}
Example 2: Function to check queue underflow
int qempty (int count)
{
return ( count == 0 ) ? 1: 0; /* return true if Q is empty; otherwise false */
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 111
}
Example 3 : Function to insert an item at the rear end
void insert_rear(int item, int q[], int *r, int *count)
{
if ( qfull(*count) )
{
printf("Overflow of queue\n");
return;
}
*r = (*r + 1) % QUEUE_SIZE ; /* increment rear pointer */
q[*r] = item; /* Insert the item */
*count += 1; /* update the counter */
}
a) To insert from the front end
Note that insertion is done only when queue is not full. So, if queue is not full, to insert an item, increment rear end identified by r by 1 and then insert. Also, as an item is inserted update the value of count by 1. The variable count is used to check for overflow or underflow. The function to insert an item into the queue is shown in the above example 3.
b) To delete from front end
As in an ordinary queue, the element at the front end of the queue has to be deleted. 'So, access an item which is at the front end by specifying q[f] and update the front end identified f to point to next front item. The front end identified by f can be incremented using the following statement
f= (f+ 1) % QUEUE_SIZE;
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 112
As an item is deleted from a queue, the count should be decremented by 1. The complete C, function to delete an element from the circular queue is shown in below example 4.
Example 4 : Function to delete an item from the front end of queue
void delete_front(int q[], int *f, int *count)
{
if ( qempty(*count) )
{
printf("Underflow of queue\n");
return;
}
printf("The deleted element is %d\n",q[*f]); /* Access the item */
*f = (*f + 1) % QUEUE_SIZE; /* Point to next first item */
*count -= 1; /* update counter */
}
c) To display queue contents
If queue is not empty, elements in the queue should be displayed from the front end identified by f to the rear end identified by r. The total number of items to be displayed can be obtained from the variable count. This can be achieved by initializing the index variable i to the front end identified by f and incrementing i each time using the statement
i= (i + 1)% QUEUE_SIZE;
count number of times. As the index variable i point to the each item in the queue, the queue contents can be accessed and displayed one by one. The function to display the contents of circular queue is shown in below example 5.
Example 5: Function to display the contents of the queue
void display(int q[], int f, int count)
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 113
{
int i, j ;
if ( qempty(count) )
{
printf("Q is empty\n");
return;
}
printf(“Contents of queue is\n”);
i= f; /* Point to front of queue */
for ( j = 1; j <= count; j++)
{
printf(%d “,q[i]); /* access, the item */
i= (i + 1) % QUEUE_SIZE; /* Point to next item */
}
printf(“\n”);
}
The complete C program to implement circular queue is shown in below example 6.
Example 6: C program to implement circular queue
#include <stdio.h>
#include <process.h>
#define QUEUE_SIZE 5
/* function to check for overflow shown in example 1. */
/* function to check for underflow shown in example 2 */
/* function to insert an item at the rear end shown in example 3 */
/* function to delete an item from the front end shown in example 4 */
/* function to display the contents of the queue shown in example 5 */
void main()
{
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 114
int choice,item,f,r,count,q[20];
f= 0;
r= -1;
count = 0; /* queue is empty */
for (;;)
{
printf(" 1 :Insert 2: Delete\n");
printf("3: Display 4: Exit\n");
printf("Enter the choice\n");
scanf("%d",& choice);
switch ( choice )
{
case 1:
printf("Enter the item to be inserted\n");
scanf("%d",& item);
insert_rear( item.q ,&r ,&count );
break;
case 2:
delete_front(q, &f, &count); break;
case 3:
display(q, f, count); break;
default:
exit(0);
}
}
}
Output
1: lnsert 2: Delete
3: Display 4: Exit
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 115
Enter the choice
2
Underflow of queue
1: lnsert 2: Delete
3: Display 4: Exit
Enter the choice
3
Q is empty
l: lnsert 2: Delete
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted 10
1: lnsert 2: Delete
3: Display 4: Exit
Enter the choice 1
Enter the item to be inserted 20
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 1
Enter the item to be inserted 30
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted 40
1: Insert 2: Delete
3: Display 4 Exit
Enter the choice
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 116
1
Enter the item to be inserted 50
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
1
Enter the Item to be inserted 60
Overflow of Q
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
2
The deleted item is 10
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted 60
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted 70
Overflow of Q
1: Insert 2: Delete
3: Display 4: Exit
Enter the choice 4
The C program to simulate the working of circular queue of names using an array is shown in below example 7.
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 117
Example 7: C program to implement circular queue with items as strings
#include <stdio.h>
#include <process.h>
#include <alloc.h>
#include <string.h>
#define QUEUE_SIZE 5
/* function to check for underflow */
int qempty(int count)
{
return ( count = = 0 ) ? 1: 0;
}
/* function to check for overflow */
int qfull(int count)
{
return ( count = = QUEUE_SIZE ) ? 1: 0;
}
/* function to insert an item at the rear end */
void insert_rear(char item[], char q[][30], int *r, int *count)
{
if ( qfull(*count) )
{
printf("Overflow of queue\n”);
return;
}
*r = (*r + 1) % QUEUE_SIZE; ,
strcpy (q[*r],item);
*count += 1 ;
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 118
/* function to delete an item from the front end */
void delete_ front(char q[][30], int *f, int *count)
{
if ( qempty(*count) )
{
printf("Underflow of queue\n”);
return;
}
printf ("The deleted element is %s\n",q[*f]);
*f = (*f + 1) % QUEUE_SIZE;
*count-= 1;
}
/* function to display the contents of the queue */
void display(char q[][30], int f, int count)
{
int i,j;
if (qempty (count) )
{
printf("Q is empty\n");
return;
}
printf("Contents of queue is\n ");
i= f;
for (j = l;j <= count; j++)
{
printf("%s\n",q[i]);
i = (i + 1) % QUEUE_SIZE; }
printf("\n");
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 119
void main()
{
int choice,f,r,count;
char item[20],q[20][30];
f=0;
r = -1;
count = 0; /* queue is empty */
for (;;)
{
printf("1: Insert 2: Delete\n");
printf("3: Display 4: Exit\n");
printf("Enter the choice\n");
scanf("%d", & choice);
switch ( choice )
{
case 1:
printf ("Enter the item to be inserted\n");
scanf("%s", item);
insert_rear(item, q,& r ,&count);
break;
case 2:
delete_ front(q, &f, &count);
break;
case 3:
display(q, f, count);
break;
default:
exit(0);
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 120
}
}
Self Assessment Questions
1. Explain the ordinary Queue Insert at the rear end with suitable example.
2. Discuss the deletion of item from queue with suitable example.
3. Write „C‟ Program to display the contents from the queue.
4.3 Sample C programs to represents the Queue Implementation :
Example 1
// Stack Implementation using arrays to Insert element in the Stack
#include<stdio.h>
#include<conio.h>
#define Max 5
int Staff (Max] , top=-l;
void display( )
{
if ((top= =-l) || (top= =0))
{
printf{"\n Stack is full \n");
}
else
{
printf{"\n Stack elements are \n”);
for(int i=top-1;i>=0;i--)
printf("%5d", Staff([i]);
}
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 121
void push ( )
{
int ele;
char ch;
if(top-=-l)
top=0;
do
{ if(top>=5)
{
printf(“\n STACK IS FULL”);
break;
}
else
{ clrscr( );
printf ("\nENTER THE ELEMENT TO BE INSERTED\n") ;
scanf("%d",&ele) ;
Staff(top++]=ele;
display ( ) ;
}
printf ("\nDO U WANT 2 ADD MORE ELEMENTS:?\n");
scanf ( "\n%c" , &ch);
}while ( (ch= ='y' ) || (ch=='Y' ) );
}
void pop ( )
{
if ( (top= =-l) || (top= =0))
{
printf ("\nstack is under flow\n");
}
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 122
else
{
printf{"\n %d is deleed from stack\n",Staff(--top]) ;
display( );
}
}
Example 1
//Stack Implementation using push and pop
void main()
{
clrscr( );
char c;
int choice;
do
{
clrscr() ;
printf("\n Enter the choice\n");
printf ("l->push\n");
printf ("2->pop\n") ;
scant (" %d ",&choice);
if(choice= =l)
push( );
else if(choice= =2)
pop ( ) ;
else
printf (" \ninvalid choice");
printf ("\ndo u want 2 continue:?";
scanf("\n%c",&c) ;
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 123
}while{ (c=='y')||(c=='Y'));
}
Example 2
// Stack Implementation using array
#include<stdio.h>
#include<conio.h>
#define Max 5
int a [Max] , top=-l;-
void push()
{
int ele;
char ch;
if(top= =-l)
top=0;
do
{
if(top>=5)
{
printf("Stack if full");
break;
else
{
clrscr();
printf ( "Enter element to be inserted\n" ) ;
scanf(“%d”,&ele);
a[top++] =ele;
}
printf ( "Do you want to add more elements: ?\n") ;
scanf ( "\n%c" , &ch);
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 124
printf(“%c”,ch)
}while((ch= = „Y‟)||(ch==‟Y‟));
}
void pop( )
{
if(top= =-l)
{
printf ( "stack is underflow\n");
}
else
{
for(int i=top-l;i>=0;i--)
printf ("%d\n", a [i] ) ;
}
}
void main()
{
clrscr ( ) ;
char c;
int choice;
do
{
clrscr( );
printf ("Enter Your Choice\n");
printf("l -> Push\n");
printf ("2 -> Pop\n");
scanf ("%d", &Choice);
if(choice= =l)
push( );
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 125
else if (choice= = 2)
pop( );
else
printf(“invalid choice”);
printf(“Do You Want to continue\n”);
scanf(“\n%c”,&c);
}while((c= = „y‟)||(c= = „Y‟));
}
Example 3
// Queue Implementation using Array
#include<stdio.h>
#include<conio.h>
#define Max 5 // define macro
int Queue (Max] , front=-l, rear=0;
void Display ( )
{
int i;
if(front+l==rear)
printf("Empty Queue\n");
else
{
printf ("Elements of Queue \n”) ;
for (i=front+l ; i<rear; i++)
printf(“ %d\t",Queue[i]);
printf("\n”);
}
}
void InsertElement( )
{
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 126
int ele;
if (rear= = Max)
printf("Queue is Full");
else
{
printf("Enter Element to be Inserted\n");
scanf("%d",&ele);
Queue (rear++] =ele;
Display( );
}
}
void DeleteElement ( )
{
if(front+l= 0=rear)
printf("Empty Queue \n");
else
{
printf("%d is Deleted from Queue\n”, Queue[++front ]);
Display( );
}
}
void main( )
{
clrscr( ); .
char c;
int choice;
do
{
printf("Select Your Choice\n");
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 127
printf("1-> Insert\n");
printf("2 -> Delete\n") ;
scanf("%d",& choice);
if(choice= =1)
InsertElement( );
else if(choice= =2)
DeleteElement();
else
printf("Invalid choice”);
printf(“\nDo You Want to Continue \n”);
scanf("\n%c",&c);
}while((c= = „y‟) || (c=='Y'));
}
Example 4
//Stack Implementation using Pointers
#include<stdio"h>
#include<conio.h>
#include<alloc.h>
#define NewNode (Node*)malloc(sizeof(Node))
typedef struct node
{
int item;
struct node *next;
}Node;
Node * Push(Node* );
Node * Pop(Node *);
void Display(Node*);
void main()
{
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 128
int ch;
Node *start=NULL;
clrscr();
do
{
printf("Select choice\n ");
scanf("%d",&ch);
switch(ch)
{
case 1:
start= Push( start);
break;
case 2:
start= Pop( start);
break";
default:
printf("Invalid Choice\n ");
break;
}
Display( start ) ;
}while( ch!=0);
}
Node* Push(Node *s)
{
Node *tmp=NULL;
tmp=NewNode;
int item;
tmp->next=NULL;
printf("Enter the Item \n");
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 129
scanf("% d" , &tmp->item );
if(s==NULL)
s=tmp;
else
{
tmp->next=s
s=tmp;
}
return(s);
}
Node *Pop(Node*s )
{
Node *tmp;
if(s!=NULL)
{
printf("Element Deleted: %d\n",s~>item);
tmp=s;
s=s->next;
free(tmp);
}
else
printf("Stack Underdlow\n");
return(s);
}
void Display(Node *s )
{
Node* tmp;
tmp=s;
if( tmp! = NULL )
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 130
{
while(tmp!=NULL )
{
printf(“%d ->",tmp->item);
tmp=tmp->next;
}
printf (Null\n ");
}
else
printf("Stack Underflow\n");
}
// Queue Implementation using Pointers
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
#define NewNode (Node *)malloc(sizeof(Node))
typedef struct node
{
int item;
node *next;
}Node;
Node * Insert(Node *f, Node *r);
Node * Delete(Node *f, Node *r);
void Display(Node *f, Node *r);
void main( )
{
Node *front=NULL,*rear=NULL;
int ch,flag=0;
do
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 131
{
printf("Enter Your Choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
rear=Insert(front, rear);
if(flag= = 0)
{
front=rear;
flag=l;
}
break;
}
case 2:
{
front=Delete(front, rear);
if(front-=NULL)
{
rear=NULL;
flag=0;
}
Break;
}
default:
{
printf("Invalid Choice\n");
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 132
break;
}
}
}while(ch!=0);
}
Node*Insert (Node *f, Node *r)
{
Node * tmp;
tmp=NewNode;
scanf(“%d",&tmp->item);
tmp->next=NULL;
if(r==NULL)
{
r=tmp;
f=tmp;
}
else
{
tmp->next=r;
r=tmp;
Display(r, f);
}
return(r);
}
Node * Delete(Node *f,Node *r)
{
Node *ptr;
if(f==NULL)
printf("Empty Queue\n");
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 133
else if(f= =r)
{
printf("Element Deleted:% d\n",f->item);
free(r);
f=r=NULL;
}
else
{
ptr=r;
while(ptr->next->next!=NULL)
ptr=ptr->next;
ptr->next=NULL;
printf("Element Deleted: %d\n",f->item);
free(f);
f=ptr;
}
Display(r,f);
return(f);
}
void Display(Node *r,Node *f)
{
Node *ptr=r;
if(ptr==NULL)
printf("Queue Empty\n");
else
{
while(ptr!=f)
{
printf("%d ->",ptr->item);
Data Structures using „C‟ Unit 4
Sikkim Manipal University Page No.: 134
ptr=ptr->next;
}
printf("%d ->",ptr->item);
printf("\n") ;
}
}
4.4 Summary
Queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end. (FIFO) In this unit discussed the various types of Queues (such as Ordinary Queue, Double ended Queue, Circular Queue, Priority Queue) and its implementation using C programming for its different operations such as insertion, deletion, display etc. from/to the queues.
4.5 Terminal Question
1. Define Queue with neat diagram.
2. Explain the different types of Queues.
3. Discuss the Insert/Delete operation from the rear and front end of the queue.
4. Illustrate the „C‟ program to implement an ordinary queue.
5. Write note on:
Double ended queue (Deque)