Contenu du cours

Java Data Structures

1. Fundamental Data Structures in Java

Introduction to Data Structures List and ArrayList in Java Challenge: Library Management System CRUD Operations in Java LinkedList in Java Implementing LinkedList in Java Challenge: Implementing size and delete Methods in LinkedList Quiz: Fundamental Data Structures

2. Advanced Data Structures in Java

Queue Data Structure in Java Deque Data Structure in Java Challenge: Implementing a TaskManager Service Stack Data Structure in Java Challenge: Implementing BrowserHistory Quiz: Advanced Data Structures

3. Mastering Map in Java

What is Map?Working with HashMap in Java HashMap Practice in Java Map with Other Data Structures Quiz: Mastering Map

4. Advanced Java Features and Techniques

Working with Enum in Java Challenge: Implementing Character Classes Stream API in Java Method Reference in Java Practicing with Stream API Quiz: Enum and Stream API

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:

Main


              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:

Main


              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:

Main


              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:

Main


              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:

Main


              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.

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 2

Java Data Structures

Deque Data Structure in Java

Double-Ended Queue

Methods

Removal Methods

Retrieving Methods

Alternative Methods

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?

Java Data Structures

Deque Data Structure in Java

Double-Ended Queue

Methods

Removal Methods

Retrieving Methods

Alternative Methods

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?

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