Estructuras de datos en Java: pila y cola

¡Hola! Hoy hablaremos de cosas tan importantes para cualquier programador como las estructuras de datos . Wikipedia dice: La estructura de datos ( ing. estructura de datos ) es una unidad de software que le permite almacenar y procesar muchos datos del mismo tipo y/o relacionados lógicamente en informática. La definición es un poco confusa, pero su esencia es clara. Una estructura de datos es un tipo de almacenamiento donde almacenamos datos para su uso posterior. Existe una gran variedad de estructuras de datos en programación. Muy a menudo, a la hora de resolver un problema concreto, lo más importante es elegir la estructura de datos más adecuada para tal fin. ¡Y muchos de ellos ya los conoces! Por ejemplo, con matrices . Y también con Map(que suele traducirse como “diccionario”, “mapa” o “matriz asociativa”). Es muy importante entender: las estructuras de datos no están ligadas a ningún lenguaje específico . Estos son simplemente "planos" abstractos según los cuales cada lenguaje de programación crea sus propias clases, implementaciones de esta estructura. Por ejemplo, una de las estructuras de datos más famosas es la lista enlazada . Puedes ir a Wikipedia, leer sobre cómo funciona, qué ventajas y desventajas tiene. Puede que su definición le resulte familiar :) “Una lista enlazada es una estructura de datos dinámica básica en informática, que consta de nodos, cada uno de los cuales contiene tanto los datos en sí como uno o dos enlaces (“enlaces”) al siguiente y/o lista de nodos anterior” ¡ Así que esto es nuestro LinkedList! Exactamente, así es :) La estructura de datos de la lista vinculada se implementa en el lenguaje Java en la clase LinkedList. ¡Pero otros idiomas también implementan listas enlazadas! En Python se llama " llist", en Scala se llama igual que en Java: " LinkedList". Una lista enlazada es una de las estructuras de datos básicas comunes, por lo que puedes encontrar su implementación en cualquier lenguaje de programación moderno. Lo mismo ocurre con una matriz asociativa. Aquí está su definición de Wikipedia: Una matriz asociativa es un tipo de datos abstracto (una interfaz para un almacén de datos) que permite almacenar pares de la forma "(clave, valor)" y admite las operaciones de sumar un par, así como la búsqueda. y eliminar un par por clave. ¿No te recuerda a nada? :) Exactamente, para nosotros los javaistas, una matriz asociativa es una interfazMap. ¡Pero esta estructura de datos también se implementa en otros idiomas! Por ejemplo, los programadores de C# lo conocen con el nombre de “Diccionario”. Y en el lenguaje Ruby se implementa en una clase llamada “Hash”. En general, comprenderá a grandes rasgos cuál es el significado: una estructura de datos es algo común a toda la programación, que se implementa de manera diferente en cada lenguaje específico. Hoy estudiaremos dos de estas estructuras y veremos cómo se implementan en Java: pila y cola.

Apilar en Java

Una pila es una estructura de datos conocida. Es muy sencillo y muchos objetos de nuestra vida diaria se “implementan” en forma de pila. Imagine una situación sencilla: vive en un hotel y durante el día recibe cartas comerciales. Como usted no estaba en la habitación en ese momento, el empleado del hotel simplemente puso las cartas entrantes sobre su mesa. Primero puso la primera carta sobre la mesa. Luego vino el segundo y lo puso encima del primero. Colocó la tercera letra que llegó encima de la segunda y la cuarta encima de la tercera. Ahora, responde una pregunta simple: ¿qué carta leerás primero cuando llegues a tu habitación y veas una pila sobre la mesa? Así es, leerás la letra superior. Es decir, el que llegó último en el tiempo . Así es exactamente como funciona una pila. Este principio de funcionamiento se llama LIFO - "último en entrar, primero en salir" ("último en entrar, primero en salir"). ¿Para qué puede ser útil una pila? Por ejemplo, estás creando algún tipo de juego de cartas en Java. Sobre la mesa hay una baraja de cartas. Las cartas jugadas se descartan. Puedes implementar tanto el mazo como el descarte usando dos pilas. Los jugadores roban cartas de la parte superior del mazo, el mismo principio que con las letras. Cuando los jugadores descartan cartas, las cartas nuevas se colocan encima de las antiguas. Así es como se vería el primer borrador de nuestro juego, implementado usando una pila:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Como decíamos antes, tenemos dos pilas: el mazo y el descarte. La estructura de datos de la pila se implementa en Java en java.util.Stack. En nuestro juego de cartas existen 3 métodos que describen las acciones de los jugadores:

• tomar una carta de la baraja (método getCardFromDeck());
• descartar tarjeta (método discard());
• Mire la tarjeta superior (método lookTopCard()). Digamos que esta será la mecánica de bonificación "Inteligencia", que permitirá al jugador descubrir qué carta entrará en juego a continuación.

Dentro de nuestros métodos, los métodos de clase se llaman Stack:

• push()— agrega un elemento a la parte superior de la pila. Cuando descartamos una carta, esta va encima de las cartas previamente descartadas;
• pop()— elimina el elemento superior de la pila y lo devuelve. Este método es ideal para implementar la mecánica de "el jugador roba una carta".
• peek()- devuelve el elemento superior de la pila, pero no lo elimina de la pila

Veamos cómo funcionará nuestro juego:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Así que hemos añadido cinco cartas a nuestro mazo. El primer jugador tomó 3 de ellos. ¿Qué tarjetas recibió? Salida de consola:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Preste atención al orden en que se enviaron las tarjetas a la consola. La carta “Edwin Van Cleiff” fue la última en llegar a la baraja (quinta consecutiva), y fue la carta que el jugador tomó primero. “Michhlaus” fue el penúltimo en la baraja y su jugador quedó en segundo lugar. “Sylvanas” cayó al suelo tercero desde el final y se dirigió hacia el tercer jugador. A continuación, el jugador descarta sus cartas. Primero deja caer a Edwin, luego a Millhouse y luego a Sylvanas. Después de lo cual sacamos una a una a la consola las cartas que están en nuestro descarte: Salida a la consola:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

¡Y nuevamente vemos cómo funciona la pila! El descarte en nuestro juego también es una pila (al igual que el mazo). "Edwin Van Clyffe" fue el primero en desaparecer. El segundo en caer fue "Millhouse Manastorm" - y quedó encima de Edwin en el descarte. Luego, Sylvanas fue descartada y esta carta quedó encima de Millhouse. Como puede ver, no hay nada complicado en el funcionamiento de la pila. Sin embargo, es necesario conocer esta estructura de datos: a menudo se pregunta sobre ella en las entrevistas y, a menudo, se construyen estructuras de datos más complejas sobre esta base.

Cola

Una cola (o, en inglés, “Queue”) es otra estructura de datos común. Al igual que una pila, se implementa en muchos lenguajes de programación, incluido Java. ¿Cuál es la diferencia entre una cola y una pila? Su cola no se basa en LIFO, sino en otro principio: FIFO ("primero en entrar, primero en salir", "primero en entrar, primero en salir") . Es fácil de entender, tomando como ejemplo... ¡o al menos una cola ordinaria y real de la vida real! Por ejemplo, una cola para ir a la tienda. Si hay cinco personas en la fila, la primera persona de la fila entrará a la tienda . Si una persona más (además de las cinco en la fila) quiere comprar algo y hace fila, entonces ingresa a la tienda el último , es decir, el sexto. Cuando se trabaja con una cola, se agregan nuevos elementos al final y, si desea obtener un elemento, se tomará desde el principio. Este es el principio básico de su funcionamiento, que es necesario recordar: el principio de la cola es muy fácil de entender intuitivamente, ya que se encuentra a menudo en la vida real. Vale la pena señalar por separado que en Java una cola no está representada por una clase, sino por una interfaz: Queue. Pero al mismo tiempo, una cola en Java es una interfaz que tiene muchas implementaciones. Si miramos la documentación de Oracle, veremos que de la cola se heredan 4 interfaces diferentes y una lista extremadamente impresionante de clases:

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

¡Qué lista tan grande! Pero, por supuesto, no es necesario que memorices todas estas clases e interfaces ahora; tu cabeza podría explotar :) Consideraremos sólo un par de los puntos más importantes e interesantes. Primero, prestemos atención a una de las cuatro "subinterfaces" de la cola: Deque. ¿Qué tiene de especial? Deque- Esta es una cola de dos vías. Extiende la funcionalidad de una cola normal al permitirle agregar elementos en ambos extremos (el principio y el final de la cola) y tomar elementos de ambos extremos de la cola. El deque se usa ampliamente en el desarrollo. Preste atención a la lista de clases de cola que proporcionamos anteriormente. La lista es bastante larga, pero ¿hay algo que nos resulte familiar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

¡Ja, entonces nuestro viejo amigo está aquí LinkedList! Es decir, ¿implementa la interfaz Queue? ¿Pero cómo puede ser una cola? Después de todo LinkedList, ¡esta es una lista conectada! Es cierto, pero eso no impide que siga siendo una cola :) Aquí hay una lista de todas las interfaces que implementa:

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Como puede ver, LinkedListimplementa una interfaz Deque: una cola bidireccional. ¿Por qué es esto necesario? Gracias a esto podremos obtener elementos tanto del principio como del final LinkedList. Y también: agregue elementos tanto al principio como al final. Estos son los métodos heredados LinkedListde la interfaz Deque:

• peekFirst()— devuelve (pero no elimina de la cola) el primer elemento.
• peekLast()— devuelve (pero no elimina de la cola) el último elemento.
• pollFirst()- devuelve el primer elemento de la cola y lo elimina.
• pollLast()- devuelve el último elemento de la cola y lo elimina.
• addFirst()— agrega un nuevo elemento al comienzo de la cola.
• addLast()— agrega un elemento al final de la cola.

Como puede ver, LinkedList¡implementa completamente la funcionalidad de una cola bidireccional! Y si se necesita dicha funcionalidad en el programa, sabrá que se puede utilizar :) Y nuestra conferencia de hoy llega a su fin. Finalmente, te daré un par de enlaces para seguir leyendo. Primero, preste atención al artículo dedicado a PriorityQueue - "cola de prioridad". Esta es una de las implementaciones más interesantes y útiles de Queue. Por ejemplo, si hay 50 personas haciendo cola en tu tienda y 7 de ellas son clientes VIP, ¡ PriorityQueuete permitirá atenderles primero! Algo muy útil, ¿no estás de acuerdo? :) En segundo lugar, no estaría de más mencionar una vez más el libro de Robert Laforet "Estructuras de datos y algoritmos en Java" . Mientras lee el libro, no solo aprenderá muchas estructuras de datos (incluidas la pila y la cola), sino que también implementará muchas de ellas usted mismo. Por ejemplo, imagina si Java no tuviera una clase Stack. ¿Qué harías si necesitaras una estructura de datos de este tipo para tu programa? Por supuesto, tendría que escribirlo yo mismo. Cuando leas el libro de Laforet, esto es a menudo lo que harás. Gracias a esto, tu comprensión de las estructuras de datos será mucho más amplia que simplemente estudiar teoría :) ¡Hemos terminado con la teoría por hoy, pero la teoría sin práctica no es nada! Los problemas no se resolverán solos, ¡así que ahora es el momento de abordarlos! :)