Tuesday, August 5, 2008

The Queue Abstract Data Type


As opposed to a stack, a queue is an ordered list in which all insertions take place at one end (rear) and all deletions take place at the opposite end (front). Consider the queue in the figure 17.1 containing the elements U, V, W, and X. The first element that can be deleted from the queue is U. A new element say Y is to be inserted after X. Since the first element into a queue is the one which is to be removed, queue is also known as First-in-First-Out. (FIFO).

U V W X

é é

front rear

U V W X Y

é é

front rear

V W X Y

é é

front rear

Fig. 17.1 Insertion and deletion operations on a queue.


The operations that are to be included in the ADT Queue are listed below.

create (q)

- creates an empty queue

isempty(q)

-returns true if q is an empty queue else returns false

insert_queue(q,item)

-appends an element item at the rear of the queue q.

delete_queue(q)

-deletes the element at the front of q and returns the data of the element it has deleted.

17.1 ARRAY IMPLEMENTATION OF A QUEUE

In an array implementation of the queue given below (Example 17.1), the function create assigns -1 to both front and rear and 0 to noele (number of elements) indicating that the queue is empty. The isempty function returns TRUE, if the number of elements noele is 0. Since insertion in the queue always takes place only at rear, it is important to confirm that the queue is not full. The function isfull returns TRUE if number of elements in the queue noele is having the value of MAX-1, where MAX is the maximum number of elements that can be inserted in the queue. The deletion from the queue removes the elements from the location indicated by the front, and subsequently increments the front to the next element in the queue.

An array implementation of the operations of a ADT QUEUE having integer elements is given below.

EXAMPLE 17.1 :

# include

#define MAX 5

#define TRUE 1

#define FALSE 0

#define ERROR -1

struct qinfo{

int front,rear;

int noele;

int qelement[MAX];

};

typedef struct qinfo queue;

void create(),insert_queue();

int isfull(),isfull(),delete_queue();

void create(queue *q)

{

q->front=-1;

q->rear=-1;

q->noele=0;

return;

}

int isempty(queue *q)

{

if(q->noele == 0)

return(TRUE);

else

return(FALSE);

}

int isfull(queue *q)

{

if(q->noele == MAX)

return(TRUE);

else

return(FALSE);

}

void insert_queue(queue *q,int item)

{

char stop;

if(isfull(q))

printf("Queue is full \n");

else

{

if(isempty(q))

{

create(q);

q->front++;

q->rear++;

}

else

if(q->rear < (MAX - 1) || q->rear < (q->front - 1))

q->rear++;

else

if(q->rear == (MAX - 1) && q->noele <>

q->rear=0;

q->qelement[q->rear]=item;

q->noele++;

}

return;

}

int delete_queue(queue *q)

{

int data;

if(isempty(q))

{

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

return(ERROR);

}

else

{

data=q->qelement[q->front];

if(q->front == (MAX - 1))

q->front=0;

else

q->front++;

q->noele--;

if(isempty(q))

create(q);

return(data);

}

}

17.2 LINKED LIST IMPLEMENTATION OF QUEUE

The implementation of a queue using a linked list requires two pointers, the front and the rear to indicate the beginning and the last element of the list. Thus, each element of the queue is a node in a linear linked list containing a pointer to the next element. In the given implementation, a queue is identified by its front and rear pointers only. The function create, creates an empty queue and returns a pointer to it. The insert_queue inserts an element in the list. If it is a first time insertion, then the function makes the front and rear pointers point to the first node in the process. Any further insertion manipulates the rear pointer only. Similarly delete_queue uses the front pointer to delete the element and returns the element thus deleted. However, if the queue contains only one element, both the front and the rear pointers are assigned NULL values to indicate the queue is empty.

EXAMPLE 17.2 :

#define TRUE 1

#define FALSE 0

struct queue_element{

int data;

struct queue_element *next;

};

typedef struct queue_element queue_info;

typedef struct qpointer{

queue_info *front, *rear;

}queue;

queue *q;

queue *create()

{

queue *p;

p=(queue *)malloc(sizeof(queue));

p->front=NULL;

p->rear=NULL;

return(p);

}

int isempty(queue *q)

{

if(q->front == NULL)

return(TRUE);

else

return(FALSE);

}

void insert_queue (queue *q,int item)

{

queue_info *new;

new=(queue_info *) malloc (sizeof (queue_info));

new->next = NULL;

new->data = item;

if (isempty(q))

{

q->front = new;

q->rear = new;

}

else

{

q->rear->next=new;

q->rear=new;

}

return;

}

int delete_queue(queue *q)

{

int item;

queue_info *del;

if (isempty(q))

{

printf(“Queue is empty ! \n”);

return(-1);

}

else

{

del=q->front;

q->front=q->front->next;

item=del->data;

free (del);

if(q->front == NULL)

q->rear=NULL;

return(item);

}

}1. Suppose customers are arriving at a railway reservation counter for booking /cancellation of tickets. Show the contents of the queue at each step of the following sequence of operations. Also estimate maximum queue length.

i) create (Q); ii) create (Q);

insert (‘ Ashok’, Q); insert (‘Ashok’, Q);

delete (Q); insert (‘Amar’, Q);

insert (‘Amar’, Q); insert (‘Subir’, Q);

insert (‘Subir’, Q); delete (Q);

insert (‘Rajat’, Q); delete (Q);

delete (Q); insert (‘Rajat’, Q);

delete (Q); delete (Q);

2. Consider a queue of strings (names of persons). Using the operations of the ADT queue, explain how the following tasks can be performed.

i. Find how many persons are ahead of ‘Ashok’ in the queue.

ii. Find the length of the queue.

iii. Check whether two persons having same name are in the queue.

iv. Remove the second person from the queue, keeping rest of the queue unchanged.

v. Remove the last but one person from the queue.

No comments: