Data structures

In my previous posts, we have seen what is queue data structure and how to implement it using linked list and array Is this queue full? But we have seen that the array implementation had some problem - it would say "Queue is full" even when the queue was not full. In the image above, there are 3 slots free in the begining of the array. But as back (rear) is equal to size of array -1, the program will say - queue is full. One way of overcoming this is to implement a circular queue. That is once end of array is reached, go back to beginning of array and insert elements there. Like this. Image courtesy: maxtudor.com  As can be seen in this diagram, once we reach end of array, next element 11 is inserted at the beginning of array. Then we continue from there. We can say that index = rear % MAX array[index] = new_element Similarly when dequeuing, we can say that index = front % MAX temp = array[index] That way, when front and rear exceed MAX, they continue from 0. Is the queue fu...

Queue is a linear data structure to which values are added and removed using FIFO method - first in first out. That is to say, the value which is added first, will be removed first from the queue. Exactly like the behavior of a real life queue. The other related data structure is stack, from which elements are added and removed using LIFO method - last in first out. Terminology An element is always added to the rear end of the queue. This operation is called enqueue .  An element is added from the front end of the queue. The operation of removing an element is called dequeue operation. Implementation of queue You can implement a queue using an array or a linked list. Array poses the problem that it is limited by its size. But by making the array as circular, queue can be implemented. Here when the array index reaches maximum value, queue insertion happens at the beginning of the array. But implementation of a queue with linked list is not having such limitations. If you just add o...