Dynamic queues in C language.

What Will I Learn?

• create a dynamic queue in c language.
• create a node.
• adds a node to the queue.
• extracts a node to the queue.
• destroy the queue and its nodes.

https://sistemasumma.files.wordpress.com/2014/08/dev-c.png
photocredit

Requirements

• Laptop
• Dev-C++ (C/C++ IDE)

Difficulty

• Intermediate

Tutorial Contents

• Pointers
  A pointer is a variable that contains the memory address of a data or other variable.Pointers can be used to reference and manipulate data structures, to reference dynamically assigned memory blocks and to provide the passage of arguments by references in function calls.
• Structs
  A struct in C is a composite data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory, allowing the different variables to be accessed via a single pointer, or the struct declared name which returns the same address.
• Queue
  A queue is a structure in which elements are stored (in order of arrival), that is, the elements are entered by the end of the structure and eliminated (or served) by the front part. this structure has two pointers, one pointing to the last element and the other pointing to the first elemeto (or the front element).
  A queue is a special type of open list. This type of list is known as the FIFO list (First In First Out) .

In the following image we will see a diagram of a queue.

http://www.cs.grinnell.edu/~walker/courses/201.sp05/labs/queues1.gif
Photocredit

now we are going to do the implementation in c of the queue.
The text code implemented and explained step by step is shown below.

---

#include <stdlib.h>
#include <stdio.h>

/*
First we define two structures, one for the queue nodes and other for the queue itself

The structure of the queue nodes needs to have all the attributes desired, in this case,
we only want a number because we have to create a queue of entire numbers. The nodes also
need a pointer to the next node. The last node of a queue always points to NULL
/
typedef struct node_str
{
int number;
struct node_str next;

}node_t;

typedef node_t* node;
/*
The structure of the queue needs two pointers, one to the first node and other to the last node
This is because we want to add nodes at the end of the queue and extract them from the beggining
*/
typedef struct queue_str
{
node first;
node last;

}queue_t;

typedef queue_t* queue;

/*
We will be working with pointers because we have to use dynamic memory (the size of a queue used
to be unkonwn). That's why we create the pointer types of the structures defined above
*/

/*
This function reserves the memory space to the node n and assigns the number that we want to add
Remember that the last node always points to NULL, so when we create a node, we assing the next
pointer to NULL
*/
node new_node(int num)
{
node n;
n=(node)malloc(sizeof(node_t));
n->number = num;
n->next = NULL;
return n;
}

/*
This function reserves the memory space to the queue q and assigns NULL to the first and last pointer
because a new queue is empty so it doesn't have nodes
*/
queue new_queue()
{
queue q;
q=(queue)malloc(sizeof(queue_t));
q->first = NULL;
q->last = NULL;
return q;
}

/*
This function adds a number to the queue. So inside it, we create a node with the number num.
If the first node pointer of the queue points to NULL, means that the queue is empty, so
both pointers (first and last) have to point to the new node.
In other case we have to add the node at the end (queue->last->next), and then point the last
pointer to the new end of the queue (queue->last = queue->last->next)
*/
void add_queue_node(queue q , int num)
{
node n = new_node(num);
if (q->first == NULL)
{
q->first = n;
q->last = n;
}
else
{
q->last->next = n;
q->last = q->last->next;
}

}

/*
This function extracts a number to the queue.
If the first node pointer of the queue points to NULL, means that the queue is empty, so we don't
extract any node.
If it doesn't point to NULL, we assing the first node to an auxiliary variable because we are going
to lose the reference to that node.
Then we change the first pointer to the next node of the queue.
After that, we save the node's information into the variable n and free the node's allocated memory
It is important to save the value before losing the reference of the pointer.
Finally the node extracted is returned so we can use it's attributes for whatever we want
*/
node_t extract_queue_node(queue q)
{
node aux;
node_t n;
if (q->first != NULL)
{
aux = q->first;
q->first = q->first->next;
n = *aux;
free(aux);
}
return n;
}

/*
Before the program's end, it is necessary to destroy the queue and its nodes and liberate the
allocated memory. So we use the extract_queue_node function to liberate all the nodes and print
the numbers (this is not necessary, just for example)
Finally we also liberate the memory allocated for the queue
*/
void destroy_queue(queue q)
{
node_t n;
while(q->first != NULL)
{
n = extract_queue_node(q);
printf("%d\n", n.number);
}
free(q);
}

int main()
{
queue q = new_queue();
add_queue_node(q,1); //we add an element
add_queue_node(q,2); //we add an element
add_queue_node(q,3); //we add an element
add_queue_node(q,4); //we add an element
extract_queue_node(q); //we extract an element
destroy_queue(q);
return 0;
}

---

Now let's show how the queue works.

Work Result

first the queue is created, then 4 elements are added to the queue. An element of the queue is extracted according to FIFO (First In First Out) rules and finally the queue is destroyed.

This is the code part of the main function.

---

int main()
{
queue q = new_queue();
add_queue_node(q,1); //we add an element
add_queue_node(q,2); //we add an element
add_queue_node(q,3); //we add an element
add_queue_node(q,4); //we add an element
extract_queue_node(q); //we extract an element
destroy_queue(q);
return 0;
}

---

the final result is as follows:

the elements added to the queue are numbers 1 2 3 and 4.
after extracting an element from the queue, the number 1 is the first one to exit since it was the first one to enter

If we extract another element, number 2 is the next one out.
we will modify the main function to extract another element

---

int main()
{
queue q = new_queue();
add_queue_node(q,1); //we add an element
add_queue_node(q,2); //we add an element
add_queue_node(q,3); //we add an element
add_queue_node(q,4); //we add an element
extract_queue_node(q); // we extract an element
extract_queue_node(q); //we extract an element
destroy_queue(q);
return 0;
}

---

the final result for this test is as follows:

try to run the code and start to learn.

Curriculum

my previous contributions are as follows:

• Tutorial 1
• Tutorial 2
• Tutorial 3
• Tutorial 4

Collaborations:

• conclase
• trukazo

---

Posted on Utopian.io - Rewarding Open Source Contributors

---