Fila Duplamente Encadeada

Deque, ou fila duplamente encadeada, permite trabalhar com filas tanto pela frente quanto pelo final.

A interface Deque estende a interface Queue, portanto, uma classe como LinkedList também implementa essa interface.

Assim, você utilizará novamente o LinkedList, mas desta vez com uma nova interface.

Declarar um objeto do tipo Deque não é diferente de Queue:

Main.java


              1
            
Deque<T> deque = new LinkedList<>();

A principal diferença surge quando analisamos os métodos desta interface.

Como um Deque é uma fila de duas extremidades, ou seja, é possível manipular elementos tanto no início quanto no final da fila, seus métodos são adaptados para essa característica.

Métodos

Alguns métodos principais da interface Deque são:

addFirst(element): adiciona um elemento ao início do deque;
addLast(element): adiciona um elemento ao final do deque.

Evidentemente, em um deque, existem métodos para adicionar no início e no final. Os nomes desses métodos são autoexplicativos. Vamos analisar esses métodos em código:

Main.java


              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);
    }
}

Como você pode ver, após usar o método addFirst(), o elemento foi adicionado ao início do deque. Isso o diferencia do método addLast().

O Deque também possui um método add() comum, que funciona da mesma forma que o método addLast(). Portanto, a escolha de qual método utilizar depende inteiramente de você.

Métodos de Remoção

Se existem métodos para adicionar elementos ao início e ao final, também devem existir métodos para remover do início e do final do deque.

removeFirst(): remove e retorna o elemento do início do deque;
removeLast(): remove e retorna o elemento do final do deque.

Os métodos addFirst() e addLast() realizam a remoção de elementos do início e do final do deque.

Vamos analisar um exemplo de uso no código:

Main.java


              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);
    }
}

Como pode ser observado, os primeiros e últimos elementos foram removidos do deque, restando apenas o segundo elemento.

É simples e conveniente, e os nomes dos métodos são autoexplicativos.

Métodos de Recuperação

Em seguida, vamos avançar para os métodos de acesso aos elementos em um deque.

getFirst(): recupera, mas não remove, o elemento na frente do deque;
getLast(): recupera, mas não remove, o elemento no final do deque.

Isso permite acessar os primeiros e últimos elementos em uma fila de duas pontas.

Agora, confira um exemplo em código:

Main.java


              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);
    }
}

Utilizando os métodos getFirst() e getLast(), os primeiros e últimos elementos foram recuperados da deque e atribuídos a variáveis recém-criadas.

Na interface Deque, também existem os métodos peekFirst() e peekLast(), que tratam a questão de lançar uma exceção. Em vez de lançar uma exceção e interromper o programa, eles retornam null se a fila estiver vazia.

Veja um exemplo:

Main.java


              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);
    }
}

A partir deste exemplo, ficou claro que é muito melhor utilizar os métodos peekFirst() e peekLast() em vez de getFirst() e getLast(), pois eles não interrompem o programa em caso de erro.

No entanto, não se esqueça da NullPointerException! Essa exceção pode causar muitos problemas no seu programa.

Também existem métodos alternativos equivalentes para os métodos addFirst(), addLast(), removeFirst() e removeLast(). Não vamos nos aprofundar neles, pois você já entende como esses métodos funcionam, mas aqui está a lista:

Métodos Alternativos

Métodos para adicionar um elemento ao deque:

offerFirst(E e): adiciona um elemento no início do deque, se possível, e retorna true. Retorna false se não for possível adicionar;
offerLast(E e): adiciona um elemento no final do deque, se possível, e retorna true. Retorna false se não for possível adicionar;
push(E e): adiciona um elemento no início do deque, semelhante ao addFirst(). Observe que push() também é um método de pilha na classe Deque.

Métodos para remover um elemento do deque:

pollFirst(): remove e retorna o primeiro elemento do deque. Retorna null se o deque estiver vazio;
pollLast(): remove e retorna o último elemento do deque. Retorna null se o deque estiver vazio;
pop(): remove e retorna o primeiro elemento do deque, semelhante ao removeFirst().

A escolha depende dos requisitos do programa. Sempre é possível resolver tudo com um array comum, mas seria bastante desafiador e não seria otimizado. É por isso que existem tantas estruturas de dados diferentes—para tornar a escrita de vários programas mais conveniente.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 2

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Deslize para mostrar o menu

Fila Duplamente Encadeada

Deque, ou fila duplamente encadeada, permite trabalhar com filas tanto pela frente quanto pelo final.

A interface Deque estende a interface Queue, portanto, uma classe como LinkedList também implementa essa interface.

Assim, você utilizará novamente o LinkedList, mas desta vez com uma nova interface.

Declarar um objeto do tipo Deque não é diferente de Queue:

Main.java


              1
            
Deque<T> deque = new LinkedList<>();

A principal diferença surge quando analisamos os métodos desta interface.

Como um Deque é uma fila de duas extremidades, ou seja, é possível manipular elementos tanto no início quanto no final da fila, seus métodos são adaptados para essa característica.

Métodos

Alguns métodos principais da interface Deque são:

addFirst(element): adiciona um elemento ao início do deque;
addLast(element): adiciona um elemento ao final do deque.

Evidentemente, em um deque, existem métodos para adicionar no início e no final. Os nomes desses métodos são autoexplicativos. Vamos analisar esses métodos em código:

Main.java


              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);
    }
}

Como você pode ver, após usar o método addFirst(), o elemento foi adicionado ao início do deque. Isso o diferencia do método addLast().

O Deque também possui um método add() comum, que funciona da mesma forma que o método addLast(). Portanto, a escolha de qual método utilizar depende inteiramente de você.

Métodos de Remoção

Se existem métodos para adicionar elementos ao início e ao final, também devem existir métodos para remover do início e do final do deque.

removeFirst(): remove e retorna o elemento do início do deque;
removeLast(): remove e retorna o elemento do final do deque.

Os métodos addFirst() e addLast() realizam a remoção de elementos do início e do final do deque.

Vamos analisar um exemplo de uso no código:

Main.java


              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);
    }
}

Como pode ser observado, os primeiros e últimos elementos foram removidos do deque, restando apenas o segundo elemento.

É simples e conveniente, e os nomes dos métodos são autoexplicativos.

Métodos de Recuperação

Em seguida, vamos avançar para os métodos de acesso aos elementos em um deque.

getFirst(): recupera, mas não remove, o elemento na frente do deque;
getLast(): recupera, mas não remove, o elemento no final do deque.

Isso permite acessar os primeiros e últimos elementos em uma fila de duas pontas.

Agora, confira um exemplo em código:

Main.java


              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);
    }
}

Utilizando os métodos getFirst() e getLast(), os primeiros e últimos elementos foram recuperados da deque e atribuídos a variáveis recém-criadas.

Veja um exemplo:

Main.java


              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);
    }
}

No entanto, não se esqueça da NullPointerException! Essa exceção pode causar muitos problemas no seu programa.

Métodos Alternativos

Métodos para adicionar um elemento ao deque:

offerFirst(E e): adiciona um elemento no início do deque, se possível, e retorna true. Retorna false se não for possível adicionar;
offerLast(E e): adiciona um elemento no final do deque, se possível, e retorna true. Retorna false se não for possível adicionar;
push(E e): adiciona um elemento no início do deque, semelhante ao addFirst(). Observe que push() também é um método de pilha na classe Deque.

Métodos para remover um elemento do deque:

pollFirst(): remove e retorna o primeiro elemento do deque. Retorna null se o deque estiver vazio;
pollLast(): remove e retorna o último elemento do deque. Retorna null se o deque estiver vazio;
pop(): remove e retorna o primeiro elemento do deque, semelhante ao removeFirst().

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 2

Estrutura de Dados Deque em Java

Fila Duplamente Encadeada

Métodos

Métodos de Remoção

Métodos de Recuperação

Métodos Alternativos

1. O que significa "Deque"?

2. Qual interface em Java representa um Deque?

3. Qual é a finalidade do método `addFirst()` em um Deque?

4. Qual método é utilizado para recuperar, mas não remover, o último elemento de um Deque?

Estrutura de Dados Deque em Java

Fila Duplamente Encadeada

Métodos

Métodos de Remoção

Métodos de Recuperação

Métodos Alternativos

1. O que significa "Deque"?

2. Qual interface em Java representa um Deque?

3. Qual é a finalidade do método `addFirst()` em um Deque?

4. Qual método é utilizado para recuperar, mas não remover, o último elemento de um Deque?

Estrutura de Dados Deque em Java

Fila Duplamente Encadeada

Métodos

Métodos de Remoção

Métodos de Recuperação

Métodos Alternativos

1. O que significa "Deque"?

2. Qual interface em Java representa um Deque?

3. Qual é a finalidade do método addFirst() em um Deque?

4. Qual método é utilizado para recuperar, mas não remover, o último elemento de um Deque?

Estrutura de Dados Deque em Java

Fila Duplamente Encadeada

Métodos

Métodos de Remoção

Métodos de Recuperação

Métodos Alternativos

1. O que significa "Deque"?

2. Qual interface em Java representa um Deque?

3. Qual é a finalidade do método addFirst() em um Deque?

4. Qual método é utilizado para recuperar, mas não remover, o último elemento de um Deque?

3. Qual é a finalidade do método `addFirst()` em um Deque?

3. Qual é a finalidade do método `addFirst()` em um Deque?