Le Tutoriel de Java Deque

Deque
Les méthodes de Deque
Examples

1. Deque

Dequeest l'abréviation de "Double Ended Queue" (File d'attente à double extrémité). Comme les personnes faisant la queue au supermarché, seules la première et la dernière de la file d'attente sont servies. Deque offre un peu plus de flexibilité qu'une file d'attente normale.

public interface Deque<E> extends Queue<E>

Le Tutoriel de Java Queue

Deque est une sous-interface de Queue qui fournit des méthodes permettant d'insérer un élément au début ou à la fin, et celles susceptibles d'accéder ou de supprimer son premier ou dernier élément.

Deque inclut également des méthodes qui lui permettent d'agir comme une stack (pile) (Voir plus d'explications dans l'article).

Queue
BlockingDeque
BlockingQueue
TransferQueue
ArrayDeque
ConcurrentLinkedDeque
ConcurrentLinkedQueue
LinkedList
PriorityQueue
ArrayBlockingQueue
DelayQueue
LinkedBlockingQueue
LinkedBlockingDeque
PriorityBlockingQueue
SynchronousQueue
LinkedTransferQueue

2. Les méthodes de Deque

Methods of Deque

void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);

E removeFirst();
E removeLast();
E pollFirst();
E pollLast();

E getFirst();
E getLast();
E peekFirst();
E peekLast();

void push(E e);
E pop();

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

Iterator<E> descendingIterator();

// Methods inherited from Queue:

boolean add(E e);
boolean offer(E e);

E remove();
E poll();

E element();
E peek();

// Methods inherited from Collection:

boolean addAll(Collection<? extends E> c);  
boolean remove(Object o);
boolean contains(Object o);

int size();
Iterator<E> iterator();
...

La liste de 12 méthodes caractéristiques de Deque:

Insert	addFirst(E)	offerFirst(E)	addLast(E)	offerLast(E)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

boolean addFirst(E) / boolean offerFirst(E)

boolean addFirst(E)	Insérer un élément devant Deque, cette méthode lancera une exception si la capacité de Deque est pleine. Cette méthode renvoie à true si l'insertion réussit.
boolean offerFirst(E)	Insérer un élément devant Deque. Si la capacité de Deque est déjà pleine ou l'insertion échoue, la méthode renverra à false, sinon true.

Remarque: En fonction du type de Deque, il peut limiter (ou non) le nombre d'éléments.

boolean addLast(E) / boolean offerLast(E)

boolean addLast(E)	Insérer un élément à la fin de Deque. Cette méthode lancera une exception si la capacité de Deque est pleine. La méthode renvoie true si l'insertion réussit.
boolean offerLast(E)	Insérer un élément à la fin de Deque. Si la capacité Deque est pleine ou si l'insertion échoue, la méthode renverra false, sinon true.

E removeFirst() / E pollFirst()

E removeFirst()	Renvoyer le premier élément de Deque et le supprimer de Deque. Cette méthode lancera une exception si Deque ne dispose d'aucun élément.
E pollFirst()	Renvoyer le premier élément de Deque et le supprimer de Deque. Cette méthode renverra null si Deque ne dispose d'aucun élément.

E removeLast() / E pollLast()

E removeLast()	Renvoyer le dernier élément de Deque et le supprimer de Deque. Cette méthode lancera une exception si Deque ne dispose d'élément.
E pollLast()	Renvoyer le dernier élément de Deque et le supprimer de Deque. Cette méthode renverra null si Deque ne dispose d'élément.

E getFirst() / E peekFirst()

E getFirst()	Renvoyer le premier élément de Deque mais ne le supprimer pas de Deque. Cette méthode lance une exception si Deque ne dispose d'élément.
E peekFirst()	Renvoyer le premier élément de Deque mais ne le supprimer pas de Deque. Cette méthode renvoie null si Deque ne dispose d'aucun élément.

E getLast() / E peekLast()

E getLast()	Renvoyer le dernier élément de Deque mais ne le supprimer pas de Deque. Cette méthode lancera une exception si Deque ne dispose d'aucun élément.
E peekLast()	Renvoyer le dernier élément de Deque mais ne le supprimer pas de Deque. Cette méthode renvoie null si Deque n'a aucun élément.

Methods inherited from Queue:

Les méthodes héritées de Queue et les méthodes correspondantes dans Deque:

booleanadd(E)	booleanaddLast(E)	(*)
booleanoffer(E)	booleanofferLast(E)	(*)
E remove()	E removeFirst()
E poll()	E pollFirst()
E element()	E getFirst()
E peek()	E peekFirst()

(*) - Dans la plupart des types de Queue, les méthodes add(E) et offer(E) insèrent un élément à la fin. Mais ce n'est pas le cas pour PriorityQueue, car PriorityQueue spécifie la position de l'élément inséré en fonction de sa priorité.

Le Tutoriel de Java PriorityQueue

Stack?

Deque peut agir comme une stack (pile), car il fournit des méthodes pour travailler avec le mécanisme LIFO (Last In First Out).

boolean push(e)	boolean addFirst(e)
E pop()	E removeFirst()
E peek()	E getFirst()

3. Examples

Deque est une interface, donc pour créer un objet Deque, il faut utiliser l'une de ses sous-classes, telles que ArrayDeque, ConcurrentLinkedDeque, LinkedList, LinkedBlockingDeque.

Deque<String> deque = new ArrayDeque<>();

Deque<String> deque = new LinkedList<>();

La classe Customer sera présente dans ces exemples:

Customer.java

package com.o7planning.deque.ex;

public class Customer {
    private Integer cusId;
    private String cusName;
    
    public Customer(Integer cusId, String cusName) {
        super();
        this.cusId = cusId;
        this.cusName = cusName;
    }
    public Integer getCusId() {
        return cusId;
    }
    public String getCusName() {
        return cusName;
    }
}

DequeEx1.java

package com.o7planning.deque.ex;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeEx1 {

    public static void main(String[] args) {
        
        // Create a Deque with maximum capacity of 10 elements.
        Deque<Customer> deque = new ArrayDeque<Customer>(10);
        
        deque.addFirst(new Customer(1, "Tom"));
        deque.addFirst(new Customer(2, "Jerry"));
        deque.addLast(new Customer(3, "Donald"));
        
        Customer current = null;
        
        // Retrieve first element and remove it from Deque.
        while((current = deque.pollFirst())!= null) {
            System.out.println("Serving customer: " + current.getCusName());
        }
    }
}

Output:

Serving customer: Jerry
Serving customer: Tom
Serving customer: Donald

Deque peut être utilisé comme une stack (pile). Observer cet exemple de cartes de simulation:

DequeStackEx1.java

package com.o7planning.deque.ex;

import java.util.Deque;
import java.util.LinkedList;

public class DequeStackEx1 {

    public static void main(String[] args) {
        // Create a Deque to use as a Stack.
        Deque<String> stackOfCards = new LinkedList<>();

        // Pushing new items to the Stack
        stackOfCards.push("Jack");
        stackOfCards.push("Queen");
        stackOfCards.push("King");
        stackOfCards.push("Ace");

        System.out.println("Stack => " + stackOfCards);
        System.out.println();
 
        // Popping items from the Stack
        String cardAtTop = stackOfCards.pop();  // Throws NoSuchElementException if the stack is empty
        System.out.println("Stack.pop() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
        System.out.println();

        // Get the item at the top of the stack without removing it
        cardAtTop = stackOfCards.peek();
        System.out.println("Stack.peek() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
    }
}