Double-ended queue

This chapter won't be very long; it will expand on the previous one. Deque, or double-ended queue, helps work with queues from both the front and the back.

The Deque interface extends the Queue interface, so a class like LinkedList also implements this interface (I'm amazed at how versatile LinkedList is). Therefore, we will again use LinkedList, but this time with a new interface.

Declaring an object with the Deque type is no different from Queue:

The main difference comes into play when we move on to the methods of this interface. Since a Deque is a double-ended queue, meaning you can work with elements at both the front and the end of the queue, its methods are tailored to this feature.

Methods

Some key methods of the Deque interface are:

• addFirst(element): Adds an element to the beginning of the deque;
• addLast(element): Adds an element to the end of the deque.

Evidently, in a deque, there would be methods for adding to the beginning and the end. The names of these methods are self-explanatory.

Let's take a look at these methods in code:

As you can see, after using the addFirst() method, the element was added to the beginning of the deque. This distinguishes it from the addLast() method.

Deque also has a regular add() method, which functions the same as the addLast() method. Therefore, choosing which method to use is entirely up to you.

Let's move on!

Removal methods

If there are methods for adding elements to the beginning and the end, there should also be methods for removing from the beginning and the end of the deque.

• removeFirst(): Removes and returns the element from the beginning of the deque;
• removeLast(): Removes and returns the element from the end of the deque.

The addFirst() and addLast() methods perform the removal of elements from the beginning and the end of the deque. Let's take a look at an example of usage in the code:

As you can see, we removed the first and last elements from the deque, leaving only the second element. It's simple and convenient, and the method names speak for themselves.

Note

To ensure that your program and methods are equally understandable, it's worth giving them clear names. The name of a variable/method/class should indicate what that method does. Try to avoid names like "a," "var1/var2," and so on. With this approach to writing code, it will be much easier for you to work with your own methods.

Retrieving methods

Next, let's move on to the methods of retrieving elements from the deque.

• getFirst(): Returns, but does not remove, the element from the beginning of the deque;
• getLast(): Returns, but does not remove, the element from the end of the deque.

We can access the first and last elements in such a double-ended queue. Let's traditionally look at the implementation in the code:

Using the getFirst() and getLast() methods, we retrieved the first and last elements from the deque and assigned them to newly created variables.

In the Deque interface, there are also peekFirst() and peekLast() methods, which address the issue of throwing an exception. Instead of throwing an exception and halting the program, they return null if the queue is empty. Let's look at an example:

From this example, it became evident that it is much better to use the peekFirst() and peekLast() methods instead of using the getFirst() and getLast() methods, as they will not halt the program in case of an error.

However, don't forget about the NullPointerException! This exception can cause many issues in your program.

There are also equivalent alternative methods for the addFirst(), addLast(), removeFirst(), and removeLast() methods. We won't dwell on them for long, as you already understand the principle of how these methods work, but here is the list:

Alternative methods

Methods for adding an element to the beginning of the deque:

• offerFirst(E e): Adds an element to the beginning of the deque, if possible, and returns true. Returns false if addition is not possible;
• offerFirst(E e): Adds an element to the end of the deque, if possible, and returns true. Returns false if addition is not possible;
• push(E e): Adds an element to the beginning of the deque, similar to addFirst(). Note that push() is also a stack method in the Deque class.

Methods for removing an element from the beginning of the deque:

• pollFirst(): Removes and returns the first element of the deque. Returns null if the deque is empty;
• pollLast(): Removes and returns the last element of the deque. Returns null if the deque is empty;
• pop(): Removes and returns the first element of the deque, similar to removeFirst().

We've covered the main methods. Whether to use Queue or Deque is entirely up to you.

The choice depends on the program's requirements. You can always solve everything with a regular array, but it would be quite challenging, and I don't think it would be optimized. That's why so many different data structures are created solely for the convenience of writing various programs.

In the next chapter, we'll put queues into practice, and you'll see how convenient they are to work within the right context.