Queue Data Structure


The queue data structure is also considered as a collection of elements of similar data types that are arranged in a linear order. In queue data structure the elements are inserted from one end and are deleted from another end. Tail or rear is the end to which the elements are inserted in a queue data structure.

And head or front is the end from which the elements are deleted. The queue data structure follows FIFO that is first in, first out which means that the element that is inserted first will be deleted first. The process through which an element is added in a queue is called Enqueue and the process in which the elements are removed from the queue is called Dequeue.


Dequeue


Basic Features of Queue:

The following are some basic features of queue data structure:

  1. The queue data structure is also considered as a collection of elements of similar data types that are arranged in a linear order.
  2. Queue data structure follows FIFO that is first in, first out.
  3. If we have inserted a new element in the queue and the queue have other elements before also. Then to remove the new element from the queue, first we have to remove all the previous elements.
  4. There is a function implemented in queue data structure named peek () which is used to return the value of the new element without dequeuing it.


Applications of Queue:

There are many applications of queue data structure for example queue can be used in simulation. Queue can also be used in call centre phone.


Implementation of Queue:

A queue data structure can be implemented by using stack, array or linked list. The easiest way to implement queue is by using array. In queue data structure the head and the tail are at the same index that is 0 initially. Then whenever an element is inserted tail moves forward. The tail thus points to the position where the next new element is inserted but the head will remain at the same position that is at index 0.

Consider the following figure in which the head and tail in a queue are at same position initially:

position initially

Suppose at index 0 we inserted an element, then the tail will move forward. Consider the following figure:

2

As we are inserting elements into array the tail is moving in the forward direction accordingly:

forward direction accordingly

The following is the code in which queue is implemented in C++ programming language:

CODE:

# include < iostream. h >

# include < conio. h >

class queue

{

private:

int array [5];

int top;

int queue;

public:

queue ();

void enqueue (int d);

int dequeue ();

};

queue : : queue ()

{

array [top] = 0;

queue = 0;

}

void queue :: enqueue (int d)

{

array [top] = d;

top ++;

}

int queue :: dequeue ()

{

queue ++;

return array [queue];

}

void main ()

{

clrscr ();

queue q;

  1. enqueue (1);
  2. enqueue (2);

cout << q. dequeue ();

  1. enqueue (3);

cout << q. dequeue ();

getch ();

}

In the above code first we have declared an array. Then using the enqueue function we are inserting elements into the array of queue and by using the dequeue function these elements are deleted from the queue. The further working of queue has already been explained.


Analysis of Queue:

The following are the time complexities for the basic operations that can be applied on queue data structure:

Enqueue operation:

The time complexity for enqueue operation is O (1).

Dequeue operation:

The time complexity for dequeue operation is O (1).