Estructuras de datos: pila y cola

¡Hola! Hoy hablaremos de algo súper importante para cualquier programador: las estructuras de datos. Wikipedia dice: "Una estructura de datos es un formato de organización, gestión y almacenamiento de datos que permite un acceso y una modificación eficientes. Más precisamente, una estructura de datos es una colección de valores de datos, las relaciones entre ellos y las funciones u operaciones que pueden ser aplicado a los datos". La definición es un poco confusa, pero su esencia es clara. Una estructura de datos es una especie de repositorio donde almacenamos datos para uso futuro. En programación, hay una gran variedad de estructuras de datos. Al resolver problemas específicos, muy a menudo lo más importante es elegir la estructura de datos más adecuada para el problema. ¡Y ya estás familiarizado con muchos de ellos! Por ejemplo, sabes sobre arreglos. Y también estás familiarizado conMap(esta estructura de datos también puede denominarse "diccionario" o "matriz asociativa"). Es muy importante comprender que las estructuras de datos no están vinculadas a ningún idioma en particular. Son simplemente "modelos" abstractos que cada lenguaje de programación usa para crear sus propias clases o implementaciones de una estructura particular. Por ejemplo, una de las estructuras de datos más famosas es una lista enlazada. Puedes ir a Wikipedia y leer sobre cómo funciona y qué ventajas y desventajas tiene. Quizás su definición le resulte familiar :) "Una lista enlazada es una colección lineal de elementos de datos, cuyo orden no viene dado por su ubicación física en la memoria. En cambio, cada elemento apunta al siguiente". Eso describe a nuestro amado LinkedList, ¿no? Sí, y eso es exactamente lo que es :) En Java, la clase implementa la estructura de datos de "lista enlazada" LinkedList. ¡Pero otros lenguajes también implementan listas enlazadas! En Python, esta estructura de datos se llama " llist". En Scala se llama " LinkedList", al igual que en Java. Una lista enlazada es una de las estructuras de datos comunes básicas, por lo que encontrará que se implementa en cualquier lenguaje de programación moderno. Lo mismo ocurre con las matrices asociativas. Aquí está la definición de Wikipedia: "Una matriz asociativa, un mapa, una tabla de símbolos o un diccionario es un tipo de datos abstracto compuesto por una colección de pares (clave, valor), de modo que cada clave posible aparece como máximo una vez en la colección". ¿Eso te recuerda a algo? :) Sí. Para nosotros, los desarrolladores de Java, una matriz asociativa es elMapinterfaz. ¡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 Ruby, se implementa en una clase llamada "Hash". Bueno, entiendes el punto: las estructuras de datos son conceptos universales en la programación, y cada lenguaje de programación los implementa a su manera. Hoy estudiaremos dos estructuras de este tipo, la pila y la cola, y veremos cómo se implementan en Java.

Pilas en Java

Una pila es una estructura de datos bien conocida. Es muy simple. Bastantes elementos en nuestra vida diaria se "implementan" como una pila. Imagine esta situación simple: se hospeda en un hotel y, en el transcurso del día, recibió algunas cartas comerciales. No estaba en su habitación en ese momento, por lo que el empleado del hotel simplemente colocó las cartas entrantes en su escritorio. Primero, colocó la primera carta sobre el escritorio. Luego llegó una segunda carta y la colocó encima de la primera. Puso la tercera letra encima de la segunda y la cuarta encima de la tercera. Y ahora, responde una simple pregunta: ¿qué letra leerás primero cuando regreses a tu habitación y veas la pila sobre la mesa? Correcto, leerás la parte superiorcarta. Es decir, el que llegó más recientemente . Así es exactamente como funciona una pila. Este principio se denomina "último en entrar, primero en salir" (LIFO) . ¿Para qué sirven las pilas? Bueno, supongamos que está creando algún tipo de juego de cartas en Java. Una baraja de cartas yace sobre la mesa. Las cartas jugadas se descartan. Puedes usar dos pilas para implementar tanto el mazo de robo como la pila de descarte. Los jugadores toman sus cartas de la parte superior de la baraja, siguiendo el mismo principio que con sus cartas comerciales. Cuando los jugadores ponen cartas en la pila de descarte, las cartas recién descartadas se colocan encima de las antiguas. Aquí está nuestro primer intento de juego, implementado sobre la base de 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 {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

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

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

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Como dijimos antes, tenemos dos pilas: una baraja de robo y una pila de descarte. En Java, la estructura de datos de la pila se implementa en la java.util.Stackclase. Nuestro juego de cartas tiene 3 métodos que describen las acciones de los jugadores:

• tomar una carta de la baraja ( getCardFromDeck()método)
• descartar una carta ( discard()método)
• mira la carta superior ( lookAtTopCard()método). Digamos que este es un bono de "Inteligencia" que le permite al jugador averiguar qué carta vendrá a continuación en el juego.

Dentro de nuestros métodos, llamamos a los siguientes métodos de la clase Stack:

• push()— añade un elemento a la parte superior de la pila. Cuando enviamos una carta a la pila de descarte, va a la parte superior de la pila
• pop()— elimina el elemento superior de la pila y lo devuelve. Este método es perfecto para implementar acciones en las que 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) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Agregamos cinco cartas a nuestra baraja. El primer jugador tomó 3 de ellos. ¿Qué cartas recibió? Salida de la consola:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Preste atención al orden en que se muestran las tarjetas en la consola. La última carta de "Edwin VanCleef" entró en la baraja (era la quinta carta), y fue la carta que el jugador sacó primero. "Millhouse" fue el penúltimo en llegar a la baraja, y el jugador lo robó en segundo lugar. "Sylvanas" entró en el mazo tercero desde arriba, y fue la tercera carta que sacó el jugador. A continuación, el jugador descarta cartas. Primero descarta a Edwin, luego a Millhouse y luego a Sylvanas. Luego mostramos las cartas en nuestra pila de descarte una por una: Salida de la consola:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

¡Una vez más, vemos cómo funciona una pila! En nuestro juego, la pila de descarte también es una pila (igual que el mazo de robo). "Edwin VanCleef" fue descartado primero. El segundo descarte de cartas fue Millhouse Manastorm, y se colocó encima de Edwin en la pila de descartes. Luego se descartó a Sylvanas y esta carta se colocó encima de Millhouse. Como puede ver, no hay nada complicado en una pila. Aún así, necesita conocer esta estructura de datos: a menudo se pregunta durante las entrevistas de trabajo y, a menudo, es la base para construir estructuras de datos más complejas.

Cola en Java

Una cola es otra estructura de datos común. Además de las pilas, muchos lenguajes de programación, incluido Java, también implementan la estructura de datos de la cola. ¿Cuál es la diferencia entre una cola y una pila? Una cola no se basa en el principio LIFO, sino en el principio FIFO ("primero en entrar, primero en salir"). ¡Este principio es fácil de entender si se considera, por ejemplo, una línea normal o una cola en la vida real! Por ejemplo, una fila en el supermercado. Si hay cinco personas en la fila, la primera en ser atendida será la que entró primero a la fila . Si otra persona (además de las cinco que ya están en la fila) quiere comprar algo y se pone en la fila, se le sirve en último lugar ., es decir, sexto. Cuando se trabaja con una cola, se agregan nuevos elementos en la cola (atrás), y si desea obtener un elemento, se tomará de la cabeza (frente). Este es el principio principal que debe recordar con respecto a cómo funciona una cola. El funcionamiento de una cola es muy intuitivo, ya que encontramos colas 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. Además, hay muchas implementaciones de esta interfaz de cola en Java. Si miramos la documentación de Oracle, veremos que 4 interfaces diferentes, así como una lista de clases extremadamente impresionante, heredan la interfaz Queue:

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é gran lista! Pero, por supuesto, no necesita memorizar todas estas clases e interfaces en este momento; su cabeza podría explotar :) Solo consideraremos un par de los puntos más importantes e interesantes. Primero, prestemos atención a una de las cuatro "subinterfaces" de Queue: Deque . ¿Qué lo hace tan especial? A Dequees una cola de dos extremos. Extiende la funcionalidad de una cola regular, permitiéndole agregar elementos a ambos extremos (en la cabeza y la cola) y tomar elementos de ambos extremos de la cola. Las colas de dos extremos se utilizan ampliamente en el desarrollo de software. Preste atención a la lista de clases de cola que proporcionamos anteriormente. La lista es bastante larga, pero ¿contiene algo familiar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

¡Ja! ¡Aquí está nuestro viejo amigo LinkedList! Entonces, ¿implementa la interfaz Queue? Pero, ¿cómo puede ser una cola? Después de todo, ¡a LinkedListes una lista enlazada! Cierto, pero eso no evita que sea 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 la Dequeinterfaz (nuevamente, esto significa cola de dos extremos). ¿Por qué es necesario? Esto nos permite obtener elementos desde el principio y el final de un archivo LinkedList. También nos permite añadir elementos al principio y al final. Estos son los métodos que LinkedListse obtienen de la Dequeinterfaz:

• peekFirst()— devuelve el primer elemento (pero no lo elimina de la cola).
• peekLast()— devuelve el último elemento (pero no lo elimina de la cola).
• 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 frente de la cola.
• addLast()— agrega un elemento al final de la cola.

Como puede ver, ¡ LinkedListimplementa completamente la funcionalidad de una cola de dos extremos! Y si necesita esa funcionalidad en su programa, sabrá dónde encontrarla :) La lección de hoy está llegando a su fin. En conclusión, le daré un par de enlaces para lectura adicional. Primero, presta atención a este artículo sobre PriorityQueue . Esta es una de las Queueimplementaciones más interesantes y útiles. Por ejemplo, suponga que hay 50 personas esperando en fila en su tienda y 7 de ellas son clientes VIP. ¡Un PriorityQueue le permitirá servirlos primero! Cosas muy útiles, ¿verdad? :) En segundo lugar, no estaría de más mencionar una vez más el libro de Robert Lafore "Estructuras de datos y algoritmos en Java".. Al leer este 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, ¿qué pasaría si Java no tuviera una clase Stack? ¿Qué haría si necesitara una estructura de datos de este tipo para su programa? Tendrías que escribirlo tú mismo, por supuesto. Cuando lea el libro de Lafore , a menudo hará precisamente eso. Como resultado, su comprensión de las estructuras de datos será mucho más profunda de lo que obtendría con un simple estudio de la teoría :) Estamos terminando la teoría de hoy, ¡pero la teoría sin práctica no es nada! Las tareas no se resolverán solas, ¡así que es hora de abordarlas! :)