Queue

What is Queue?

Queue is an abstract data type. Now saying abstract means that we only worry about the operations provided by the queue, don’t worry about implementation. Of course we have to implement it. It is implemented with the help of an array or linked list. It works on the concept of “First In First Out”. Let’s understand the concept of queue by an example. Suppose you have to deposit the cash into your account. You go to the bank and stand in a queue at the deposit counter. It’s one of the real life examples. That’s how the queue works. The customer who came first will be given a chance to deposit the case. You have to wait until your frontiers are not deposited. The basic operation of queue are: enqueue(), dequeue() and peek().

Enqueue Operation:

We have to simply add the new element at the end of the queue. It’s very simple and can be done in O(1).

queue.enqueue(10)
10

queue.enqueue(20)
20 10

queue.enqueue(30)
30 20 10

Dequeue Operation:

We just have to simply remove the element from the front(the opposite site from where element is added). Or In simple words from the starting at the beginning of the queue. It can be done in O(1).

queue.dequeue();
30 20 10
queue.dequeue();
30 20

queue.dequeue();
30 20
queue.peek()=10
30

Peek Operation:

Peek operation just tells the value of the front element. It does not remove any element from the queue. It’s simple and can be done in O(1).

queue.peek() = 10
30 20 10

Application:

  • In the BFS algorithm, It is used as the underlying data structure.
  • In CPU scheduling, when a resource is shared among several
    threads. We store them in a queue.