Queue

Queue is a data structure which implements ordering principle FIFO or first-in first-out. The essence of the principle FIFO is that the first element added to the queue will be the first one to be removed. To make things clear, let’s consider simple example from real life:

Queue-at-Check-In

On the picture above those who came first will be checked in first and that is FIFO. In computer science we can use queue there where we need to execute some actions in order of receipt.

Operations with queue

Adding a new element into the queue is usually called “enqueue”. Removing element from the queue is called “dequeue”.

Implementation

There are two approaches to implement queue:

1) Using linked list:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/LinkedListQueue.java

2) Using array:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/ArrayQueue.java

Complexity

Enqueue and dequeue operations have O(1) complexity.

Leave a Reply