Data structures

Queue is a FIFO data structure. It is used in all situations where the values returned must be in the same order as values entered. We have discussed the terminologies, function needed and also implemented a queue in C language earlier. We can implement a queue by using an array or a linked list for storing values. Let us look at array implementation of a queue in C++ Data members We will need the array, front, rear and size of the array. We can use a static array or a dynamic array.  class Queue { static int size; int arr[ 40 ]; int front,rear; public: Queue(); void enqueue ( int num); int dequeue (); bool is_empty (); bool is_full (); void display (); static int ERR_EMPTY; }; int Queue :: ERR_EMPTY =- 9999 ; int Queue :: size = 40 ; Why are we using two static members in this class. size is the array size. And ERR_EMPTY is a constant which can be returned from dequeue function when the queue is empty. Const...

We have seen an introduction to Queue data structure and how to implement it using linked list. Now we shall try to implement the queue using an array. In linked list, front and rear were pointers to nodes with first element of the queue and last element of the queue respectively. In case of array, front is the  index of array which store first element of queue and rear is the index after the last element of the queue So how do we start the implementation. To start with set front and rear = 0 If front = rear, queue is empty. If rear = max , (max is size of array) queue is full enqueue If queue is not full set array[rear] to new value increment rear dequeue If queue is not empty set temp to array[front] increment front First let us write isEmpty() function which checks whether queue is empty by inspecting whether front is equal to rear int is_empty ( int front, int rear) { return front == rear; } Next to enqueue function we need to send array as a parameter, value to be in...