DOUG LLOYD: Quindi, se avete visto il video sullo stack, Probabilmente si tratta di andare a sentire come un po 'di déjà vu. Sta andando a un concetto molto simile, solo con una leggera torsione su di esso. Stiamo andando a parlare ora sulle code. Quindi una coda, simile ad una pila, un altro tipo di struttura dati che possiamo utilizzare per mantenere i dati in modo organizzato. Simile a una pila, può essere attuata come un array o una lista collegata. A differenza di una pila, le regole che usiamo per determinare quando le cose vengono aggiunti e rimossi dalla una coda sono un po 'diverso. A differenza di una pila, che è una struttura LIFO, last in, first out, una coda è un FIFO struttura, FIFO, first in, first out. Ora le code, probabilmente avere un'analogia di code. Se siete mai stati in coda al un parco di divertimenti o presso una banca, c'è una sorta di equità struttura di attuazione. La prima persona in linea al la banca è la prima persona che arriva a parlare con il cassiere. 

Sarebbe una sorta di gara al fondo se l'unico modo devi parlare con il cassiere al banca doveva essere l'ultima persona in linea. Ognuno avrebbe vogliono sempre di essere l'ultima persona in linea, e la persona che era prima ci che è stato in attesa per un po ', potrebbe essere lì per ore, e ore e ore prima che abbiano la possibilità di realtà ritirare i soldi in banca. E così le code sono una sorta di equità attuazione struttura. Ma questo non significa necessariamente che stack sono una brutta cosa, basta che le code sono un altro modo per farlo. Quindi, di nuovo una coda è prima in, first fuori, contro uno stack che durano in, first out. Simile a una pila, abbiamo due operazioni che possiamo eseguire su code. I nomi sono enqueue, che è quello di aggiungere un nuovo elemento alla fine della coda, e dequeue, che è per rimuovere il più antico elemento dalla testa alla coda. Quindi stiamo andando ad aggiungere elementi sull'estremità della coda, e stiamo andando a rimuovere gli elementi dalla parte anteriore della coda. Anche in questo caso, con lo stack, siamo stati l'aggiunta di elementi alla sommità della pila e rimozione di elementi dalla cima della pila. Quindi, con enqueue, è l'aggiunta di Alla fine, la rimozione dal davanti. Quindi la cosa più antica di là è sempre la prossima cosa uscire se cerchiamo e annullare l'accodamento qualcosa. 

Così ancora una volta, con le code, possiamo implementazioni basate su array e lista concatenata implementazioni basate su. Inizieremo di nuovo con implementazioni basate su array. La definizione della struttura sembra piuttosto simile. Abbiamo un altro array ci valore tipo di dati, in modo che possa contenere i tipi di dati arbitrari. Stiamo ancora intenzione di utilizzare interi in questo esempio. 

E proprio come con la nostra implementazione dello stack basata su array, perché stiamo usando un array, abbiamo necessariamente avere quella limitazione che tipo C di impone su di noi, che è noi non hanno alcun dinamismo nella nostra capacità di crescere e ridurre l'array. Dobbiamo decidere all'inizio ciò è il numero massimo di cose che siamo in grado di mettere in questo coda, e in questo caso, capacità sarebbe qualche libbra definito costante nel nostro codice. E ai fini della presente il video, la capacità sarà 10. 

Abbiamo bisogno di tenere traccia di la parte anteriore della coda così sappiamo che elemento vogliamo dequeue, e abbiamo anche bisogno di tenere traccia di qualcosa else-- il numero di elementi che abbiamo nel nostro coda. Si noti che non stiamo tenendo traccia della fine della coda, appena la dimensione della coda. E la ragione di che, si spera diventare un po 'più chiaro in un momento. Una volta che abbiamo completato questa definizione tipo, abbiamo un nuovo tipo di dati chiamato coda, che possiamo ora dichiarare variabili di questo tipo di dati. E un po 'confusamente, ho deciso chiamare questa coda q, la lettera q invece che il tipo di dati q. 

Quindi, ecco il nostro coda. Si tratta di una struttura. Esso contiene tre membri o tre campi, una serie di capacità dimensioni. In questo caso, la capacità è 10. E questo array è intenzione di tenere interi. In verde è la parte anteriore della nostra coda, la successivo elemento da rimuovere, e in rosso sarà la dimensione della coda, quanti elementi sono attualmente esistenti nella coda. Quindi, se diciamo uguali q.front 0, e la dimensione q.size uguale 0-- stiamo mettendo 0s in quei campi. E a questo punto, siamo più o meno pronto per iniziare a lavorare con la nostra coda. 

Quindi la prima operazione possiamo svolgere è quello di accodare qualcosa, aggiungere un nuovo elemento alla fine della coda. Beh, che cosa abbiamo bisogno di fare nel caso generale? Ebbene questa funzione enqueue esigenze accettare un puntatore alla nostra coda. Anche in questo caso, se avessimo dichiarato nostra coda a livello globale, non avremmo bisogno di fare questo necessariamente, ma in generale, bisogno di accettare i puntatori per strutture di dati così, perché altrimenti, stiamo passando da value-- siamo passando copie della coda, e quindi non siamo in realtà cambia la coda che abbiamo intenzione di cambiare. 

L'altra cosa che deve fare è accettare un elemento di dati del tipo appropriato. Anche in questo caso, è sta per essere interi, ma si potrebbe arbitrariamente dichiarare il tipo di dati come valore e utilizzare questo, più in generale. Questo è l'elemento che vogliamo accodare, vogliamo aggiungere alla fine della coda. Poi noi davvero vogliamo collocare i dati nella coda. In questo caso, ponendolo nel corretta posizione del nostro array, e poi vogliamo cambiare le dimensioni della coda, quanti elementi noi attualmente hanno. 

Quindi cerchiamo di iniziare. Ecco, ancora una volta, che il generale dichiarazione di funzione modulo per quello accodamento potrebbe essere simile. E qui andiamo. Facciamo enqueue il numero 28 nella coda. Allora cosa dobbiamo fare? Beh, la parte anteriore della nostra coda è a 0, e la dimensione della nostra coda è a 0, e quindi probabilmente vogliamo mettere il numero 28 a numero di elemento di matrice 0, giusto? Così ora abbiamo messo che lì dentro. Così ora che cosa dobbiamo cambiare? Noi non vogliamo cambiare la parte anteriore della coda, perché vogliamo sapere cosa elemento potremmo aver bisogno di annullare l'accodamento più tardi. Quindi la ragione che abbiamo davanti ci è una sorta di un indicatore di ciò che è la cosa più antica della matrice. Beh, la cosa più antica della array-- in Infatti, l'unica cosa al campo di destra now-- è 28, che è a matrice posizione 0. Quindi noi non vogliamo cambiare quel numero verde, perché questo è l'elemento più antico. Piuttosto, vogliamo cambiare le dimensioni. Quindi, in questo caso, faremo incrementare le dimensioni di 1. 

Ora una sorta di generale un'idea di dove il prossimo elemento sta per andare in una coda è quello di aggiungere questi due numeri insieme, anteriore e dimensioni, e che ti dirò dove il prossimo elemento in coda sta per andare. Quindi, ora diamo enqueue un altro numero. Andiamo enqueue 33. Così 33 sta per andare in array di posizione 0 e 1. Quindi, in questo caso, sta andando per entrare in posizione 1 campo, e ora la dimensione della nostra coda è 2. 

Anche in questo caso, non stiamo cambiando la parte anteriore della nostra coda, perché 28 è ancora il elemento più antico, e noi vogliono a-- quando siamo finalmente otteniamo per l'accodamento, la rimozione di elementi da questa coda, vogliamo sapere dove l'elemento è più vecchia. E così abbiamo sempre bisogno di mantenere qualche indicatore di dove si trova. Ecco, questo è ciò che la 0 è lì per. Questo è ciò che davanti è lì per. 

Facciamo in accodamento un elemento in più, 19. Sono sicuro che si può intuire dove 19 sta per andare. E 'intenzione di andare in array di posizione numero 2. Ecco 0 più 2. Ed ora le dimensioni del nostro coda è di 3. Abbiamo 3 elementi in esso. Quindi, se dovessimo, e non stiamo andando in questo momento, accodare un altro elemento, sarebbe andare in posizione di matrice 3, e la dimensione della nostra coda sarebbe 4. Così abbiamo accodato diversi elementi ora. Ora cominciamo a rimuoverli. Diamo loro dequeue dalla coda. 

Così simile al pop, che è una specie dell'analogo di questo per pile, dequeue bisogno di accettare un puntatore al queue-- nuovo, meno che non sia dichiarato a livello globale. Ora vogliamo cambiare la posizione della parte anteriore della coda. Questo è dove si parla una sorta di in gioco, quella variabile anteriore, perché una volta togliamo un elemento, vogliamo per passare al successivo elemento più antico. 

Poi vogliamo diminuire la dimensione della coda, e poi vogliamo restituire il valore che è stato rimosso dalla coda. Ancora una volta, non vogliamo scartare proprio questo. Siamo presumibilmente estraiamo dal queue-- siamo accodamento perché ci preoccupiamo di esso. Così vogliamo questa funzione per tornare un dato di valore tipo. Anche in questo caso, il valore è un numero intero. 

Quindi, ora diamo DEQUEUE qualcosa. Rimuoviamo un elemento dalla coda. Se diciamo int x equivale & q, commerciale q-- ancora una volta che è un puntatore a questi dati q structure-- quale elemento sta per essere rimosse dalla coda? In questo caso, perché è una prima in, first out struttura di dati, FIFO, la prima cosa che abbiamo messo in questo coda era 28, e quindi in questo caso, stiamo andando a prendere 28 di la coda, non 19, che è ciò che avremmo fatto se questa fosse una pila. Stiamo andando a prendere 28 dalla coda. 

Simile a quello che abbiamo fatto con una pila, non siamo in realtà andando a eliminare 28 dalla coda stessa, stiamo solo andando a tipo di far finta che non c'è. Così sta andando a stare lì in memoria, ma siamo solo andando a tipo di ignorarlo spostando gli altri due campi di nostri dati q struttura. Stiamo per cambiare l'anteriore. Q.front è ora di andare a essere 1, perché è ora l'elemento più antico che abbiamo nel nostro coda, perché abbiamo già rimosso 28, che è stato il primo elemento più antico. 

Ed ora, vogliamo cambiare la dimensione della coda a due elementi invece di tre. Ora ricordate in precedenza ho detto quando abbiamo vogliono aggiungere elementi alla coda, abbiamo messo in una posizione di matrice che è la somma di fronte e dimensione. Quindi, in questo caso, stiamo ancora mettendo esso, l'elemento successivo nella coda, in posizione matrice 3, e vedremo che in un secondo. 

Così ora abbiamo rimosse dalla coda nostro primo elemento dalla coda. Facciamolo ancora. Rimuoviamo un altro elemento dalla coda. Nel caso, la corrente più vecchio elemento è la posizione 1 campo. Questo è quello che ci dice q.front. Quella scatola verde ci dice che questo è l'elemento più antico. E così, x diventerà 33. Dobbiamo solo tipo di dimenticare 33 che esiste nella matrice, e diremo che ora, il nuovo elemento meno recente nella coda è in posizione di matrice 2, e la dimensione della coda, il numero di elementi abbiamo in coda, è di 1. Ora diamo enqueue qualcosa, e io tipo di dato questa via un secondo fa, ma se vogliamo mettere 40 nel coda, dove è 40 intenzione di andare? Bene, noi stiamo mettendo esso in q.front più coda di formato, e così ha senso in realtà per mettere 40 qui. Ora notate che al un certo punto, stiamo andando per arrivare alla fine la nostra gamma all'interno di q, ma che sbiadito fuori 28 e 33-- sono in realtà, tecnicamente spazi aperti, giusto? E così, possiamo eventually-- che regola di aggiungere quei due together-- possiamo finalmente necessario mod dalle dimensioni della capacità così possiamo avvolgere intorno. 

Quindi, se si arriva a elemento numero 10, se siamo sostituendolo in numero di elemento 10, saremmo in realtà messo in ordine posizione 0. E se stavamo andando a matrice mi posizione-- scusi, se li abbiamo aggiunto insieme, e abbiamo avuto modo di numero 11 sarebbe dove avremmo dovuto mettere esso, che non esiste in questo array-- sarebbe andare fuori dai limiti. Potremmo mod del 10 e mettere in posizione 1 campo. Ecco come funzionano le code. Stanno sempre intenzione di andare da sinistra a destra e, eventualmente, avvolgere intorno. E sai che sono completo se la dimensione, quella scatola rossa, diventa uguale alla capacità. E così dopo abbiamo aggiunto 40 al coda, bene che cosa dobbiamo fare? Ebbene, l'elemento più antico nella coda è ancora 19, quindi non vogliamo cambiare la parte anteriore della coda, ma ora abbiamo due elementi in coda, e così vogliamo aumentare la nostra dimensione 1-2. 

Questo è più o meno con lavorare con code basate su array, e simili per impilare, vi è anche un modo attuare una coda come una lista collegata. Ora, se questo tipo di struttura dati sembra familiare a voi, lo è. Non è una lista concatenata, si tratta di una lista doppiamente concatenata. Ed ora, per inciso, è effettivamente possibile implementare una coda come una lista concatenata, ma Penso che in termini di visualizzazione, in realtà potrebbe aiutare a visualizzare questo come una lista doppiamente concatenata. Ma è sicuramente possibile fare questo come una lista concatenata. 

Quindi cerchiamo di avere uno sguardo a ciò che questo potrebbe essere simile. Se vogliamo enquue-- così ora, ancora una volta siamo il passaggio a una lista collegata modello basato qui. Se vogliamo accodare, vogliamo aggiungere un nuovo elemento, ben che cosa dobbiamo fare? Ebbene, prima di tutto, perché stiamo aggiungendo alla fine e togliere dal inizio, probabilmente vogliono mantenere i puntatori sia per il testa e la coda della lista collegata? Coda di essere un altro termine per alla fine della lista collegata, l'ultimo elemento della lista collegata. E questi probabilmente, ancora una volta, essere vantaggioso per noi se sono variabili globali. Ma ora, se vogliamo aggiungere un nuovo elemento che cosa dobbiamo fare? Quello che abbiamo appena [? malak?] o dinamicamente allocare il nostro nuovo nodo per noi stessi. E poi, come proprio quando aggiungiamo qualsiasi elemento di una lista che doppiamente collegata, resta che ordinare di-- questi ultimi tre passaggi qui sono solo tutto sullo spostamento della puntatori nel modo corretto in modo che l'elemento viene inserito la catena senza rompere la catena o fare un qualche tipo di errore o che hanno qualche tipo di incidente accadere quale noi accidentalmente orfani alcuni elementi della nostra coda. Ecco che cosa questo potrebbe essere simile. Vogliamo aggiungere l'elemento 10 alla fine di questa coda. Quindi l'elemento più vecchio qui è rappresentato dalla testa. Questa è la prima cosa che abbiamo messo in questo ipotetico coda di qui. E coda, 13, è la più recentemente aggiunto elemento. E così, se vogliamo accodare 10 in questa coda, vogliamo metterlo dopo il 13. E così stiamo andando a dinamicamente allocare spazio per un nuovo nodo e verificare la presenza di nulla per assicurarsi che non abbiamo un errore di memoria. Poi andremo a mettere 10 in quel nodo, e ora abbiamo bisogno di stare attenti su come si organizzano i puntatori in modo da non rompere la catena. 

Siamo in grado di impostare 10 del precedente campo per puntare di nuovo al vecchio coda, e dal '10 sarà la nuova coda ad un certo punto dal momento tutti questi catene sono collegate, niente sta andando a venire dopo le 10 in questo momento. E così 10 del prossimo puntatore punterà su null, e poi dopo faremo questo, dopo che avremo 10 collegata a ritroso alla catena, possiamo prendere la vecchia testa, o, scusa me, il vecchio coda della coda. Il vecchio fine della coda, 13, e farlo puntare a 10. E ora, a questo punto, abbiamo accodato il numero 10 in questa coda. Tutto quello che dobbiamo fare ora è solo spostare il coda per puntare 10 invece che a 13. 

Annullamento dell'accodamento è in realtà molto simile a popping da una risma implementato come una lista collegata se hai visto il video pile. Tutto quello che dobbiamo fare è iniziare a inizio, trovare il secondo elemento, liberare il primo elemento, e quindi spostare la testa per puntare al secondo elemento. Probabilmente meglio per visualizzarlo tanto per essere chiari al riguardo in più. Quindi, ecco di nuovo la nostra coda. 12 è l'elemento più vecchio nella nostra coda, la testa. 10 è l'elemento più recente nella nostra coda, la nostra coda. 

E così quando vogliamo per annullare l'accodamento di un elemento, vogliamo rimuovere l'elemento più antico. Allora cosa facciamo? Beh, abbiamo fissato un puntatore attraversamento che inizia in testa, e si passa in modo che punti al secondo elemento di questo queue-- qualcosa dicendo trav uguale trav freccia successiva, per esempio, si muoverebbe trav lì per puntare a 15, il quale, dopo si dequeue 12, o dopo togliamo 12, sarà diventare l'elemento quindi più antica. 

Ora abbiamo una presa sulla prima elemento via la testa puntatore e il secondo elemento tramite il puntatore trav. Possiamo testa ora libero, e allora possiamo dire nulla viene prima 15 più. Così possiamo cambiare 15 del precedente puntatore per puntare a null, e abbiamo appena spostiamo la testa sopra. E ce ne andiamo. Ora abbiamo con successo rimosse dalla coda 12, e ora siamo avere un'altra coda di 4 elementi. Questo è praticamente tutto c'è da code, entrambi matrice-based e lista concatenata based. Sono Doug Lloyd. Questo è CS 50.