Strutture dati in Java: stack e coda

Ciao! Oggi parleremo di cose così importanti per qualsiasi programmatore come le strutture dati . Wikipedia dice: La struttura dei dati ( ing. struttura dei dati ) è un'unità software che consente di archiviare ed elaborare molti dati dello stesso tipo e/o logicamente correlati nell'informatica. La definizione è un po’ confusa, ma la sua essenza è chiara. Una struttura dati è un tipo di spazio di archiviazione in cui memorizziamo i dati per un ulteriore utilizzo. Esiste un'enorme varietà di strutture dati nella programmazione. Molto spesso, quando si risolve un problema specifico, la cosa più importante è scegliere la struttura dati più adatta allo scopo. E ne conosci già molti! Ad esempio, con gli array . E anche con Map(che di solito viene tradotto come “dizionario”, “mappa” o “array associativo”). È molto importante capire: le strutture dati non sono legate a nessun linguaggio specifico . Questi sono semplicemente "progetti" astratti in base ai quali ogni linguaggio di programmazione crea le proprie classi - implementazioni di questa struttura. Ad esempio, una delle strutture dati più famose è la lista concatenata . Puoi andare su Wikipedia, leggere come funziona, quali vantaggi e svantaggi ha. Potresti trovare familiare la sua definizione :) "Una lista concatenata è una struttura di dati dinamica di base in informatica, composta da nodi, ciascuno dei quali contiene sia i dati stessi che uno o due collegamenti ("link") al successivo e/o elenco dei nodi precedenti” Quindi questo è nostro LinkedList! Esatto, è così :) La struttura dei dati dell'elenco collegato è implementata nel linguaggio Java nella classe LinkedList. Ma anche altri linguaggi implementano elenchi collegati! In Python si chiama “ llist”, in Scala si chiama come in Java - “ LinkedList“. Un elenco collegato è una delle strutture dati comuni di base, quindi puoi trovare la sua implementazione in qualsiasi linguaggio di programmazione moderno. Stessa cosa con un array associativo. Ecco la sua definizione da Wikipedia: Un array associativo è un tipo di dati astratto (un'interfaccia per un archivio dati) che consente di memorizzare coppie nella forma "(chiave, valore)" e supporta le operazioni di aggiunta di una coppia, nonché di ricerca ed eliminando una coppia tramite chiave. Non ti ricorda niente? :) Esattamente, per noi Javaisti, un array associativo è un'interfacciaMap. Ma questa struttura dati è implementata anche in altri linguaggi! Ad esempio, i programmatori C# lo conoscono con il nome “Dizionario”. E nel linguaggio Ruby è implementato in una classe chiamata “Hash”. In generale, capisci approssimativamente qual è il significato: una struttura dati è una cosa comune a tutta la programmazione, che è implementata in modo diverso in ogni linguaggio specifico. Oggi studieremo due di queste strutture e vedremo come sono implementate in Java: stack e coda.

Impilare in Java

Uno stack è una struttura dati conosciuta. È molto semplice e molti oggetti della nostra vita quotidiana vengono “implementati” come uno stack. Immagina una situazione semplice: vivi in ​​un albergo e durante il giorno ricevi lettere commerciali. Poiché in quel momento non eri nella stanza, il dipendente dell'hotel ha semplicemente messo le lettere in arrivo sul tuo tavolo. Per prima cosa mise sul tavolo la prima lettera. Poi arrivò il secondo e lo mise sopra il primo. Pose la terza lettera arrivata sopra la seconda e la quarta sopra la terza. Ora rispondi a una semplice domanda: quale lettera leggerai per prima quando arriverai nella tua stanza e vedrai una pila sul tavolo? Esatto, leggerai la lettera in alto. Cioè quello arrivato per ultimo nel tempo . Questo è esattamente il modo in cui funziona uno stack. Questo principio di funzionamento è chiamato LIFO - “last in - first out” (“last in, first out”). A cosa può essere utile uno stack? Ad esempio, stai creando una sorta di gioco di carte in Java. Sul tavolo c'è un mazzo di carte. Le carte giocate vengono scartate. Puoi implementare sia il mazzo che lo scarto utilizzando due pile. I giocatori pescano le carte dalla cima del mazzo, lo stesso principio delle lettere. Quando i giocatori scartano le carte, le nuove carte vengono posizionate sopra quelle vecchie. Ecco come apparirebbe la prima bozza del nostro gioco, implementata utilizzando uno stack:

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

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

Come abbiamo detto prima, abbiamo due pile: il mazzo e gli scarti. La struttura dei dati dello stack è implementata in Java nel formato java.util.Stack. Nel nostro gioco di carte ci sono 3 metodi che descrivono le azioni dei giocatori:

• prendere una carta dal mazzo (metodo getCardFromDeck());
• scartare la carta (metodo discard());
• guarda la prima carta (metodo lookTopCard()). Diciamo che questa sarà la meccanica bonus "Intelligenza", che permetterà al giocatore di scoprire quale carta entrerà in gioco dopo.

All'interno dei nostri metodi, i metodi della classe sono chiamati Stack:

• push()— aggiunge un elemento in cima allo stack. Quando scartiamo una carta, questa va sopra le carte precedentemente scartate;
• pop()— rimuove l'elemento in cima allo stack e lo restituisce. Questo metodo è ideale per implementare la meccanica “il giocatore pesca una carta”.
• peek()- restituisce l'elemento in cima allo stack, ma non lo rimuove dallo stack

Vediamo come funzionerà il nostro gioco:

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

Quindi abbiamo aggiunto cinque carte al nostro mazzo. Il primo giocatore ne ha presi 3. Che carte ha ricevuto? Uscita console:

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

Prestare attenzione all'ordine in cui le carte sono state inviate alla console. La carta “Edwin Van Cleiff” è stata l'ultima a colpire il mazzo (la quinta consecutiva), ed è stata la carta che il giocatore ha preso per prima. “Michhlaus” è stato il penultimo sul mazzo e il suo giocatore è arrivato secondo. "Sylvanas" ha colpito il mazzo per terzo dalla fine ed è andato al terzo giocatore. Successivamente, il giocatore scarta le sue carte. Prima lascia cadere Edwin, poi Millhouse, poi Sylvanas. Dopodiché, una per una, trasmettiamo alla console le carte che sono nei nostri scarti: Output alla console:

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

E ancora vediamo come funziona lo stack! Anche lo scarto nel nostro gioco è una pila (proprio come il mazzo). "Edwin Van Clyffe" è stato il primo ad essere abbandonato. Il secondo ad essere eliminato è stato "Millhouse Manastorm" - e si trovava sopra Edwin nello scarto. Successivamente, Sylvanas è stata scartata e questa carta si trovava sopra Millhouse. Come puoi vedere, non c'è nulla di complicato nel funzionamento dello stack. Tuttavia, è necessario conoscere questa struttura dei dati: viene spesso chiesta nelle interviste e spesso sulla sua base vengono costruite strutture di dati più complesse.

Coda

Una coda (o, in inglese, "Queue") è un'altra struttura dati comune. Proprio come uno stack, è implementato in molti linguaggi di programmazione, incluso Java. Qual è la differenza tra una coda e uno stack? La sua coda non si basa sul LIFO, ma su un altro principio: FIFO ("first in - first out", "first in - first out") . È facile da capire, prendendo come esempio... o almeno una normale coda reale della vita reale! Ad esempio, una coda al negozio. Se ci sono cinque persone in fila, la prima persona in fila entrerà nel negozio . Se un'altra persona (oltre alle cinque in fila) vuole comprare qualcosa e si mette in fila, entrerà per ultima nel negozio , cioè la sesta. Quando si lavora con una coda, i nuovi elementi vengono aggiunti alla fine e, se si desidera ottenere un elemento, verrà preso dall'inizio. Questo è il principio di base del suo funzionamento, che devi ricordare. Il principio della coda è molto facile da capire intuitivamente, poiché lo si incontra spesso nella vita reale. Vale la pena notare separatamente che in Java la coda non è rappresentata da una classe, ma da un'interfaccia - Queue. Ma allo stesso tempo, una coda in Java è un'interfaccia che ha molte implementazioni. Se guardiamo la documentazione di Oracle, vedremo che dalla coda vengono ereditate 4 diverse interfacce e un elenco di classi estremamente impressionante:

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

Che lunga lista! Ma, ovviamente, non è necessario memorizzare tutte queste classi e interfacce adesso: la tua testa potrebbe esplodere :) Considereremo solo un paio dei punti più importanti e interessanti. Innanzitutto, prestiamo attenzione a una delle quattro "interfacce secondarie" della coda: Deque. Cosa c'è di così speciale? Deque- Questa è una coda a doppio senso. Estende la funzionalità di una coda normale consentendo di aggiungere elementi a entrambe le estremità (l'inizio e la fine della coda) e di prendere elementi da entrambe le estremità della coda. La deque è ampiamente utilizzata nello sviluppo. Presta attenzione all'elenco delle classi di coda che abbiamo fornito sopra. L'elenco è piuttosto lungo, ma c'è qualcosa di familiare a noi lì?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ah, quindi il nostro vecchio amico è qui LinkedList! Cioè, implementa l'interfaccia Queue? Ma come può essere una coda? Dopo tutto LinkedList, questa è una lista connessa! Vero, ma ciò non gli impedisce di essere una coda :) Ecco un elenco di tutte le interfacce che implementa:

All Implemented Interfaces:

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

Come puoi vedere, LinkedListimplementa un'interfaccia Deque: una coda bidirezionale. Perché è necessario? Grazie a questo, possiamo ottenere elementi sia dall'inizio che dalla fine LinkedList. E inoltre: aggiungi elementi sia all'inizio che alla fine. Ecco i metodi ereditati LinkedListdall'interfaccia Deque:

• peekFirst()— restituisce (ma non rimuove dalla coda) il primo elemento.
• peekLast()— restituisce (ma non rimuove dalla coda) l'ultimo elemento.
• pollFirst()- restituisce il primo elemento dalla coda e lo rimuove.
• pollLast()- restituisce l'ultimo elemento dalla coda e lo rimuove.
• addFirst()— aggiunge un nuovo elemento all'inizio della coda.
• addLast()— aggiunge un elemento alla fine della coda.

Come puoi vedere, LinkedListimplementa pienamente la funzionalità di una coda bidirezionale! E se tale funzionalità è necessaria nel programma, saprai che può essere utilizzata :) E la nostra lezione di oggi sta giungendo al termine. Infine, ti darò un paio di link per ulteriori letture. Innanzitutto, presta attenzione all'articolo dedicato a PriorityQueue - "coda prioritaria". Questa è una delle implementazioni più interessanti e utili di Queue. Ad esempio, se ci sono 50 persone in fila nel tuo negozio e 7 di loro sono clienti VIP, PriorityQueueti permetterà di servirli per primi! Una cosa molto utile, non sei d’accordo? :) In secondo luogo, non sarebbe superfluo menzionare ancora una volta il libro di Robert Laforet "Data Structures and Algorithms in Java" . Durante la lettura del libro, non solo imparerai molte strutture dati (inclusi stack e coda), ma ne implementerai anche molte tu stesso! Ad esempio, immagina se Java non avesse una classe Stack. Cosa faresti se avessi bisogno di una tale struttura dati per il tuo programma? Naturalmente, dovrei scriverlo io stesso. Quando leggi il libro di Laforet, spesso questo è ciò che farai. Grazie a questo, la tua comprensione delle strutture dati sarà molto più ampia rispetto a quando studi semplicemente la teoria :) Per oggi abbiamo finito con la teoria, ma la teoria senza la pratica non è nulla! I problemi non si risolveranno da soli, quindi ora è il momento di affrontarli! :)