Let's talk about two quite interesting data structures - Queue and Deque.

Queue

Let's start with a Queue. Imagine a queue in a store during a sale. There are 10 people; the first person is closer to the store doors than the others, and the 10th person is farthest away. When the first person enters the store, it exits the queue, thereby shifting the entire queue forward by one person. The Java Queue operates on a very similar principle.

This way, we can implement various programs where the queue logic is well-thought-out. For example, implementing a board with plans and tasks.

But first, let's take a look at the basic methods for working with a Queue.

Queue is an interface from which the LinkedList class inherits, which you are already familiar with, so we will use this implementation.

Note

Note that a class implementation (such as LinkedList) can inherit from certain interfaces and implement methods of these interfaces.

This way, we use the interface as the object's type, but the object's implementation will be LinkedList because it is a specific implementation of this object. (Remember that we cannot create objects based on an interface, right?)

Example:

This way, we can make our application very flexible by using various implementations of the same interface.

But let's get back to the methods of working with Queue.

Methods

Some key methods of the Queue interface are:

• add(element): Adds an element to the queue, throwing an exception if the operation is not possible;
• offer(element): Adds an element to the queue, returning true if successful or false otherwise.

You can notice that these methods essentially do the same thing. However, the key difference is the safety of the offer method. In case of an improperly added element, the offer method won't throw an exception and won't halt the program's execution.

But at the moment, this feature is not of great interest to us, as a regular Queue is not limited. However, there is a structure called BlockingQueue, which has a restriction on the number of elements; in that case, these methods will have a noticeable difference.

Let's look at an example:

As you can see, when using the add() method and trying to add an element that doesn't fit into the queue, the program throws an error, unexpectedly terminating the execution. Let's try the same operation but with a safer method - offer():

As you can see, now the element didn't get added to the queue, but it also didn't throw an exception. So, we can consider that we gracefully handled the error. We can handle exceptions differently using a structure like try-catch, but we'll discuss that later.

Note

Data structures like BlockingQueue, BlockingDeque, and similar ones are in the java.util.concurrent package and used for multithreaded programming. We will learn about Java multithreading in future courses.

Let's move on to the next methods:

Removal methods

• remove(): Removes and returns the element from the beginning of the queue, throwing an exception if the queue is empty;
• poll(): Removes and returns the element from the beginning of the queue, returning null if the queue is empty.

These methods precisely perform the function as if the first person in the queue entered the store and left the queue. This is where the FIFO (First In, First Out) principle comes into play. In other words, the element that was added first to the queue will be the first one removed.

Here, you can also observe the difference between these two methods. The poll() method is used more often than the delete() method because it is safer and does not throw exceptions.

Let's take a look at an example:

As you can see, the program throws a NoSuchElementException because we are trying to remove an element from an empty queue. To avoid such an exception, it's better to use the poll() method:

Now, we have safely removed an element from the queue, and no exception was thrown when we tried to remove an element from an empty list. Cool!

The poll() returning null feature can be used, for example, in a while() loop. Let's look at an example:

This way, we can remove all elements from the queue using a loop. Remember that the first element that entered the queue is the one removed! For example, in the case of the above example, the element with the data "One" was removed first. The FIFO principle is demonstrated below:

Great, we can move on to the methods that return the first and last elements:

• element(): Returns, but does not remove, the element from the beginning of the queue, throwing an exception if the queue is empty;
• peek(): Returns, but does not remove, the element from the beginning of the queue, returning null if the queue is empty.

Well, I think I don't need to explain for the third time that using the peek() method is much better, as it is safer and won't throw an exception.

Let's look at an example of usage:

You can combine this method with other queue methods. For example, if we have a queue with five elements and we need to remove all elements until the fourth one(inclusive), let's look at the implementation of such an operation:

We used a loop with a condition based on the peek() method. We can significantly optimize this loop by using the contains() method. This method returns true if the specified element is present in the queue and false if it is not.

Let's improve the above code:

Here, we set a single condition for the while loop. We successfully managed to remove all elements up to and including the "Four" element.

In the next chapters, you will learn about another similar data structure - Deque, and also write your own implementation of a Task Manager application.