Last Updated:

Writing a queue in Java

The data structure, which is called a queue in computer science, is somewhat similar to a stack, but in the queue the element inserted first is retrieved first. (FiFO data organization method, First-In-First-Out), while in the stack we saw that the element that was inserted last was removed first (the LIFO data organization method, Last-In-First-Out).

The queue works on the same principle as any queue in the cinema (the person who first got in line will be the first to reach the box office and buy a ticket). Accordingly, the one who will be the last in the queue will buy a ticket last (or will not buy it at all, if all tickets are sold out).

A queue is as much a programmer's help tool as a stack. They are used to simulate real situations of waiting for customers in the bank, departure of aircraft or data transmission over the Internet.

Where is the queue used?

In the operating system of your computer (and on the Internet), various queues are constantly working, imperceptibly performing their duties.

For example, in the print queue, documents are waiting for the printer to be released. Data entered from the keyboard is also stored in the queue.

If you are working in a text editor, and the computer is distracted by another operation, then the pressed will wait in the queue until the editor has free time to get them.

Implementing a Queue

Let's illustrate our turn. The first element in the queue is called Front, the element that finds the last element in the queue is Rear. The basis of our turn will be a classic array.

The two main operations with a queue are inserting an item at the end of the queue and removing an item from the beginning of the queue.

Graphic illustration of the insertion of the element (insert the number 7):

Let's remove the item from the queue start (321):

It is worth considering such a phenomenon as cyclic transfer. When you insert a new item, the Front marker moves up toward higher indexes. When items are deleted, the Rear handle also shifts upwards. The problem is that even if there are empty cells at the beginning of the array from which the elements were removed, you will not be able to insert a new element, because the Rear marker has nowhere to move on. Let's illustrate this situation:

 

To solve this problem with inserting into a queue in which there are free cells, the Front and Rear markers move to the beginning of the array when they reach the array boundary. This data structure is called a circular queue (or ring buffer).

 

Sample Queue in Java

Implement an array-based queue. Declare and initialize variables:

Implement the method of inserting an item into a queue (using round-robin migration):

Implement a method to remove an item from the queue start (using round-robin migration):

Just in case, here is a list of necessary heteros and methods for checking the queue for overflow or emptiness:

We implement the method and apply the above methods:main

So we see that everything is working correctly. First, insert elements 10, 20, 30, 40, 50. The next 3 executions of the method will leave 40, 50 in our queue. And finally we add 60 to the queue and get 40, 50, 60.

remove()