Home Misc Implementing a Queue

# Implementing a Queue

0 comment

Before implementing a queue, we must know the basic operations that should be available for a queue.

Main Queue Operations:-

• enQueue(int data) :- Inserts an element at the end of the queue.
• int deQueue():- Removes and returns the element at the front of the queue.

Auxiliary Queue Operations:-

• int front():- Returns the first element at the queue, without removing it.
• int queueSize():- Returns the size of the queue.
• int isEmptyQueue():- Indicates whether no elements are present.

We can implement a queue using an ADT (Abstract Data Type). To implement a queue, we can use the structure for the node of a Linked List:-

struct node
{
int data;
struct node * next;
};


Further, a Queue is represented by a front end and a rear end. Thus, we can extend the data structure of the Linked List node to use it in our queue.

struct queue
{
struct node * front;
struct node * rear;
};


Now, to ENQUEUE, we need to add a node to the original queue. If the queue is initially NULL, we need to allocate new memory and assign the value to a node and update the FRONT and REAR. However, if the queue is already full, we need to add a new node at the REAR and then update the REAR pointer of the queue.

//implementing a function to EnQueue an element
struct queue * enQueue(struct queue * q, int num)
{
struct node * temp = (struct node*)malloc(sizeof(struct node));
temp -> data = num;
temp -> next = NULL;

//check if the queue is NULL
if(q==NULL)
{
q = (struct queue*)malloc(sizeof(struct queue));

//overflow check
if(!q)
{
printf("OVERFLOW EXCEPTION");
return NULL;
}

//here we need to update the FRONT pointer
q -> front = temp;
}
else
{
//We assign the NEXT of last node to the temp node we created
q -> rear -> next = temp;
}

//We need to update the REAR pointer in both the cases
q -> rear = temp;

//return the FRONT
return q;
}


The DEQUEUE, operation involves to print the FRONT of the node and then UPDATE the FRONT pointer. Printing the value is totally optional.

//implementing a DEQUEUE operation
struct queue * deQueue(struct queue * q)
{

//underflow check
if(q == NULL)
{
printf("UNDERFLOW EXCEPTION\n");
return NULL;
}

printf("The element dequeued is:- %d\n",q->front->data);

struct queue * temp = q->front;

//We need to update the FRONT pointer
q -> front = q->front->next;

//free the memory
free(temp);

return q;
}


The print operation of the queue can also be implemented as follows.

void printer(struct queue * q)
{
struct node * x = q->front;
while(x != NULL)
{
printf("%d ",x->data);
x = x->next;
}
}


A working demo of the program can be downloaded here containing the main function as well. Use your favorite editor like gEdit, Notepad++, vim to open it.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More