Share
Finora abbiamo esaminato le raccolte che forniscono un'archiviazione dei dati di base, essenzialmente astrazioni su un array. In questa sezione, esamineremo cosa succede quando aggiungiamo alcuni comportamenti di base che cambiano completamente l'utilità delle raccolte.
Una pila è una raccolta che restituisce oggetti al chiamante in un modello LIFO (Last-In-First-Out). Ciò significa che l'ultimo oggetto aggiunto alla raccolta sarà il primo oggetto restituito.
Gli stack differiscono da quelli di tipo list e array. Non possono essere indicizzati direttamente, gli oggetti vengono aggiunti e rimossi utilizzando metodi diversi e il loro contenuto è più opaco di liste e matrici. Ciò che intendo è che mentre una raccolta basata su elenchi fornisce un metodo Contiene, uno stack no. Inoltre, uno stack non è enumerabile. Per capire perché questo è, diamo un'occhiata a cosa è uno stack e come l'utilizzo di uno stack guida queste differenze.
Una delle analogie più comuni per una pila è la pila di piatti del ristorante. Questo è un semplice dispositivo a molla su cui sono impilati piatti puliti. La molla garantisce che indipendentemente dal numero di piastre presenti nella pila, la piastra superiore possa essere facilmente accessibile. Le piastre pulite vengono aggiunte nella parte superiore della pila e quando un cliente rimuove una lastra, rimuove la lastra più in alto (la lastra aggiunta più di recente).
Iniziamo con un portatarga vuoto.
Una pila di piatti vuota (la molla non tiene piatti) E poi aggiungiamo una piastra rossa, una blu e una verde al rack in questo ordine.
Il punto chiave per capire qui è che quando vengono aggiunti nuovi piatti, vengono aggiunti in cima allo stack. Se un cliente recupera un piatto, otterrà l'ultimo piatto aggiunto (il piatto verde). Il prossimo cliente otterrebbe il piatto blu, e alla fine il piatto rosso sarebbe stato rimosso.
Ora che capiamo come funziona uno stack, definiamo alcuni nuovi termini. Quando un articolo viene aggiunto allo stack, viene "spinto" sull'uso di Spingere metodo. Quando un oggetto viene rimosso dalla pila, viene "scoppiato" usando il Pop metodo. L'elemento in cima alla pila, l'ultimo aggiunto, può essere "sbirciato" nell'usare il Sbirciare metodo. Sbirciare ti permette di vedere l'oggetto senza rimuoverlo dallo stack (proprio come il cliente sul portapiatti sarebbe in grado di vedere il colore della piastra superiore). Con questi termini in mente, diamo un'occhiata all'implementazione di a Pila classe.
Il Pila la classe definisce Spingere, Pop, e Sbirciare metodi, a Contare proprietà e utilizza il Lista collegata classe per memorizzare i valori contenuti nello stack.
Stack di classe pubblica LinkedList _items = new LinkedList (); push pubblico (valore T) throw new NotImplementedException (); public T Pop () throw new NotImplementedException (); public T Peek () throw new NotImplementedException (); public int Count get;
| Comportamento | Aggiunge un elemento in cima alla pila. |
| Prestazione | O (1) |
Poiché utilizziamo un elenco collegato come nostro backing store, tutto ciò che dobbiamo fare è aggiungere il nuovo elemento alla fine dell'elenco.
public public push (valore T) _items.AddLast (valore);
| Comportamento | Rimuove e restituisce l'ultimo elemento aggiunto allo stack. Se lo stack è vuoto, a InvalidOperationException viene lanciato. |
| Prestazione | O (1) |
Spingere aggiunge elementi sul retro della lista, quindi li "pop" dalla parte posteriore. Se l'elenco è vuoto, viene generata un'eccezione.
Accentsconagua
public T Pop () if (_items.Count == 0) throw new InvalidOperationException ("Lo stack è vuoto"); T result = _items.Tail.Value; _items.RemoveLast (); ritorno risultato; | Comportamento | Restituisce l'ultimo elemento aggiunto allo stack ma lascia l'oggetto in pila. Se lo stack è vuoto, a InvalidOperationException viene lanciato. |
| Prestazione | O (1) |
public T Peek () if (_items.Count == 0) throw new InvalidOperationException ("Lo stack è vuoto"); return _items.Tail.Value; | Comportamento | Restituisce il numero di elementi nello stack. |
| Prestazione | O (1) |
Dal momento che lo stack dovrebbe essere una struttura di dati opaca, perché abbiamo un? Contare proprietà? Sapere se una pila è vuota (Conteggio == 0) è molto utile, soprattutto da quando Pop genera un'eccezione quando lo stack è vuoto.
public int Count get return _items.Count;
L'esempio classico di stack è il calcolatore Reverse Polish Notation (RPN).
La sintassi RPN è abbastanza semplice. Utilizza:
piuttosto che il tradizionale:
In altre parole, invece di dire "4 + 2", diremmo "4 2 +". Se vuoi capire il significato storico della sintassi RPN, ti incoraggio a visitare Wikipedia o il tuo motore di ricerca preferito.
Il modo in cui viene valutato l'RPN e il motivo per cui uno stack è così utile quando si implementa un calcolatore RPN, può essere visto nel seguente algoritmo:
per ogni valore di input se il valore è un numero intero spingere il valore sullo stack dell'operando altrimenti se il valore è un operatore pop i valori sinistro e destro dello stack valutare l'operatore spingere il risultato sullo stack pop risposta dallo stack.
Quindi, data la stringa di input "4 2 +", le operazioni sarebbero:
premere (4) premere (2) premere (pop () + pop ())
Ora la pila contiene un singolo valore: sei (la risposta).
La seguente è una implementazione completa di una semplice calcolatrice che legge un'equazione (ad esempio, "4 2 +") dall'ingresso della console, divide l'input in ogni spazio (["4", "2" e "+"]) e esegue l'algoritmo RPN sull'input. Il ciclo continua fino a quando l'input è la parola "esci".
void RpnLoop () while (true) Console.Write (">"); string input = Console.ReadLine (); if (input.Trim (). ToLower () == "quit") break; // La pila di numeri interi non ancora utilizzati. Stack values = new Stack (); foreach (stringa token in input.Split (nuovo char [] ")) // Se il valore è un intero ... valore int; if (int.TryParse (token, valore out)) // ... spingilo a stack. values.Push (valore); else // Altrimenti valuta l'espressione ... int rhs = values.Pop (); int lhs = values.Pop (); // ... e inserisce il risultato nello stack. switch (token) case "+": values.Push (lhs + rhs); break; case "-": values.Push (lhs - rhs); break; case "*": values.Push (lhs * rhs) ; break; case "/": values.Push (lhs / rhs); break; case "%": values.Push (lhs% rhs); break; default: throw new ArgumentException (string.Format ("Token non riconosciuto: 0 ", token)); // L'ultimo elemento nello stack è il risultato Console.WriteLine (values.Pop ()); Le code sono molto simili alle pile: forniscono una raccolta opaca da cui gli oggetti possono essere aggiunti (messi in coda) o rimossi (rimossi dalla coda) in un modo che aggiunge valore a una raccolta basata su elenchi.
Le code sono una raccolta FIFO (First-In-First-Out). Ciò significa che gli elementi vengono rimossi dalla coda nello stesso ordine in cui sono stati aggiunti. Puoi pensare a una coda come una linea in un banco cassa: le persone entrano nella fila e sono servite nell'ordine in cui arrivano.
Le code vengono comunemente utilizzate nelle applicazioni per fornire un buffer per aggiungere elementi per l'elaborazione futura o per fornire un accesso ordinato a una risorsa condivisa. Ad esempio, se un database è in grado di gestire solo una connessione, è possibile utilizzare una coda per consentire ai thread di attendere il loro turno (in ordine) per accedere al database.
Il Coda, come il Pila, è supportato da a Lista collegata. Inoltre, fornisce i metodi Enqueue (per aggiungere articoli), dequeue (per rimuovere gli oggetti), Sbirciare, e Contare. Piace Pila, non sarà trattato come una raccolta di scopi generali, il che significa che non verrà implementato ICollection.
public class Queue LinkedList _items = new LinkedList (); public void Enqueue (valore T) throw new NotImplementedException (); public T Dequeue () throw new NotImplementedException (); public T Peek () throw new NotImplementedException (); public int Count get;
| Comportamento | Aggiunge un articolo alla fine della coda. |
| Prestazione | O (1) |
Questa implementazione aggiunge l'elemento all'inizio dell'elenco collegato. L'oggetto potrebbe essere aggiunto alla fine della lista. Tutto ciò che conta davvero è che gli oggetti sono accodati ad una estremità della lista e desaccati dall'altra (FIFO). Si noti che questo è l'opposto della classe Stack in cui gli articoli vengono aggiunti e rimossi dalla stessa estremità (LIFO).
Public void Enqueue (valore T) _items.AddFirst (valore);
| Comportamento | Rimuove e restituisce l'elemento più vecchio dalla coda. Un InvalidOperationException viene lanciato se la coda è vuota. |
| Prestazione | O (1) |
Da Enqueue aggiunto l'elemento all'inizio della lista, dequeue deve rimuovere l'elemento alla fine dell'elenco. Se la coda non contiene elementi, viene generata un'eccezione.
public T Dequeue () if (_items.Count == 0) throw new InvalidOperationException ("La coda è vuota"); T last = _items.Tail.Value; _items.RemoveLast (); ritorno ultimo; | Comportamento | Restituisce l'elemento successivo che verrebbe restituito se si richiamassero Dequeue. La coda è rimasta invariata. Un'eccezione InvalidOperationException viene generata se la coda è vuota. |
| Prestazione | O (1) |
public T Peek () if (_items.Count == 0) throw new InvalidOperationException ("La coda è vuota"); return _items.Tail.Value; | Comportamento | Restituisce il numero di elementi attualmente in coda. Restituisce 0 se la coda è vuota. |
| Prestazione | O (1) |
public int Count get return _items.Count;
Una coda a doppio attacco, o deque, estende il comportamento della coda consentendo di aggiungere o rimuovere elementi da entrambi i lati della coda. Questo nuovo comportamento è utile in diversi domini problematici, in particolare task e scheduling dei thread. È anche generalmente utile per implementare altre strutture di dati. Vedremo un esempio dell'utilizzo di un deque per implementare un'altra struttura di dati in seguito.
Il deque la classe è supportata da una lista doppiamente collegata. Questo ci consente di aggiungere e rimuovere elementi dalla parte anteriore o posteriore dell'elenco e accedere a Primo e Scorso proprietà. Le principali modifiche tra la classe Queue e la classe Deque sono che il Enqueue, dequeue, e Sbirciare i metodi sono stati raddoppiati in Primo e Scorso varianti.
public class Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (valore T) throw new NotImplementedException (); public void EnqueueLast (valore T) throw new NotImplementedException (); public T DequeueFirst () throw new NotImplementedException (); public T DequeueLast () throw new NotImplementedException (); public T PeekFirst () throw new NotImplementedException (); public T PeekLast () throw new NotImplementedException (); public int Count get;
| Comportamento | Aggiunge il valore fornito al capo della coda. Questo sarà il prossimo oggetto dequeued da DequeueFirst. |
| Prestazione | O (1) |
public void EnqueueFirst (valore T) _items.AddFirst (valore);
| Comportamento | Aggiunge il valore fornito alla coda della coda. Questo sarà il prossimo oggetto dequeued da DequeueLast. |
| Prestazione | O (1) |
public void EnqueueLast (valore T) _items.AddLast (valore);
| Comportamento | Rimuove e restituisce il primo oggetto nel deque. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T DequeueFirst () if (_items.Count == 0) throw new InvalidOperationException ("DequeueFirst ha chiamato quando deque è vuoto"); T temp = _items.Head.Value; _items.RemoveFirst (); ritorno temp; | Comportamento | Rimuove e restituisce l'ultimo elemento nel deque. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T DequeueLast () if (_items.Count == 0) throw new InvalidOperationException ("DequeueLast ha chiamato quando deque è vuoto"); T temp = _items.Tail.Value; _items.RemoveLast (); ritorno temp; | Comportamento | Restituisce il primo oggetto nel deque, ma lascia la collezione invariata. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T PeekFirst () if (_items.Count == 0) throw new InvalidOperationException ("PeekFirst ha chiamato quando deque è vuoto"); return _items.Head.Value; | Comportamento | Restituisce l'ultimo elemento nel deque, ma lascia la raccolta invariata. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T PeekLast () if (_items.Count == 0) throw new InvalidOperationException ("PeekLast ha chiamato quando deque è vuoto"); return _items.Tail.Value; | Comportamento | Restituisce il numero di articoli attualmente nel deque, o 0 se il deque è vuoto. |
| Prestazione | O (1) |
public int Count get return _items.Count;
Deques sono spesso usati per implementare altre strutture di dati.
Abbiamo visto uno stack implementato usando a Lista collegata, quindi ora diamo un'occhiata a uno implementato usando a deque.
Potresti chiederti perché sceglierei di implementare un Pila usare un deque piuttosto che a Lista collegata. La ragione è una delle prestazioni e la riusabilità del codice. Un elenco collegato ha il costo dell'overhead per nodo e una ridotta localizzazione dei dati: gli elementi vengono allocati nell'heap e le posizioni di memoria potrebbero non essere vicine l'una all'altra, causando un numero maggiore di errori di cache e di errori di pagina nella CPU e nell'hardware di memoria livelli. Un'implementazione migliore di una coda potrebbe utilizzare un array come backing store piuttosto che come elenco. Ciò consentirebbe un minore sovraccarico per nodo e potrebbe migliorare le prestazioni affrontando alcuni problemi relativi alla località.
Implementazione a Pila o Coda come una matrice è un'implementazione più complessa, tuttavia. Implementando il deque in questo modo più complesso e utilizzandolo come base per altre strutture di dati, possiamo realizzare i vantaggi in termini di prestazioni per tutte le strutture, pur dovendo scrivere il codice una sola volta. Ciò accelera i tempi di sviluppo e riduce i costi di manutenzione.
Vedremo un esempio di a deque come un array più avanti in questa sezione, ma prima diamo un'occhiata a un esempio di a Pila implementato usando a deque.
public class Stack Deque _items = new Deque (); public void Push (valore T) _items.EnqueueFirst (valore); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count get return _items.Count;
Si noti che tutti i controlli degli errori sono ora rinviati a deque e qualsiasi ottimizzazione o correzione di bug apportata a deque si applicherà automaticamente al Pila classe. Implementazione a Coda è altrettanto facile e come tale è lasciato come esercizio al lettore.
Come accennato in precedenza, ci sono vantaggi nell'usare un array piuttosto che un elenco collegato come backing store per deque (una richiesta di numeri interi). Concettualmente questo sembra semplice, ma ci sono in realtà diversi problemi che devono essere affrontati affinché questo funzioni.
Diamo un'occhiata ad alcuni di questi problemi graficamente e poi vediamo come possiamo gestirli. Lungo il percorso, tieni presente i problemi relativi alla politica di crescita discussi nella sezione ArrayList e che gli stessi problemi si applicano qui.
Quando viene creata la raccolta, è una matrice di lunghezza 0. Diamo un'occhiata a come alcune azioni influenzano l'array interno. Mentre procediamo, osserviamo che la "h" verde e la "t" rossa nelle figure si riferiscono rispettivamente a "testa" e "coda". La testa e la coda sono gli indici di matrice che indicano il primo e l'ultimo elemento nella coda. Quando aggiungiamo e rimuoviamo gli oggetti, l'interazione tra testa e coda diventerà più chiara.
Deque deq = new Deque (); deq.EnqueueFirst (1);
Aggiungere un valore alla parte anteriore del deque deq.EnqueueLast (2);
Aggiunta di un valore alla fine del deque deq.EnqueueFirst (0);
Aggiungere un altro valore alla parte anteriore del deque; l'indice della testa si avvolge Notare cosa è successo a questo punto. L'indice della testa si è spostato verso la fine dell'array. Ora il primo oggetto del deque, cosa sarebbe stato restituito da DequeueFirst, è il valore nell'array index three (zero).
deq.EnqueueLast (3);
Aggiunta di un valore alla fine del deque A questo punto, la matrice è piena. Quando viene aggiunto un altro elemento, si verificherà quanto segue:
EnqueueFirst - L'articolo viene aggiunto allo zero dell'indice (l'operazione di copia lascia aperto).EnqueueLast - L'elemento viene aggiunto alla fine dell'array. deq.EnqueueLast (4);
Aggiunta di un valore alla fine del deque espanso Ora vediamo cosa succede quando gli oggetti vengono rimossi dal Deque.
deq.DequeueFirst ();
Rimozione del primo oggetto dal deque espanso deq.DequeueLast ();
Rimozione dell'ultimo elemento dal deque espanso Il punto critico da notare è che, indipendentemente dalla capacità dell'array interno, i contenuti logici del Deque sono gli elementi dall'indice di testa all'indice di coda, tenendo conto della necessità di avvolgere alla fine dell'array. Un array che fornisce il comportamento di avvolgere dalla testa alla coda è spesso noto come un buffer circolare.
Con questa comprensione di come funziona la logica dell'array, entriamo nel codice.
I metodi e le proprietà di Deque basati su array sono gli stessi di quelli basati su elenchi, quindi non verranno ripetuti qui. Tuttavia, la lista è stata sostituita con una matrice e ora ci sono tre proprietà per contenere le informazioni relative a dimensioni, testa e coda.
public class Deque T [] _items = new T [0]; // Il numero di elementi nella coda. int _size = 0; // L'indice del primo (più vecchio) elemento in coda. int _head = 0; // L'indice dell'ultimo (più recente) elemento in coda. int _tail = -1; ...
Quando l'array interno deve crescere, l'algoritmo per aumentare la dimensione dell'array, copiare i contenuti dell'array e aggiornare i valori dell'indice interno deve essere eseguito. Il Enqueue il metodo esegue quell'operazione ed è chiamato da entrambi EnqueueFirst e EnqueueLast. Il startingIndex parametro viene utilizzato per determinare se lasciare lo slot di matrice a zero dell'indice aperto (nel caso di EnqueueFirst).
Prestare particolare attenzione al modo in cui i dati vengono scartati nei casi in cui il passaggio dalla testa alla coda richiede di tornare indietro alla fine della matrice fino a zero.
private void allocateNewArray (int startingIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = new T [newLength]; if (_size> 0) int targetIndex = startingIndex; // Copia i contenuti ... // Se l'array non ha wrapping, copia l'intervallo valido. // Altrimenti, copia da capo a capo dell'array e poi da 0 a coda. // Se la coda è meno di testa, abbiamo avvolto. se (_tail < _head) // Copy the _items[head]… _items[end] -> newArray [0] ... newArray [N]. for (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1] ... per (int index = 0; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0] ... newArray [N] per (int index = _head; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; _head = startingIndex; _tail = targetIndex - 1; // Compensate for the extra bump. else // Nothing in the array. _head = 0; _tail = -1; _items = newArray;
| Comportamento | Aggiunge il valore fornito al capo della coda. Questo sarà il prossimo oggetto dequeued da DequeueFirst. |
| Prestazione | O (1) nella maggior parte dei casi; O (n) quando la crescita è necessaria. |
public void EnqueueFirst (T item) // Se l'array deve crescere. if (_items.Length == _size) allocateNewArray (1); // Poiché sappiamo che l'array non è pieno e _head è maggiore di 0, // sappiamo che lo slot davanti alla testa è aperto. if (_head> 0) _head-; else // Altrimenti abbiamo bisogno di tornare alla fine dell'array. _head = _items.Length - 1; _items [_head] = elemento; _size ++;
| Comportamento | Aggiunge il valore fornito alla coda della coda. Questo sarà il prossimo oggetto dequeued da DequeueLast. |
| Prestazione | O (1) nella maggior parte dei casi; O (n) quando la crescita è necessaria. |
public void EnqueueLast (T item) // Se l'array deve crescere. if (_items.Length == _size) allocateNewArray (0); // Ora abbiamo un array di dimensioni adeguate e possiamo concentrarci sui problemi di wrapping. // Se _tail è alla fine dell'array, dobbiamo avvolgere. if (_tail == _items.Length - 1) _tail = 0; else _tail ++; _items [_tail] = elemento; _size ++;
| Comportamento | Rimuove e restituisce il primo oggetto nel deque. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T DequeueFirst () if (_size == 0) throw new InvalidOperationException ("La deque è vuota"); Valore T = _items [_head]; if (_head == _items.Length - 1) // Se la testina è all'ultimo indice dell'array, avvolgila. _head = 0; else // Passa allo slot successivo. _head ++; _taglia--; valore di ritorno; | Comportamento | Rimuove e restituisce l'ultimo elemento nel deque. Un'eccezione InvalidOperationException viene generata se il deque è vuoto. |
| Prestazione | O (1) |
public T DequeueLast () if (_size == 0) throw new InvalidOperationException ("La deque è vuota"); Valore T = _items [_tail]; if (_tail == 0) // Se la coda è al primo indice dell'array, avvolgetela. _tail = _items.Length - 1; else // Passa allo slot precedente. _coda--; _taglia--; valore di ritorno; | Comportamento | Restituisce il primo oggetto nel deque, ma lascia la collezione invariata. Un InvalidOperationException viene lanciato se il deque è vuoto. |
| Prestazione | O (1) |
public T PeekFirst () if (_size == 0) throw new InvalidOperationException ("La deque è vuota"); return _items [_head]; | Comportamento | Restituisce l'ultimo elemento nel deque, ma lascia la raccolta invariata. Un InvalidOperationException viene lanciato se il deque è vuoto. |
| Prestazione | O (1) |
public T PeekLast () if (_size == 0) throw new InvalidOperationException ("La deque è vuota"); return _items [_tail]; | Comportamento | Restituisce il numero di articoli attualmente nel deque o 0 se il deque è vuoto. |
| Prestazione | O (1) |
public int Count get return _size;
