Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Learn Deque Data Structure in Java | Advanced Data Structures in Java
Java Data Structures
course content

Course Content

Java Data Structures

Java Data Structures

1. Fundamental Data Structures in Java
Introduction to Data StructuresList and ArrayList in JavaChallenge: Library Management SystemCRUD Operations in JavaLinkedList in JavaImplementing LinkedList in JavaChallenge: Implementing size and delete Methods in LinkedListQuiz: Fundamental Data Structures
2. Advanced Data Structures in Java
Queue Data Structure in JavaDeque Data Structure in JavaChallenge: Implementing a TaskManager ServiceStack Data Structure in JavaChallenge: Implementing BrowserHistoryQuiz: Advanced Data Structures
3. Mastering Map in Java
What is Map?Working with HashMap in JavaHashMap Practice in JavaMap with Other Data StructuresQuiz: Mastering Map
4. Advanced Java Features and Techniques
Working with Enum in JavaChallenge: Implementing Character ClassesStream API in JavaMethod Reference in JavaPracticing with Stream APIQuiz: Enum and Stream API

book
Deque Data Structure in Java

Double-Ended Queue

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.

Therefore, you will again use LinkedList, but this time with a new interface.

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

java

Main

copy

              
1

            
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:

java

Main

copy

              
123456789101112131415

            
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.

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:

java

Main

copy

              
1234567891011121314151617

            
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.

Retrieving Methods

Next, let's move on to the methods for accessing elements in a deque.

  • getFirst(): retrieves, but does not remove, the element at the front of the deque;
  • getLast(): retrieves, but does not remove, the element at the end of the deque.

This allows us to access the first and last elements in a double-ended queue.

Now, let's check out an example in code:

java

Main

copy

              
123456789101112131415161718

            
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:

java

Main

copy

              
123456789101112131415

            
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 getFirst() and getLast(), as they won't 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 how these methods work, but here's the list:

Alternative Methods

Methods for adding an element to 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;
  • offerLast(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 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().

The choice depends on the program's requirements. You can always solve everything with a regular array, but it would be quite challenging, and it wouldn't be optimized. That's why so many different data structures exist—to make writing various programs more convenient.

1. What does "Deque" stand for?

2. Which interface in Java represents a Deque?

3. What is the purpose of the addFirst() method in a Deque?

4. Which method is used to retrieve, but not remove, the last element of a Deque?

question mark

What does "Deque" stand for?

Select the correct answer

question mark

Which interface in Java represents a Deque?

Select the correct answer

question mark

What is the purpose of the addFirst() method in a Deque?

Select the correct answer

question mark

Which method is used to retrieve, but not remove, the last element of a Deque?

Select the correct answer

Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 2. Chapter 2
We're sorry to hear that something went wrong. What happened?
some-alt