Queue – Data Structure

Queue is a first in first out (FIFO) structure i.e., the element inserted at the first will be removed first. It is a linear list in which data can only be inserted at one end, called rear, and deleted from the other end, called the front.

Queue can be compared with a line of people waiting for the tickets in a movie theatre.

Queues

Queue Operations

The basic operations in Queue are :

• enqueue
• dequeue
• queue front
• queue rear

Enqueue

Enqueue operation inserts an element into queue. The data can be inserted at one end called rear only.

Dequeu

Dequeue operation deletes an element from the queue’s front.

Queue front

Data at the front of the queue can be retrieved with queue front. It returns the data at the front of the queue without changing the contents of the queue.

Queue rear

Data at the rear of the queue can be retrieved with queue rear. It returns the data at the rear of the queue without changing the contents of the queue.

Queue linked list

Data structure

Two different structures to implement queue area queue head and data node.

The queue head contains two pointers called front & rear and a count value.

The data node contains user data and the link field pointing to the next node.

typedef struct node {
	void* dataptr;
	struct node* next;
}NODE;
typedef struct {
	NODE* front;
	NODE* rear;
	int count;
}QUEUE;

Without creating two structures, we can use double pointer in one structure.

Queue algorithms

Create queue

Following is the Algorithm to create and initialize queue structure :

1. Allocate queue head
2. Set queue front to null
3. Set queue rear to null
4. Set queue count to 0
5. Return queue head

Implementation in C programming

QUEUE* createqueue(void)
{
	QUEUE* queue;
	queue=(QUEUE*)malloc(sizeof(QUEUE));
	if(queue)
	{
		queue->front=NULL;
		queue->rear=NULL;
		queue->count=o;
	}
	return queue;
}

Enqueue

Following is an Algorithm, enqueue(queue,data_in), for enqueue operation :

1. if(queue full)
   1. return false
2. end if
3. allocate (new node)
4. move datain to new node data
5. set new node next to null pointer
6. if(empty queue)
   1. set queue front to address of new node
7. else
   1. set next pointer of rear node to address of new node
8. end if
9. set queue rear to address of new node
10. increment queue count
11. return true

Implementation

bool enqueue(QUEUE* queue,void* item)
{
	NODE* newptr;
	if(!(newptr=(NODE*)malloc(sizeof(NODE))))
	return false;
	newptr->dataptr=item;
	newptr->next=NULL;
	if(queue->count==0)
		queue->front=newptr;
		else
		queue->rear->next=newptr;
	(queue->count)++;
	queue->rear=newptr;
	return true;
}

Dequeue

Algorithm dequeue(queue,item)

1. if (queue empty)
   1. return false
2. end if
3. move front data to item
4. if(only one node in queue)
   1. set queue rear to null
5. end if
6. set queue front to queue front next
7. decrement queue count
8. return true

Implementation

bool dequeue(QUEUE* queue,void** item)
{
	NODE* deleteloc;
	if(!queue->count)
	return false;
	*item=queue->front->dataptr;
	deleteloc=queue->front;
	if(queue->count==1)
	{
			queue->rear=NULL;
			queue->front=NULL;
	}
	else
		queue->front=queue->front->next;
	(queue->count)--;
	free(deleteloc);
	return true;
}

Queue Front

Algorithm queuefront(queue,dataout)

1. if(queue empty)
   1. return false
2. end if
3. move data at front of queue to dataout
4. return true

Implementation

bool queuefront(QUEUE* queue,void** item)
{
	if(!queue->count)
		return false;
	else
	{
		*item=queue>front>dataptr;
		return true;
	}
}

Destroy queue

Algorithm destroyqueue(queue)

1. if(queue not empty)
   1. loop(queue not empty)
      1. delete front node
   2. end loop
2. end if
3. delete head structure

Implementation

QUEUE* destroyqueue(QUEUE* queue)
{
	NODE* deleteptr;
	if(queue)
	{
		while(queue->front!=NULL)
		{
			free(queue->front->dataptr);
			deleteptr=queue->front;
			queue->front=queue->front->next;
			free(deQQleteptr);
		}
		free(queue);
	}
	return NULL;
}

Queue applications

Queues are used in business online applications such as processing customer requests, jobs and orders.

Queues are used in categorization. Queues categorize data into different groups without losing the original ordering of data.

It can be used in web-servers, printers and processes waiting for CPU scheduling.