Course Content
Java Data Structures
Java Data Structures
Deque
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
:
main
Deque<T> deque = new LinkedList<>();
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:
main
package com.example; import java.util.Deque; import java.util.LinkedList; public class Main { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); deque.addFirst("One"); deque.addLast("Two"); System.out.println("Deque: " + deque); deque.addFirst("Zero"); System.out.println("Deque after the `addFirst()` method: " + deque); } }
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:
main
package com.example; import java.util.Deque; import java.util.LinkedList; public class Main { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); deque.add("One"); deque.add("Second"); deque.add("Third"); System.out.println("Deque: " + deque); deque.removeFirst(); deque.removeLast(); System.out.println("Deque after the removal methods method: " + deque); } }
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:
main
package com.example; import java.util.Deque; import java.util.LinkedList; public class Main { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); deque.add("One"); deque.add("Second"); deque.add("Third"); System.out.println("Deque: " + deque); String first = deque.getFirst(); String last = deque.getLast(); System.out.println("The first element in the deque: " + first); System.out.println("The last element in the deque: " + last); } }
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:
main
package com.example; import java.util.Deque; import java.util.LinkedList; public class Main { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); System.out.println("Deque: " + deque); String first = deque.peekFirst(); System.out.println("The first element in the deque: " + first); String last = deque.getLast(); System.out.println("The last element in the deque: " + last); } }
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 returnstrue
. Returnsfalse
if addition is not possible;offerFirst(E e)
: Adds an element to the end of the deque, if possible, and returnstrue
. Returnsfalse
if addition is not possible;push(E e)
: Adds an element to the beginning of the deque, similar toaddFirst()
. Note thatpush()
is also a stack method in theDeque
class.
Methods for removing an element from the beginning of the deque:
pollFirst()
: Removes and returns the first element of the deque. Returnsnull
if the deque is empty;pollLast()
: Removes and returns the last element of the deque. Returnsnull
if the deque is empty;pop()
: Removes and returns the first element of the deque, similar toremoveFirst()
.
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.
Thanks for your feedback!