1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Quindi, se avete
visto il video sullo stack,

3
00:00:07,370 --> 00:00:09,870
Probabilmente si tratta di andare a sentire
come un po 'di déjà vu.

4
00:00:09,870 --> 00:00:13,850
Sta andando a un concetto molto simile,
solo con una leggera torsione su di esso.

5
00:00:13,850 --> 00:00:15,530
Stiamo andando a parlare ora sulle code.

6
00:00:15,530 --> 00:00:19,350
Quindi una coda, simile ad una pila,
un altro tipo di struttura dati

7
00:00:19,350 --> 00:00:22,412
che possiamo utilizzare per mantenere
i dati in modo organizzato.

8
00:00:22,412 --> 00:00:24,120
Simile a una pila,
può essere attuata

9
00:00:24,120 --> 00:00:27,000
come un array o una lista collegata.

10
00:00:27,000 --> 00:00:30,320
A differenza di una pila, le regole
che usiamo per determinare

11
00:00:30,320 --> 00:00:34,210
quando le cose vengono aggiunti e rimossi dalla
una coda sono un po 'diverso.

12
00:00:34,210 --> 00:00:36,590
>> A differenza di una pila, che
è una struttura LIFO,

13
00:00:36,590 --> 00:00:45,610
last in, first out, una coda è un FIFO
struttura, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Ora le code, probabilmente
avere un'analogia di code.

15
00:00:49,320 --> 00:00:52,820
Se siete mai stati in coda al
un parco di divertimenti o presso una banca,

16
00:00:52,820 --> 00:00:56,430
c'è una sorta di equità
struttura di attuazione.

17
00:00:56,430 --> 00:00:59,160
La prima persona in linea al
la banca è la prima persona

18
00:00:59,160 --> 00:01:00,760
che arriva a parlare con il cassiere.

19
00:01:00,760 --> 00:01:03,522
>> Sarebbe una sorta di gara
al fondo se l'unico modo

20
00:01:03,522 --> 00:01:06,730
devi parlare con il cassiere al
banca doveva essere l'ultima persona in linea.

21
00:01:06,730 --> 00:01:09,146
Ognuno avrebbe vogliono sempre
di essere l'ultima persona in linea,

22
00:01:09,146 --> 00:01:12,580
e la persona che era prima ci
che è stato in attesa per un po ',

23
00:01:12,580 --> 00:01:14,715
potrebbe essere lì per ore,
e ore e ore

24
00:01:14,715 --> 00:01:17,590
prima che abbiano la possibilità di realtà
ritirare i soldi in banca.

25
00:01:17,590 --> 00:01:22,510
E così le code sono una sorta di
equità attuazione struttura.

26
00:01:22,510 --> 00:01:25,780
Ma questo non significa necessariamente
che stack sono una brutta cosa, basta

27
00:01:25,780 --> 00:01:28,160
che le code sono un altro modo per farlo.

28
00:01:28,160 --> 00:01:32,420
Quindi, di nuovo una coda è prima in, first
fuori, contro uno stack che durano in,

29
00:01:32,420 --> 00:01:34,440
first out.

30
00:01:34,440 --> 00:01:36,190
Simile a una pila,
abbiamo due operazioni

31
00:01:36,190 --> 00:01:38,470
che possiamo eseguire su code.

32
00:01:38,470 --> 00:01:43,910
I nomi sono enqueue, che è quello di aggiungere
un nuovo elemento alla fine della coda,

33
00:01:43,910 --> 00:01:47,330
e dequeue, che è
per rimuovere il più antico

34
00:01:47,330 --> 00:01:49,670
elemento dalla testa alla coda.

35
00:01:49,670 --> 00:01:53,600
Quindi stiamo andando ad aggiungere elementi
sull'estremità della coda,

36
00:01:53,600 --> 00:01:57,220
e stiamo andando a rimuovere gli elementi
dalla parte anteriore della coda.

37
00:01:57,220 --> 00:02:00,790
Anche in questo caso, con lo stack, siamo stati l'aggiunta di
elementi alla sommità della pila

38
00:02:00,790 --> 00:02:03,380
e rimozione di elementi
dalla cima della pila.

39
00:02:03,380 --> 00:02:07,570
Quindi, con enqueue, è l'aggiunta di
Alla fine, la rimozione dal davanti.

40
00:02:07,570 --> 00:02:10,639
Quindi la cosa più antica di là
è sempre la prossima cosa

41
00:02:10,639 --> 00:02:13,620
uscire se cerchiamo
e annullare l'accodamento qualcosa.

42
00:02:13,620 --> 00:02:18,330
>> Così ancora una volta, con le code, possiamo
implementazioni basate su array

43
00:02:18,330 --> 00:02:20,110
e lista concatenata implementazioni basate su.

44
00:02:20,110 --> 00:02:24,620
Inizieremo di nuovo con
implementazioni basate su array.

45
00:02:24,620 --> 00:02:27,070
La definizione della struttura
sembra piuttosto simile.

46
00:02:27,070 --> 00:02:30,720
Abbiamo un altro array
ci valore tipo di dati,

47
00:02:30,720 --> 00:02:32,690
in modo che possa contenere i tipi di dati arbitrari.

48
00:02:32,690 --> 00:02:35,570
Stiamo ancora intenzione di utilizzare
interi in questo esempio.

49
00:02:35,570 --> 00:02:39,830
>> E proprio come con la nostra
implementazione dello stack basata su array,

50
00:02:39,830 --> 00:02:42,340
perché stiamo usando un
array, abbiamo necessariamente

51
00:02:42,340 --> 00:02:46,850
avere quella limitazione che tipo C
di impone su di noi, che è noi

52
00:02:46,850 --> 00:02:51,670
non hanno alcun dinamismo nella nostra
capacità di crescere e ridurre l'array.

53
00:02:51,670 --> 00:02:55,710
Dobbiamo decidere all'inizio
ciò è il numero massimo di cose

54
00:02:55,710 --> 00:02:59,300
che siamo in grado di mettere in questo
coda, e in questo caso,

55
00:02:59,300 --> 00:03:02,070
capacità sarebbe qualche libbra
definito costante nel nostro codice.

56
00:03:02,070 --> 00:03:05,430
E ai fini della presente
il video, la capacità sarà 10.

57
00:03:05,430 --> 00:03:07,690
>> Abbiamo bisogno di tenere traccia di
la parte anteriore della coda

58
00:03:07,690 --> 00:03:11,160
così sappiamo che elemento
vogliamo dequeue,

59
00:03:11,160 --> 00:03:15,070
e abbiamo anche bisogno di tenere traccia di
qualcosa else-- il numero di elementi

60
00:03:15,070 --> 00:03:16,690
che abbiamo nel nostro coda.

61
00:03:16,690 --> 00:03:19,360
Si noti che non stiamo tenendo traccia
della fine della coda, appena

62
00:03:19,360 --> 00:03:21,150
la dimensione della coda.

63
00:03:21,150 --> 00:03:24,310
E la ragione di che, si spera
diventare un po 'più chiaro in un momento.

64
00:03:24,310 --> 00:03:26,143
Una volta che abbiamo completato
questa definizione tipo,

65
00:03:26,143 --> 00:03:29,080
abbiamo un nuovo tipo di dati
chiamato coda, che possiamo ora

66
00:03:29,080 --> 00:03:30,630
dichiarare variabili di questo tipo di dati.

67
00:03:30,630 --> 00:03:35,350
E un po 'confusamente, ho deciso
chiamare questa coda q, la lettera

68
00:03:35,350 --> 00:03:38,090
q invece che il tipo di dati q.

69
00:03:38,090 --> 00:03:39,600
>> Quindi, ecco il nostro coda.

70
00:03:39,600 --> 00:03:40,700
Si tratta di una struttura.

71
00:03:40,700 --> 00:03:45,730
Esso contiene tre membri o tre
campi, una serie di capacità dimensioni.

72
00:03:45,730 --> 00:03:47,340
In questo caso, la capacità è 10.

73
00:03:47,340 --> 00:03:49,580
E questo array è
intenzione di tenere interi.

74
00:03:49,580 --> 00:03:55,240
In verde è la parte anteriore della nostra coda, la
successivo elemento da rimuovere, e in rosso

75
00:03:55,240 --> 00:03:58,610
sarà la dimensione della coda,
quanti elementi sono attualmente

76
00:03:58,610 --> 00:04:01,190
esistenti nella coda.

77
00:04:01,190 --> 00:04:05,300
Quindi, se diciamo uguali q.front
0, e la dimensione q.size uguale 0--

78
00:04:05,300 --> 00:04:07,120
stiamo mettendo 0s in quei campi.

79
00:04:07,120 --> 00:04:11,070
E a questo punto, siamo più o meno
pronto per iniziare a lavorare con la nostra coda.

80
00:04:11,070 --> 00:04:14,140
>> Quindi la prima operazione possiamo
svolgere è quello di accodare qualcosa,

81
00:04:14,140 --> 00:04:16,860
aggiungere un nuovo elemento
alla fine della coda.

82
00:04:16,860 --> 00:04:19,089
Beh, che cosa abbiamo bisogno di
fare nel caso generale?

83
00:04:19,089 --> 00:04:23,690
Ebbene questa funzione enqueue esigenze
accettare un puntatore alla nostra coda.

84
00:04:23,690 --> 00:04:26,370
Anche in questo caso, se avessimo dichiarato
nostra coda a livello globale,

85
00:04:26,370 --> 00:04:29,490
non avremmo bisogno di fare questo
necessariamente, ma in generale,

86
00:04:29,490 --> 00:04:32,330
bisogno di accettare i puntatori
per strutture di dati

87
00:04:32,330 --> 00:04:35,040
così, perché altrimenti,
stiamo passando da value-- siamo

88
00:04:35,040 --> 00:04:38,140
passando copie della coda,
e quindi non siamo in realtà cambia

89
00:04:38,140 --> 00:04:41,050
la coda che abbiamo intenzione di cambiare.

90
00:04:41,050 --> 00:04:44,860
>> L'altra cosa che deve fare è accettare
un elemento di dati del tipo appropriato.

91
00:04:44,860 --> 00:04:46,818
Anche in questo caso, è
sta per essere interi,

92
00:04:46,818 --> 00:04:49,330
ma si potrebbe arbitrariamente
dichiarare il tipo di dati come valore

93
00:04:49,330 --> 00:04:51,160
e utilizzare questo, più in generale.

94
00:04:51,160 --> 00:04:56,030
Questo è l'elemento che vogliamo accodare,
vogliamo aggiungere alla fine della coda.

95
00:04:56,030 --> 00:04:58,573
Poi noi davvero vogliamo
collocare i dati nella coda.

96
00:04:58,573 --> 00:05:01,490
In questo caso, ponendolo nel
corretta posizione del nostro array,

97
00:05:01,490 --> 00:05:05,040
e poi vogliamo cambiare le dimensioni
della coda, quanti elementi noi

98
00:05:05,040 --> 00:05:07,050
attualmente hanno.

99
00:05:07,050 --> 00:05:07,990
>> Quindi cerchiamo di iniziare.

100
00:05:07,990 --> 00:05:10,890
Ecco, ancora una volta, che il generale
dichiarazione di funzione modulo

101
00:05:10,890 --> 00:05:13,980
per quello accodamento potrebbe essere simile.

102
00:05:13,980 --> 00:05:14,910
E qui andiamo.

103
00:05:14,910 --> 00:05:18,335
Facciamo enqueue il numero
28 nella coda.

104
00:05:18,335 --> 00:05:19,460
Allora cosa dobbiamo fare?

105
00:05:19,460 --> 00:05:23,390
Beh, la parte anteriore della nostra coda è
a 0, e la dimensione della nostra coda

106
00:05:23,390 --> 00:05:29,680
è a 0, e quindi probabilmente vogliamo mettere
il numero 28 a numero di elemento di matrice

107
00:05:29,680 --> 00:05:31,124
0, giusto?

108
00:05:31,124 --> 00:05:32,540
Così ora abbiamo messo che lì dentro.

109
00:05:32,540 --> 00:05:34,820
Così ora che cosa dobbiamo cambiare?

110
00:05:34,820 --> 00:05:37,090
Noi non vogliamo cambiare
la parte anteriore della coda,

111
00:05:37,090 --> 00:05:40,850
perché vogliamo sapere cosa elemento
potremmo aver bisogno di annullare l'accodamento più tardi.

112
00:05:40,850 --> 00:05:44,020
Quindi la ragione che abbiamo davanti ci
è una sorta di un indicatore di ciò che è

113
00:05:44,020 --> 00:05:46,439
la cosa più antica della matrice.

114
00:05:46,439 --> 00:05:49,730
Beh, la cosa più antica della array-- in
Infatti, l'unica cosa al campo di destra

115
00:05:49,730 --> 00:05:53,540
now-- è 28, che è
a matrice posizione 0.

116
00:05:53,540 --> 00:05:56,160
Quindi noi non vogliamo
cambiare quel numero verde,

117
00:05:56,160 --> 00:05:57,910
perché questo è l'elemento più antico.

118
00:05:57,910 --> 00:06:00,510
Piuttosto, vogliamo cambiare le dimensioni.

119
00:06:00,510 --> 00:06:04,110
Quindi, in questo caso, faremo
incrementare le dimensioni di 1.

120
00:06:04,110 --> 00:06:08,430
>> Ora una sorta di generale un'idea di dove il
prossimo elemento sta per andare in una coda

121
00:06:08,430 --> 00:06:12,310
è quello di aggiungere questi due numeri
insieme, anteriore e dimensioni,

122
00:06:12,310 --> 00:06:16,390
e che ti dirò dove il prossimo
elemento in coda sta per andare.

123
00:06:16,390 --> 00:06:18,130
Quindi, ora diamo enqueue un altro numero.

124
00:06:18,130 --> 00:06:20,250
Andiamo enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Così 33 sta per andare in
array di posizione 0 e 1.

126
00:06:24,480 --> 00:06:26,840
Quindi, in questo caso, sta andando
per entrare in posizione 1 campo,

127
00:06:26,840 --> 00:06:29,500
e ora la dimensione della nostra coda è 2.

128
00:06:29,500 --> 00:06:31,840
>> Anche in questo caso, non stiamo cambiando
la parte anteriore della nostra coda,

129
00:06:31,840 --> 00:06:34,730
perché 28 è ancora il
elemento più antico, e noi

130
00:06:34,730 --> 00:06:38,220
vogliono a-- quando siamo finalmente otteniamo
per l'accodamento, la rimozione di elementi

131
00:06:38,220 --> 00:06:43,300
da questa coda, vogliamo sapere
dove l'elemento è più vecchia.

132
00:06:43,300 --> 00:06:48,620
E così abbiamo sempre bisogno di mantenere
qualche indicatore di dove si trova.

133
00:06:48,620 --> 00:06:50,410
Ecco, questo è ciò che la 0 è lì per.

134
00:06:50,410 --> 00:06:52,910
Questo è ciò che davanti è lì per.

135
00:06:52,910 --> 00:06:55,022
>> Facciamo in accodamento un elemento in più, 19.

136
00:06:55,022 --> 00:06:56,980
Sono sicuro che si può intuire
dove 19 sta per andare.

137
00:06:56,980 --> 00:06:59,860
E 'intenzione di andare in
array di posizione numero 2.

138
00:06:59,860 --> 00:07:01,570
Ecco 0 più 2.

139
00:07:01,570 --> 00:07:03,199
Ed ora le dimensioni del nostro coda è di 3.

140
00:07:03,199 --> 00:07:04,240
Abbiamo 3 elementi in esso.

141
00:07:04,240 --> 00:07:08,490
Quindi, se dovessimo, e non stiamo andando
in questo momento, accodare un altro elemento,

142
00:07:08,490 --> 00:07:11,370
sarebbe andare in posizione di matrice
3, e la dimensione della nostra coda

143
00:07:11,370 --> 00:07:13,160
sarebbe 4.

144
00:07:13,160 --> 00:07:15,279
Così abbiamo accodato diversi elementi ora.

145
00:07:15,279 --> 00:07:16,570
Ora cominciamo a rimuoverli.

146
00:07:16,570 --> 00:07:19,450
Diamo loro dequeue dalla coda.

147
00:07:19,450 --> 00:07:23,340
>> Così simile al pop, che è una specie
dell'analogo di questo per pile,

148
00:07:23,340 --> 00:07:26,180
dequeue bisogno di accettare un
puntatore al queue-- nuovo,

149
00:07:26,180 --> 00:07:28,140
meno che non sia dichiarato a livello globale.

150
00:07:28,140 --> 00:07:31,610
Ora vogliamo cambiare la posizione
della parte anteriore della coda.

151
00:07:31,610 --> 00:07:35,050
Questo è dove si parla una sorta di
in gioco, quella variabile anteriore,

152
00:07:35,050 --> 00:07:37,310
perché una volta togliamo
un elemento, vogliamo

153
00:07:37,310 --> 00:07:40,720
per passare al successivo elemento più antico.

154
00:07:40,720 --> 00:07:44,180
>> Poi vogliamo diminuire
la dimensione della coda,

155
00:07:44,180 --> 00:07:47,130
e poi vogliamo restituire il valore
che è stato rimosso dalla coda.

156
00:07:47,130 --> 00:07:48,921
Ancora una volta, non vogliamo scartare proprio questo.

157
00:07:48,921 --> 00:07:51,170
Siamo presumibilmente estraiamo
dal queue-- siamo

158
00:07:51,170 --> 00:07:54,170
accodamento perché ci preoccupiamo di esso.

159
00:07:54,170 --> 00:08:01,080
Così vogliamo questa funzione per tornare
un dato di valore tipo.

160
00:08:01,080 --> 00:08:04,360
Anche in questo caso, il valore è un numero intero.

161
00:08:04,360 --> 00:08:05,670
>> Quindi, ora diamo DEQUEUE qualcosa.

162
00:08:05,670 --> 00:08:09,310
Rimuoviamo un elemento dalla coda.

163
00:08:09,310 --> 00:08:15,970
Se diciamo int x equivale & q, commerciale q--
ancora una volta che è un puntatore a questi dati q

164
00:08:15,970 --> 00:08:20,177
structure-- quale elemento
sta per essere rimosse dalla coda?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
In questo caso, perché è una prima
in, first out struttura di dati, FIFO,

167
00:08:29,480 --> 00:08:33,690
la prima cosa che abbiamo messo in questo
coda era 28, e quindi in questo caso,

168
00:08:33,690 --> 00:08:37,245
stiamo andando a prendere 28 di
la coda, non 19, che è ciò che

169
00:08:37,245 --> 00:08:38,870
avremmo fatto se questa fosse una pila.

170
00:08:38,870 --> 00:08:42,220
Stiamo andando a prendere 28 dalla coda.

171
00:08:42,220 --> 00:08:44,960
>> Simile a quello che abbiamo fatto con
una pila, non siamo in realtà

172
00:08:44,960 --> 00:08:47,345
andando a eliminare 28
dalla coda stessa,

173
00:08:47,345 --> 00:08:49,470
stiamo solo andando a tipo
di far finta che non c'è.

174
00:08:49,470 --> 00:08:51,678
Così sta andando a stare lì
in memoria, ma siamo solo

175
00:08:51,678 --> 00:08:57,820
andando a tipo di ignorarlo spostando
gli altri due campi di nostri dati q

176
00:08:57,820 --> 00:08:58,830
struttura.

177
00:08:58,830 --> 00:09:00,230
Stiamo per cambiare l'anteriore.

178
00:09:00,230 --> 00:09:04,290
Q.front è ora di andare a
essere 1, perché è ora

179
00:09:04,290 --> 00:09:07,740
l'elemento più antico che abbiamo nel nostro
coda, perché abbiamo già rimosso 28,

180
00:09:07,740 --> 00:09:10,460
che è stato il primo elemento più antico.

181
00:09:10,460 --> 00:09:13,540
>> Ed ora, vogliamo cambiare
la dimensione della coda

182
00:09:13,540 --> 00:09:15,780
a due elementi invece di tre.

183
00:09:15,780 --> 00:09:20,450
Ora ricordate in precedenza ho detto quando abbiamo
vogliono aggiungere elementi alla coda,

184
00:09:20,450 --> 00:09:26,000
abbiamo messo in una posizione di matrice
che è la somma di fronte e dimensione.

185
00:09:26,000 --> 00:09:29,050
Quindi, in questo caso, stiamo ancora mettendo
esso, l'elemento successivo nella coda,

186
00:09:29,050 --> 00:09:33,360
in posizione matrice 3, e
vedremo che in un secondo.

187
00:09:33,360 --> 00:09:35,730
>> Così ora abbiamo rimosse dalla coda nostro
primo elemento dalla coda.

188
00:09:35,730 --> 00:09:36,480
Facciamolo ancora.

189
00:09:36,480 --> 00:09:38,696
Rimuoviamo un altro
elemento dalla coda.

190
00:09:38,696 --> 00:09:42,400
Nel caso, la corrente più vecchio
elemento è la posizione 1 campo.

191
00:09:42,400 --> 00:09:44,220
Questo è quello che ci dice q.front.

192
00:09:44,220 --> 00:09:46,980
Quella scatola verde ci dice che
questo è l'elemento più antico.

193
00:09:46,980 --> 00:09:49,310
E così, x diventerà 33.

194
00:09:49,310 --> 00:09:52,130
Dobbiamo solo tipo di dimenticare
33 che esiste nella matrice,

195
00:09:52,130 --> 00:09:55,100
e diremo che ora, il
nuovo elemento meno recente nella coda

196
00:09:55,100 --> 00:09:58,900
è in posizione di matrice 2, e la dimensione
della coda, il numero di elementi

197
00:09:58,900 --> 00:10:02,152
abbiamo in coda, è di 1.

198
00:10:02,152 --> 00:10:05,110
Ora diamo enqueue qualcosa, e io
tipo di dato questa via un secondo fa,

199
00:10:05,110 --> 00:10:10,340
ma se vogliamo mettere 40 nel
coda, dove è 40 intenzione di andare?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Bene, noi stiamo mettendo esso
in q.front più coda di formato,

202
00:10:17,730 --> 00:10:20,850
e così ha senso
in realtà per mettere 40 qui.

203
00:10:20,850 --> 00:10:22,840
Ora notate che al
un certo punto, stiamo andando

204
00:10:22,840 --> 00:10:27,980
per arrivare alla fine
la nostra gamma all'interno di q,

205
00:10:27,980 --> 00:10:32,010
ma che sbiadito fuori 28 e 33--
sono in realtà, tecnicamente

206
00:10:32,010 --> 00:10:33,300
spazi aperti, giusto?

207
00:10:33,300 --> 00:10:36,040
E così, possiamo eventually--
che regola di aggiungere

208
00:10:36,040 --> 00:10:40,390
quei due together-- possiamo finalmente
necessario mod dalle dimensioni della capacità

209
00:10:40,390 --> 00:10:41,410
così possiamo avvolgere intorno.

210
00:10:41,410 --> 00:10:43,620
>> Quindi, se si arriva a elemento
numero 10, se siamo

211
00:10:43,620 --> 00:10:48,790
sostituendolo in numero di elemento 10, saremmo
in realtà messo in ordine posizione 0.

212
00:10:48,790 --> 00:10:50,997
E se stavamo andando a
matrice mi posizione-- scusi,

213
00:10:50,997 --> 00:10:53,080
se li abbiamo aggiunto insieme,
e abbiamo avuto modo di numero

214
00:10:53,080 --> 00:10:56,330
11 sarebbe dove avremmo dovuto mettere
esso, che non esiste in questo array--

215
00:10:56,330 --> 00:10:58,200
sarebbe andare fuori dai limiti.

216
00:10:58,200 --> 00:11:03,367
Potremmo mod del 10 e mettere
in posizione 1 campo.

217
00:11:03,367 --> 00:11:04,450
Ecco come funzionano le code.

218
00:11:04,450 --> 00:11:08,540
Stanno sempre intenzione di andare da sinistra
a destra e, eventualmente, avvolgere intorno.

219
00:11:08,540 --> 00:11:11,280
E sai che sono
completo se la dimensione, quella scatola rossa,

220
00:11:11,280 --> 00:11:13,710
diventa uguale alla capacità.

221
00:11:13,710 --> 00:11:16,720
E così dopo abbiamo aggiunto 40 al
coda, bene che cosa dobbiamo fare?

222
00:11:16,720 --> 00:11:19,890
Ebbene, l'elemento più antico
nella coda è ancora 19,

223
00:11:19,890 --> 00:11:21,990
quindi non vogliamo cambiare
la parte anteriore della coda,

224
00:11:21,990 --> 00:11:23,820
ma ora abbiamo due
elementi in coda,

225
00:11:23,820 --> 00:11:28,710
e così vogliamo aumentare
la nostra dimensione 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Questo è più o meno con
lavorare con code basate su array,

227
00:11:31,820 --> 00:11:33,630
e simili per impilare,
vi è anche un modo

228
00:11:33,630 --> 00:11:36,450
attuare una coda come una lista collegata.

229
00:11:36,450 --> 00:11:40,150
Ora, se questo tipo di struttura dati
sembra familiare a voi, lo è.

230
00:11:40,150 --> 00:11:43,780
Non è una lista concatenata,
si tratta di una lista doppiamente concatenata.

231
00:11:43,780 --> 00:11:46,790
Ed ora, per inciso, è
effettivamente possibile implementare

232
00:11:46,790 --> 00:11:50,160
una coda come una lista concatenata, ma
Penso che in termini di visualizzazione,

233
00:11:50,160 --> 00:11:53,350
in realtà potrebbe aiutare a visualizzare
questo come una lista doppiamente concatenata.

234
00:11:53,350 --> 00:11:56,850
Ma è sicuramente possibile
fare questo come una lista concatenata.

235
00:11:56,850 --> 00:12:00,110
>> Quindi cerchiamo di avere uno sguardo a
ciò che questo potrebbe essere simile.

236
00:12:00,110 --> 00:12:02,750
Se vogliamo enquue--
così ora, ancora una volta siamo

237
00:12:02,750 --> 00:12:05,360
il passaggio a una lista collegata
modello basato qui.

238
00:12:05,360 --> 00:12:08,420
Se vogliamo accodare, vogliamo
aggiungere un nuovo elemento, ben

239
00:12:08,420 --> 00:12:09,730
che cosa dobbiamo fare?

240
00:12:09,730 --> 00:12:12,770
Ebbene, prima di tutto, perché
stiamo aggiungendo alla fine

241
00:12:12,770 --> 00:12:15,520
e togliere dal
inizio, probabilmente

242
00:12:15,520 --> 00:12:20,050
vogliono mantenere i puntatori sia per il
testa e la coda della lista collegata?

243
00:12:20,050 --> 00:12:22,660
Coda di essere un altro termine per
alla fine della lista collegata,

244
00:12:22,660 --> 00:12:24,496
l'ultimo elemento della lista collegata.

245
00:12:24,496 --> 00:12:26,620
E questi probabilmente,
ancora una volta, essere vantaggioso per noi

246
00:12:26,620 --> 00:12:28,477
se sono variabili globali.

247
00:12:28,477 --> 00:12:31,060
Ma ora, se vogliamo aggiungere un nuovo
elemento che cosa dobbiamo fare?

248
00:12:31,060 --> 00:12:35,262
Quello che abbiamo appena [? malak?] o dinamicamente
allocare il nostro nuovo nodo per noi stessi.

249
00:12:35,262 --> 00:12:38,220
E poi, come proprio quando aggiungiamo qualsiasi
elemento di una lista che doppiamente collegata,

250
00:12:38,220 --> 00:12:40,410
resta che ordinare di--
questi ultimi tre passaggi qui

251
00:12:40,410 --> 00:12:43,330
sono solo tutto sullo spostamento della
puntatori nel modo corretto

252
00:12:43,330 --> 00:12:46,710
in modo che l'elemento viene inserito
la catena senza rompere la catena

253
00:12:46,710 --> 00:12:49,580
o fare un qualche tipo di errore
o che hanno qualche tipo di incidente

254
00:12:49,580 --> 00:12:54,505
accadere quale noi accidentalmente
orfani alcuni elementi della nostra coda.

255
00:12:54,505 --> 00:12:55,880
Ecco che cosa questo potrebbe essere simile.

256
00:12:55,880 --> 00:13:00,980
Vogliamo aggiungere l'elemento
10 alla fine di questa coda.

257
00:13:00,980 --> 00:13:03,380
Quindi l'elemento più vecchio qui
è rappresentato dalla testa.

258
00:13:03,380 --> 00:13:06,800
Questa è la prima cosa che abbiamo messo
in questo ipotetico coda di qui.

259
00:13:06,800 --> 00:13:10,430
E coda, 13, è la più
recentemente aggiunto elemento.

260
00:13:10,430 --> 00:13:17,030
E così, se vogliamo accodare 10 in
questa coda, vogliamo metterlo dopo il 13.

261
00:13:17,030 --> 00:13:19,860
E così stiamo andando a dinamicamente
allocare spazio per un nuovo nodo

262
00:13:19,860 --> 00:13:23,280
e verificare la presenza di nulla per assicurarsi che
non abbiamo un errore di memoria.

263
00:13:23,280 --> 00:13:27,040
Poi andremo a
mettere 10 in quel nodo,

264
00:13:27,040 --> 00:13:30,030
e ora abbiamo bisogno di stare attenti
su come si organizzano i puntatori

265
00:13:30,030 --> 00:13:32,180
in modo da non rompere la catena.

266
00:13:32,180 --> 00:13:38,910
>> Siamo in grado di impostare 10 del precedente campo
per puntare di nuovo al vecchio coda,

267
00:13:38,910 --> 00:13:41,620
e dal '10 sarà la
nuova coda ad un certo punto

268
00:13:41,620 --> 00:13:44,459
dal momento tutti questi
catene sono collegate,

269
00:13:44,459 --> 00:13:46,250
niente sta andando a venire
dopo le 10 in questo momento.

270
00:13:46,250 --> 00:13:49,880
E così 10 del prossimo puntatore
punterà su null,

271
00:13:49,880 --> 00:13:53,580
e poi dopo faremo questo, dopo che avremo
10 collegata a ritroso alla catena,

272
00:13:53,580 --> 00:13:57,780
possiamo prendere la vecchia testa, o, scusa
me, il vecchio coda della coda.

273
00:13:57,780 --> 00:14:02,980
Il vecchio fine della coda,
13, e farlo puntare a 10.

274
00:14:02,980 --> 00:14:08,220
E ora, a questo punto, abbiamo
accodato il numero 10 in questa coda.

275
00:14:08,220 --> 00:14:14,740
Tutto quello che dobbiamo fare ora è solo spostare il
coda per puntare 10 invece che a 13.

276
00:14:14,740 --> 00:14:17,630
>> Annullamento dell'accodamento è in realtà
molto simile a popping

277
00:14:17,630 --> 00:14:21,710
da una risma
implementato come una lista collegata

278
00:14:21,710 --> 00:14:24,040
se hai visto il video pile.

279
00:14:24,040 --> 00:14:27,280
Tutto quello che dobbiamo fare è iniziare a
inizio, trovare il secondo elemento,

280
00:14:27,280 --> 00:14:30,480
liberare il primo elemento,
e quindi spostare la testa

281
00:14:30,480 --> 00:14:32,930
per puntare al secondo elemento.

282
00:14:32,930 --> 00:14:37,920
Probabilmente meglio per visualizzarlo
tanto per essere chiari al riguardo in più.

283
00:14:37,920 --> 00:14:39,230
Quindi, ecco di nuovo la nostra coda.

284
00:14:39,230 --> 00:14:42,600
12 è l'elemento più vecchio
nella nostra coda, la testa.

285
00:14:42,600 --> 00:14:46,210
10 è l'elemento più recente
nella nostra coda, la nostra coda.

286
00:14:46,210 --> 00:14:49,310
>> E così quando vogliamo
per annullare l'accodamento di un elemento,

287
00:14:49,310 --> 00:14:52,202
vogliamo rimuovere l'elemento più antico.

288
00:14:52,202 --> 00:14:52,910
Allora cosa facciamo?

289
00:14:52,910 --> 00:14:55,243
Beh, abbiamo fissato un puntatore attraversamento
che inizia in testa,

290
00:14:55,243 --> 00:14:57,840
e si passa in modo che
punti al secondo elemento

291
00:14:57,840 --> 00:15:02,290
di questo queue-- qualcosa dicendo trav
uguale trav freccia successiva, per esempio,

292
00:15:02,290 --> 00:15:07,170
si muoverebbe trav lì per puntare a
15, il quale, dopo si dequeue 12,

293
00:15:07,170 --> 00:15:13,030
o dopo togliamo 12, sarà
diventare l'elemento quindi più antica.

294
00:15:13,030 --> 00:15:16,360
>> Ora abbiamo una presa sulla prima
elemento via la testa puntatore

295
00:15:16,360 --> 00:15:19,440
e il secondo elemento
tramite il puntatore trav.

296
00:15:19,440 --> 00:15:25,170
Possiamo testa ora libero, e allora possiamo
dire nulla viene prima 15 più.

297
00:15:25,170 --> 00:15:29,990
Così possiamo cambiare 15 del precedente
puntatore per puntare a null,

298
00:15:29,990 --> 00:15:31,874
e abbiamo appena spostiamo la testa sopra.

299
00:15:31,874 --> 00:15:32,540
E ce ne andiamo.

300
00:15:32,540 --> 00:15:35,840
Ora abbiamo con successo
rimosse dalla coda 12, e ora siamo

301
00:15:35,840 --> 00:15:39,180
avere un'altra coda di 4 elementi.

302
00:15:39,180 --> 00:15:41,700
Questo è praticamente tutto
c'è da code,

303
00:15:41,700 --> 00:15:45,810
entrambi matrice-based e lista concatenata based.

304
00:15:45,810 --> 00:15:46,860
Sono Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Questo è CS 50.

306
00:15:49,100 --> 00:15:50,763