Interfaz Java Deque

Java Deque es una estructura de datos que combina una cola y una pila ordinarias. Puede agregar y eliminar elementos tanto en la cabeza como en la cola del Deque. En la cola "tradicional", agrega elementos al final de la línea (después del último elemento) y elimina elementos del principio de la cola. Este principio se llama First In First Out (FIFO) y funciona como cualquier línea habitual de clientes en la vida real. En Java Queue es una interfaz, una parte de Collections Framework. También hay una estructura de datos importante llamada Stack, una lista que funciona con elementos en un principio totalmente inverso, LIFO: último en entrar, primero en salir. Es similar a una pila de platos, agregar o quitar solo es posible en la parte superior.

Cola vs Deque

Deque es un tipo de cola un poco extraño: puedes agregar nuevos elementos tanto en la cola como en la cabeza de la línea. La misma historia con la eliminación: puede eliminar el último o el primer elemento de esta estructura. Por lo tanto, parece ser una mezcla de Stack y Queue. El nombre "Deque" significa "Cola de doble terminación". “Deque” se pronuncia como una “baraja” de cartas y ¿sabes qué? Es algo similar a una baraja de cartas real: puede tomar una carta de la parte inferior o superior de dicha baraja. ¿Quiere agregar o eliminar elementos de ambos lados de alguna estructura lineal? Usa Deque. Java 8 o casi cualquier otra versión lo admite. Imagine un ladrillo de lego típico y "torres" de una columna hechas de ladrillos. Puede agregar un nuevo ladrillo en la parte superior de la torre o en la parte inferior. También puede quitar un ladrillo de ambos lados. Aquí tenemos un ejemplo: agregamos todos los ladrillos amarillos en la parte superior y todos los rojos en la parte inferior. Demostraremos este ejemplo con código Java pronto. Entonces puede poner en cola y quitar de la cola desde ambos extremos de un Java Deque, eso significa que puede usar un Deque como cola y pila. Lea sobre Stack en Java: Java Stack 101: Profundizando en la clase Stack Lea sobre Queue en Java: Java Queue Interface y sus implementaciones

Características de Deque

• Deque en Java es una interfaz, cuyas implementaciones brindan el soporte de una matriz redimensionable. Por lo tanto, tiene una matriz de capacidad libre de restricciones y puede agregar nuevos elementos de acuerdo con sus necesidades.
• Deque no admite el acceso simultáneo de varios subprocesos
• Deque no es seguro para subprocesos en caso de ausencia de sincronización externa.
• No se permiten elementos nulos en la matriz deque.

Declaración de la interfaz Java de Deque

public interface Deque<E> extends Queue<E>

Métodos Java Deque

java.util.Deque es una interfaz que amplía la interfaz de cola de Java y representa una cola de dos extremos. Entonces puede usar todos los métodos de Java Queue mientras trabaja con un Deque. A pesar de que Deque no amplía la interfaz de pila, la interfaz de Deque define métodos que le permiten realizar operaciones típicas de pila como empujar , mirar y sacar .

• boolean add(element) agrega un elemento a la cola del Deque. Devuelve verdadero en caso de éxito, arroja una IllegalStateException si no hay espacio disponible actualmente.
• addFirst(element) agrega un elemento al encabezado de Deque.
• addLast(element) agrega un elemento a la cola de Deque.
• oferta (elemento) agrega un elemento a la cola y devuelve un valor booleano para explicar si la inserción fue exitosa.
• ofrecerPrimero(elemento) agrega un elemento al encabezado y devuelve un valor booleano para explicar si la inserción fue exitosa.
• offerLast(element) agrega un elemento al final y devuelve un valor booleano para explicar si la inserción fue exitosa.
• iterator() devuelve un iterador para el deque.
• descendingIterator() devuelve un iterador que tiene el orden inverso para este deque.
• push(element) agrega un elemento a la cabeza.
• pop(elemento) elimina un elemento de la cabecera y lo devuelve.
• removeFirst() elimina el elemento en la cabecera.
• removeLast() elimina el elemento en la cola.
• poll() recupera y elimina la cabeza de la cola representada por este deque (en otras palabras, el primer elemento de este deque), o devuelve un valor nulo si este deque está vacío.
• pollFirst() recupera y elimina el primer elemento de este deque, o devuelve un valor nulo si este deque está vacío.
• pollLast() recupera y elimina el último elemento de esta deque, o devuelve un valor nulo si esta deque está vacía.
• peek() recupera, pero no elimina, la cabeza de la cola representada por este deque (en otras palabras, el primer elemento de este deque), o devuelve un valor nulo si este deque está vacío.
• peekFirst() recupera, pero no elimina, el primer elemento de este deque, o devuelve un valor nulo si este deque está vacío.
• peekLast() recupera, pero no elimina, el último elemento de esta deque, o devuelve un valor nulo si esta deque está vacía.

Aquí, en la siguiente tabla, todos los métodos están divididos por grupos. Como puede ver, hay muchos métodos diferentes para agregar y eliminar un elemento. Por ejemplo, tanto removeFirst() como pop() eliminan el primer elemento de deque. El segundo "vino" de la pila. Eso significa que si usa su ArrayDeque solo como una pila, use pop() para eliminar, push() para agregar y peek() para examinar. Esto hace que su código sea más sensible para otros desarrolladores.

Implementaciones de Deque

Java Deque es una interfaz y tiene implementaciones en Java Collections API:

• java.util.LinkedList //List y Deque implementación
• java.util.ArrayDeque //Implementación de Deque, biblioteca Java

La clase LinkedList usa una lista de doble enlace internamente para modelar una cola o una cola. La clase ArrayDeque almacena los elementos internamente en una matriz. Si el número de elementos supera el volumen de la matriz, se asigna una nueva matriz y se mueven todos los elementos. Eso significa que ArrayDeque crece según las necesidades.

clase ArrayDeque

La clase ArrayDeque <E> es una cola bidireccional general, que hereda la funcionalidad de la clase AbstractCollection y utiliza la interfaz Deque. ArrayDeque proporciona la facilidad de usar deque y matriz de tamaño variable. Inicialmente, la matriz se inicializa con el tamaño 16. Se implementa como una cola bidireccional, donde admite dos punteros, a saber, la cabeza y la cola. Hereda la clase AbstractCollection e implementa la interfaz Deque . Los puntos importantes sobre la clase ArrayDeque son:

• Puede agregar o eliminar elementos de la cola y la cabeza del ArrayDeque
• No se permiten elementos nulos
• ArrayDeque no es seguro para subprocesos, en ausencia de sincronización externa.
• ArrayDeque no tiene restricciones de capacidad.

Constructores de la clase ArrayDeque

• ArrayDeque() crea una cola vacía.
• ArrayDeque (Collection <? Extends E> collection) crea una cola llena de elementos de la colección Collection.
• ArrayDeque (capacidad int) crea una cola con capacidad de capacidad inicial . Si no especifica la capacidad inicial, la capacidad predeterminada es 16.

Ejemplo de Java Deque — ArrayDeque

¿Recuerdas el ejemplo de la torre Lego del principio del artículo? Vamos a crear una clase para construir torres de una columna hechas de piezas de Lego. Los ladrillos pueden ser rojos, amarillos o azules. Nuestra regla de construcción de torres: colocamos los ladrillos rojos en la parte inferior y los ladrillos amarillos en la parte superior. Gran ejemplo de Java Deque

//enum with colors 
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color   
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Aquí está nuestra clase Tower. Iniciamos una torre. La torre iniciada depende de la cantidad de rojos y amarillos. Podemos añadir ladrillo a la torre o quitarlo. Agregamos ladrillo arriba si es amarillo y lo agregamos abajo si es rojo.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here 
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

El resultado de ejecutar este programa:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements: 
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

¿¿Esperar lo?? ¿Por qué están los rojos en la parte superior? No, no lo hacen. Simplemente se imprimieron en la consola desde el primero (abajo) hasta el último (arriba). Entonces, si desea ver algo como en la imagen con los ladrillos de arriba, puede cambiar el método drawTower de la clase LegoTower. ¡Es una tarea muy fácil!

Lista enlazada

La interfaz de Lista mantiene la secuencia de adición de elementos y permite el acceso al elemento por índice. Deque es una cola bidireccional y admite agregar y eliminar elementos de ambos lados. LinkedList se conoce principalmente como una implementación de Lista, pero también esta clase implementa Deque, y nos permite crear una cola bidireccional que consiste en cualquier objeto, incluido nulo. LinkedList es una colección de elementos. Lo podemos ver en el código fuente de la clase, esta vez presta atención a los campos: Aquí agregamos un ejemplo, pero si quieres aprender más sobre LinkedList, bienvenido a este artículo de CodeGym .

Implementación de listas enlazadas en Java, agregando y eliminando elementos. Ejemplo

Probemos estas operaciones en la práctica. Primero, la implementación de Java LinkedList: creando una LinkedList of Strings, agregando allí 3 elementos. Luego quite uno, luego agregue uno en el medio.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

El resultado de ejecutar este programa:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]