Page 169 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Queue has two ends. One is front from where the elements can be deleted and the other if rear to
where the elements can be added. A queue can be implemented using Arrays or Linked lists.
Each representation is having it’s own advantages and disadvantages. The problems with arrays
are that they are limited in space. Hence, the queue is having a limited capacity. If queues are
implemented using linked lists, then this problem is solved. Now, there is no limit on the
capacity of the queue. The only overhead is the memory occupied by the pointers.
Algorithm for addition of an element to the queue:

Step 1: Create a new element to be added
Step 2: If the queue is empty, then go to step 3, else perform step 4
Step 3: Make the front and rear point this element
Step 4: Add the element at the end of the queue and shift the rear pointer to the newly added
element.
Algorithm for deletion of an element from the queue:
Step 1: Check for Queue empty condition. If empty, then go to step 2, else go to step 3

Step 2: Message “Queue Empty”
Step 3: Delete the element from the front of the queue. If it is the last element in the queue, then
perform step a else step b

(a) make front and rear point to null
(b) shift the front pointer ahead to point to the next element in the queue

10.1.1 Sequential Representation of a Queue

As the stack is a list of elements, the queue is also a list of elements. The stack and the queue
differ only in the position where the elements can be added or deleted. Like other liner data
structures, queues can also be implemented using arrays.
Program given below lists the implementation of a queue using arrays.
#include “stdio.h”
#define QUEUE_LENGTH 50
struct queue
{ int element[QUEUE_LENGTH];
int front, rear, choice,x,y;
}
struct queue q;
main()
{
int choice,x;
printf (“enter 1 for add and 2 to remove element front the queue”)
printf(“Enter your choice”)
scanf(“%d”,&choice);
switch (choice)
{

162 LOVELY PROFESSIONAL UNIVERSITY