Strutture dati: stack e code

CIAO! Oggi parleremo di qualcosa di estremamente importante per qualsiasi programmatore: le strutture dati. Wikipedia afferma: "Una struttura di dati è un formato di organizzazione, gestione e archiviazione dei dati che consente un accesso e una modifica efficienti. Più precisamente, una struttura di dati è una raccolta di valori di dati, le relazioni tra di essi e le funzioni o operazioni che possono essere applicato ai dati”. La definizione è un po' confusa, ma il succo è chiaro. Una struttura dati è una sorta di repository in cui archiviamo i dati per un uso futuro. Nella programmazione esiste un'enorme varietà di strutture dati. Quando si risolvono problemi specifici, molto spesso la cosa più importante è scegliere la struttura dati più adatta al problema. E conosci già molti di loro! Ad esempio, conosci gli array. E hai anche familiarità conMap(questa struttura di dati può anche essere definita "dizionario" o "array associativo"). È molto importante capire che le strutture dati non sono legate a nessuna lingua particolare. Sono semplicemente "progetti" astratti che ogni linguaggio di programmazione utilizza per creare le proprie classi o implementazioni di una particolare struttura. Ad esempio, una delle strutture dati più famose è un elenco collegato. Puoi andare su Wikipedia e leggere come funziona e quali vantaggi e svantaggi ha. Forse la sua definizione ti sembrerà familiare :) "Un elenco collegato è una raccolta lineare di elementi di dati, il cui ordine non è dato dalla loro collocazione fisica in memoria. Invece, ogni elemento punta al successivo." Questo descrive il nostro amato LinkedList, vero? Sì, ed è proprio quello che è :) In Java, la struttura dei dati "lista collegata" è implementata dalla LinkedListclasse. Ma anche altre lingue implementano elenchi collegati! In Python, questa struttura dati è chiamata " llist". In Scala si chiama " LinkedList", proprio come in Java. Un elenco collegato è una delle strutture dati comuni di base, quindi scoprirai che è implementato in qualsiasi linguaggio di programmazione moderno. La stessa cosa vale per gli array associativi. Ecco la definizione da Wikipedia: "Un array associativo, una mappa, una tabella di simboli o un dizionario è un tipo di dati astratto composto da una raccolta di coppie (chiave, valore), in modo tale che ogni possibile chiave appaia al massimo una volta nella raccolta". Ti ricorda qualcosa? :) Sì. Per noi sviluppatori Java, un array associativo è ilMapinterfaccia. Ma questa struttura dati è implementata anche in altre lingue! Ad esempio, i programmatori C# lo conoscono con il nome di "Dizionario". E in Ruby, è implementato in una classe chiamata "Hash". Bene, hai capito: le strutture dati sono concetti universali nella programmazione e ogni linguaggio di programmazione le implementa a modo suo. Oggi studieremo due di queste strutture - lo stack e la coda - e vedremo come vengono implementate in Java.

Stack in Java

Uno stack è una struttura di dati ben nota. È molto semplice. Parecchi elementi nella nostra vita quotidiana sono "implementati" come una pila. Immagina questa semplice situazione: stai in un hotel e nel corso della giornata hai ricevuto alcune lettere commerciali. Non eri nella tua stanza in quel momento, quindi l'impiegato dell'hotel ha semplicemente messo le lettere in arrivo sulla tua scrivania. Per prima cosa, ha messo la prima lettera sulla scrivania. Poi arrivò una seconda lettera e la mise sopra la prima. Mise la terza lettera sopra la seconda e la quarta sopra la terza. E ora rispondi a una semplice domanda: quale lettera leggerai per prima quando tornerai nella tua stanza e vedrai la pila sul tavolo? Bene, leggerai il più in altolettera. Cioè quello che è arrivato più di recente . Questo è esattamente il modo in cui funziona uno stack. Questo principio è chiamato "last in first out" (LIFO) . A cosa servono gli stack? Bene, supponiamo che tu stia creando una specie di gioco di carte in Java. Sul tavolo c'è un mazzo di carte. Le carte giocate vengono scartate. Puoi usare due pile per implementare sia il mazzo di pesca che la pila degli scarti. I giocatori prendono le loro carte dalla cima del mazzo, seguendo lo stesso principio delle tue lettere commerciali. Quando i giocatori mettono le carte nella pila degli scarti, le nuove carte scartate vengono poste sopra quelle vecchie. Ecco il nostro primo tentativo di gioco, implementato sulla base di 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 {

   // 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.
}

Come abbiamo detto prima, abbiamo due pile: un mazzo di pesca e una pila degli scarti. In Java, la struttura dei dati dello stack è implementata nella java.util.Stackclasse. Il nostro gioco di carte ha 3 metodi che descrivono le azioni dei giocatori:

• prendi una carta dal mazzo ( getCardFromDeck()metodo)
• scartare una carta ( discard()metodo)
• guarda la prima carta ( lookAtTopCard()metodo). Diciamo che questo è un bonus "Intelligence" che consente al giocatore di scoprire quale carta verrà dopo nel gioco.

All'interno dei nostri metodi, chiamiamo i seguenti metodi della classe Stack:

• push()— aggiunge un elemento in cima alla pila. Quando mettiamo una carta nella pila degli scarti, va in cima alla pila
• pop()— rimuove l'elemento superiore dallo stack e lo restituisce. Questo metodo è perfetto per implementare azioni in cui 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) {

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

Abbiamo aggiunto cinque carte al nostro mazzo. Il primo giocatore ne prese 3. Quali carte ha ricevuto? Uscita console:

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

Presta attenzione all'ordine in cui le carte vengono visualizzate sulla console. La carta "Edwin VanCleef" è entrata nel mazzo per ultima (era la quinta carta), ed è stata la carta che il giocatore ha pescato per prima. "Millhouse" è stato il penultimo nel mazzo e il giocatore l'ha pescato per secondo. "Sylvanas" è entrato nel mazzo per terza dall'alto, ed è stata la terza carta che il giocatore ha pescato. Successivamente, il giocatore scarta le carte. Prima scarta Edwin, poi Millhouse, poi Sylvanas. Quindi mostriamo le carte nella nostra pila degli scarti una per una: Uscita della console:

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

Ancora una volta, vediamo come funziona uno stack! Nel nostro gioco, anche la pila degli scarti è una pila (proprio come il mazzo di pesca). "Edwin VanCleef" è stato scartato per primo. La seconda carta scartata è stata Millhouse Manastorm, ed è stata messa sopra Edwin nella pila degli scarti. Quindi Sylvanas è stato scartato e questa carta è stata posizionata sopra Millhouse. Come puoi vedere, non c'è niente di complicato in uno stack. Tuttavia, è necessario conoscere questa struttura di dati: viene spesso chiesta durante i colloqui di lavoro ed è spesso la base per la creazione di strutture di dati più complesse.

Coda in Java

Una coda è un'altra struttura dati comune. Oltre agli stack, molti linguaggi di programmazione, incluso Java, implementano anche la struttura dei dati della coda. Qual è la differenza tra una coda e una pila? Una coda non si basa sul principio LIFO, ma piuttosto sul principio FIFO ("first in, first out"). Questo principio è facilmente comprensibile considerando, ad esempio, una normale fila, o coda, nella vita reale! Ad esempio, una fila al supermercato. Se ci sono cinque persone in fila, il primo ad essere servito sarà quello che è entrato per primo in fila . Se un'altra persona (oltre alle cinque già in fila) vuole comprare qualcosa e si mette in fila, viene servito per ultimo, cioè sesto. Quando si lavora con una coda, vengono aggiunti nuovi elementi alla coda (posteriore) e se si desidera ottenere un elemento, verrà preso dalla testa (davanti). Questo è il principio principale che devi ricordare riguardo a come funziona una coda. Il funzionamento di una coda è molto intuitivo, dal momento che troviamo spesso code nella vita reale. Vale la pena notare separatamente che in Java una coda non è rappresentata da una classe, ma da un'interfaccia: Queue. Inoltre, ci sono molte implementazioni di questa interfaccia di coda in Java. Se guardiamo alla documentazione Oracle, vedremo che 4 diverse interfacce, oltre a un elenco estremamente impressionante di classi, ereditano l'interfaccia 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

Che lista lunga! Ma, ovviamente, non è necessario memorizzare tutte queste classi e interfacce in questo momento: la tua testa potrebbe esplodere :) Prenderemo in considerazione solo un paio dei punti più importanti e interessanti. Innanzitutto, prestiamo attenzione a una delle quattro "sottointerfacce" di Queue: Deque . Cosa lo rende così speciale? A Dequeè una coda a doppia estremità. Estende la funzionalità di una coda regolare, consentendo di aggiungere elementi a entrambe le estremità (in testa e in coda) e prendere elementi da entrambe le estremità della coda. Le code a doppia estremità sono ampiamente utilizzate nello sviluppo di software. Presta attenzione all'elenco delle classi di coda che abbiamo fornito sopra. L'elenco è piuttosto lungo, ma contiene qualcosa di familiare?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ah! Ecco il nostro vecchio amico LinkedList! Quindi, implementa l'interfaccia Queue? Ma come può essere una coda? Dopotutto, a LinkedListè un elenco collegato! Vero, ma questo 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 l' Dequeinterfaccia (di nuovo, questo significa coda a doppia estremità). Perché è necessario? Questo ci permette di ottenere elementi dall'inizio e dalla fine di un file LinkedList. Ci permette anche di aggiungere elementi all'inizio e alla fine. Ecco i metodi che LinkedListottiene dall'interfaccia Deque:

• peekFirst()— restituisce il primo elemento (ma non lo rimuove dalla coda).
• peekLast()— restituisce l'ultimo elemento (ma non lo rimuove dalla coda).
• 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 completamente la funzionalità di una coda a doppia estremità! E hai bisogno di tale funzionalità nel tuo programma, saprai dove trovarla :) La lezione di oggi sta per finire. In conclusione, ti darò un paio di link per ulteriori letture. Innanzitutto, presta attenzione a questo articolo su PriorityQueue . Questa è una delle Queueimplementazioni più interessanti e utili. Ad esempio, supponiamo che ci siano 50 persone in fila nel tuo negozio e 7 di loro siano clienti VIP. Una PriorityQueue ti permetterà di servirli per primi! Cose molto utili, vero? :) In secondo luogo, non sarebbe male menzionare ancora una volta il libro di Robert Lafore "Data Structures and Algorithms in Java". Leggendo questo libro, non solo imparerai molte strutture di dati (inclusi stack e code), ma ne implementerai anche molte tu stesso! Ad esempio, cosa succederebbe se Java non avesse una classe Stack? Cosa faresti se avessi bisogno di una tale struttura dati per il tuo programma? Dovresti scriverlo tu stesso, ovviamente. Mentre leggi il libro di Lafore , farai spesso proprio questo. Di conseguenza, la tua comprensione delle strutture dati sarà molto più profonda di quella che otterresti da un semplice studio della teoria :) Stiamo concludendo la teoria per oggi, ma la teoria senza la pratica non è niente! I compiti non si risolveranno da soli, quindi è il momento di affrontarli! :)