Does queue use linked list?

Previous:

• Queue in C

Theprevious articlewas all about introducing you to the concepts of a queue. In this article, we will code up a queue and all its functions using a linked list.

The first thing required to make a queue using a linked list is obviously a linked list. So, let's start by creating a linked list.

The concepts and the codes of a linked list are explained in the article Linked list in C.

typedef structnode node In this line of code, we are just representingstructnodewithnodeby usingtypedef. You can learn about typedef from thetypedef chapter of the C course.

The next thing is to create a structure queue which will store the front node, rear node and the total number of nodes in the linked list. This is similar to the picture given below:

You can see that the structure queue has three part count, front and rear as discussed above. The value of the count, in this case, is 3 as there are total 3 nodes. You can also see that front and rear are linked to the front and rear nodes respectively.

So, lets make the structure of this queue.

The next part is to initialize our queue and this will be done by making the count of the queue 0 and pointing rear and front to NULL.

So, lets do this.

Till now, we are up to this:

We can also check whether our queue is empty or not. The rear [or front] will be NULL for an emptyqueue. So, we can easily check whether a queue is empty or not by checking whether the rear is NULL or not.

The next and the most important operations on a queue are enqueue anddequeue. So, lets create them.

enqueue

The steps for the enqueue operations are:

1. Make a new node [node *tmp;tmp= malloc[sizeof[node]]].
2. Give the data of the new node its value [tmp-> data = value].
3. If the queue is empty then point both front and rear of the queue to this node [q->front = q->rear = tmp;].
   
4. If it is not, then point the rear of the queue to this new node and then make this new node rear [q->rear->next =tmp; q->rear =tmp;].
   
5. Increase the count ofqueue by 1.

The first step is to make a new node and we are doing the same by
node *tmp
tmp= malloc[sizeof[node]]

The second step is to give data of this new node its value and this we are doing withtmp-> data = value.

The third and the fourth steps are done by:
if[!isempty[q]]
{
q->rear->next = tmp;
q->rear = tmp;
}
else
{
q->front = q->rear = tmp;
}
The fourth step is to increase the count of the queue by 1 and we are doing this byq->count++.

You must have understood the enqueue operation. So, lets deal with the dequeue operation now.

dequeue

In dequeue operation, we delete the front node and returns its value. In order to do so, we need to make the front pointer point to the node next to the current front node but this will led the current front node inaccessible. So, we will first make a temporary pointer to the current front node and delete it using the free function later. The steps for the dequeue operations are:

1. Make a temporary node.
2. Point this temporary node to the front node of the queue.
3. Store the value of data of this temporary node in a variable.
4. Point the front pointer to the node next to the current front node.
5. Delete the temporary node using thefree function.
6. Return the value stored in step 3.

The code is very simple and just follows the steps mentioned above.

node *tmp Step 1

tmp= q->front Step 2

n = q->front->data Step 3

q->front = q->front->next Step 4

free[tmp] Step 5

return n Step 6

So, the overall code for a stack using linkedlist is:

Next:

• Making a queue using an array in C