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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Então, se você tem
assisti o vídeo na pilha,

3
00:00:07,370 --> 00:00:09,870
esta é provavelmente vai sentir
como um pouco de deja vu.

4
00:00:09,870 --> 00:00:13,850
Vai um conceito muito semelhante,
apenas com uma leve torção nele.

5
00:00:13,850 --> 00:00:15,530
Vamos falar agora sobre filas.

6
00:00:15,530 --> 00:00:19,350
Assim, uma fila, semelhante a uma pilha,
é um outro tipo de estrutura de dados

7
00:00:19,350 --> 00:00:22,412
que podemos usar para manter
dados em uma forma organizada.

8
00:00:22,412 --> 00:00:24,120
Semelhante a uma pilha,
ele pode ser implementado

9
00:00:24,120 --> 00:00:27,000
como uma matriz ou uma lista vinculada.

10
00:00:27,000 --> 00:00:30,320
Ao contrário de uma pilha, as regras
que usamos para determinar

11
00:00:30,320 --> 00:00:34,210
Quando as coisas ficam adicionados e removidos
uma fila são um pouco diferentes.

12
00:00:34,210 --> 00:00:36,590
>> Ao contrário de uma pilha, que
é uma estrutura LIFO,

13
00:00:36,590 --> 00:00:45,610
último a entrar, primeiro a sair, uma fila é uma FIFO
estrutura, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Agora filas, você provavelmente
tem uma analogia com filas.

15
00:00:49,320 --> 00:00:52,820
Se você já foi em linha no
um parque de diversões ou em um banco,

16
00:00:52,820 --> 00:00:56,430
há uma espécie de justiça
estrutura de execução.

17
00:00:56,430 --> 00:00:59,160
A primeira pessoa na fila do
o banco é a primeira pessoa

18
00:00:59,160 --> 00:01:00,760
quem consegue falar com o caixa.

19
00:01:00,760 --> 00:01:03,522
>> Seria uma espécie de corrida
para a parte inferior se a única maneira

20
00:01:03,522 --> 00:01:06,730
você tem que falar com o caixa do
banco era para ser a última pessoa na linha.

21
00:01:06,730 --> 00:01:09,146
Todo mundo sempre quer
para ser a última pessoa na linha,

22
00:01:09,146 --> 00:01:12,580
ea pessoa que estava lá primeiro
que tem sido esperando por um tempo,

23
00:01:12,580 --> 00:01:14,715
poderia estar lá por horas,
e horas e horas

24
00:01:14,715 --> 00:01:17,590
antes que eles tenham a chance de realmente
retirar todo o dinheiro no banco.

25
00:01:17,590 --> 00:01:22,510
E assim as filas são uma espécie de
equidade implementação estrutura.

26
00:01:22,510 --> 00:01:25,780
Mas isso não significa, necessariamente,
que pilhas são uma coisa ruim, apenas

27
00:01:25,780 --> 00:01:28,160
que as filas são outra forma de fazê-lo.

28
00:01:28,160 --> 00:01:32,420
Então, novamente uma fila é o primeiro a entrar, primeiro
fora, contra uma pilha que último a entrar,

29
00:01:32,420 --> 00:01:34,440
primeiro a sair.

30
00:01:34,440 --> 00:01:36,190
Semelhante a uma pilha,
temos duas operações

31
00:01:36,190 --> 00:01:38,470
que podemos realizar em filas.

32
00:01:38,470 --> 00:01:43,910
Os nomes são enfileiramento, que consiste em adicionar
um novo elemento para o fim da fila,

33
00:01:43,910 --> 00:01:47,330
e desenfileirar, que é
para remover o mais antigo

34
00:01:47,330 --> 00:01:49,670
elemento a partir da frente da fila.

35
00:01:49,670 --> 00:01:53,600
Então, nós estamos indo para adicionar elementos
para o fim da fila,

36
00:01:53,600 --> 00:01:57,220
e nós estamos indo para remover elementos
a partir da frente da fila.

37
00:01:57,220 --> 00:02:00,790
Mais uma vez, com a pilha, fomos acrescentando
elementos para o topo da pilha

38
00:02:00,790 --> 00:02:03,380
e remoção de elementos
a partir do topo da pilha.

39
00:02:03,380 --> 00:02:07,570
Assim, com enqueue, está adicionando ao
final, a remoção a partir da frente.

40
00:02:07,570 --> 00:02:10,639
Assim, a coisa mais antiga de lá
é sempre a próxima coisa

41
00:02:10,639 --> 00:02:13,620
para sair, se tentarmos
e retirar da fila algo.

42
00:02:13,620 --> 00:02:18,330
>> Então, novamente, com filas, nós podemos
implementações baseadas em array

43
00:02:18,330 --> 00:02:20,110
e-lista vinculada implementações baseadas.

44
00:02:20,110 --> 00:02:24,620
Vamos começar de novo com
implementações baseadas em array.

45
00:02:24,620 --> 00:02:27,070
A definição da estrutura
parece muito similar.

46
00:02:27,070 --> 00:02:30,720
Temos outro array
há de valor tipo de dados,

47
00:02:30,720 --> 00:02:32,690
para que ele possa segurar tipos de dados arbitrários.

48
00:02:32,690 --> 00:02:35,570
Nós estamos indo novamente para usar
inteiros neste exemplo.

49
00:02:35,570 --> 00:02:39,830
>> E, assim como com a nossa
implementação pilha baseada em array,

50
00:02:39,830 --> 00:02:42,340
porque nós estamos usando um
matriz, que necessariamente

51
00:02:42,340 --> 00:02:46,850
tem essa limitação que tipo C
da impõe sobre nós, o que é que nós

52
00:02:46,850 --> 00:02:51,670
não têm qualquer dinamismo na nossa
capacidade de aumentar e diminuir a matriz.

53
00:02:51,670 --> 00:02:55,710
Temos que decidir no início
o que é o número máximo de coisas

54
00:02:55,710 --> 00:02:59,300
que podemos colocar em este
fila, e, neste caso,

55
00:02:59,300 --> 00:03:02,070
capacidade seria algum libra
constante definida em nosso código.

56
00:03:02,070 --> 00:03:05,430
E para os efeitos da presente
vídeo, capacidade vai ser 10.

57
00:03:05,430 --> 00:03:07,690
>> Precisamos manter o controle de
a frente da fila

58
00:03:07,690 --> 00:03:11,160
por isso sabemos que elemento
queremos retirar da fila,

59
00:03:11,160 --> 00:03:15,070
e também precisamos de acompanhar
algo else-- o número de elementos

60
00:03:15,070 --> 00:03:16,690
que temos em nossa fila.

61
00:03:16,690 --> 00:03:19,360
Observe que não estamos mantendo o controle
do final da fila, apenas

62
00:03:19,360 --> 00:03:21,150
o tamanho da fila.

63
00:03:21,150 --> 00:03:24,310
E a razão para que venha a
tornar-se um pouco mais claro em um momento.

64
00:03:24,310 --> 00:03:26,143
Uma vez que tenhamos concluído
esta definição de tipo,

65
00:03:26,143 --> 00:03:29,080
temos um novo tipo de dados
chamada de fila, que nós podemos agora

66
00:03:29,080 --> 00:03:30,630
declarar variáveis ​​desse tipo de dados.

67
00:03:30,630 --> 00:03:35,350
E um tanto confusa, eu decidi
para chamar essa fila q, a letra

68
00:03:35,350 --> 00:03:38,090
Q em vez do tipo de dados q.

69
00:03:38,090 --> 00:03:39,600
>> Então aqui é a nossa fila.

70
00:03:39,600 --> 00:03:40,700
É uma estrutura.

71
00:03:40,700 --> 00:03:45,730
Ele contém três membros ou três
campos, uma matriz de tamanho capacidade.

72
00:03:45,730 --> 00:03:47,340
Neste caso, a capacidade é de 10.

73
00:03:47,340 --> 00:03:49,580
E essa matriz é
vai realizar inteiros.

74
00:03:49,580 --> 00:03:55,240
Em verde é a frente da nossa fila, o
próximo elemento a ser removido, e no vermelho

75
00:03:55,240 --> 00:03:58,610
será o tamanho da fila,
quantos elementos estão atualmente

76
00:03:58,610 --> 00:04:01,190
existente na fila.

77
00:04:01,190 --> 00:04:05,300
Então, se nós dizemos iguais q.front
0, eo tamanho é igual a q.size 0--

78
00:04:05,300 --> 00:04:07,120
estamos colocando 0s em esses campos.

79
00:04:07,120 --> 00:04:11,070
E, neste ponto, estamos muito bonito
pronto para começar a trabalhar com a nossa fila.

80
00:04:11,070 --> 00:04:14,140
>> Assim, a primeira operação que pudermos
executar é algo para enfileirar,

81
00:04:14,140 --> 00:04:16,860
para adicionar um novo elemento
o fim da fila.

82
00:04:16,860 --> 00:04:19,089
Bem, o que nós precisamos
fazer no caso geral?

83
00:04:19,089 --> 00:04:23,690
Bem esta função necessidades enfileirar
para aceitar um ponteiro para a fila.

84
00:04:23,690 --> 00:04:26,370
Mais uma vez, se tinha declarado
nossa fila globalmente,

85
00:04:26,370 --> 00:04:29,490
nós não precisamos fazer isso
necessariamente, mas, em geral, nós

86
00:04:29,490 --> 00:04:32,330
precisa aceitar ponteiros
para estruturas de dados

87
00:04:32,330 --> 00:04:35,040
como este, porque, caso contrário,
nós estamos passando por value-- estamos

88
00:04:35,040 --> 00:04:38,140
passando em cópias da fila,
e por isso não estamos realmente mudando

89
00:04:38,140 --> 00:04:41,050
a fila que temos a intenção de mudar.

90
00:04:41,050 --> 00:04:44,860
>> A outra coisa que precisa fazer é aceitar
um elemento de dados do tipo apropriado.

91
00:04:44,860 --> 00:04:46,818
Mais uma vez, neste caso, é
vai ser inteiros,

92
00:04:46,818 --> 00:04:49,330
mas você pode arbitrariamente
declarar o tipo de dados como valor

93
00:04:49,330 --> 00:04:51,160
e utilizar esta forma mais geral.

94
00:04:51,160 --> 00:04:56,030
Esse é o elemento que queremos para enfileirar,
queremos adicionar ao final da fila.

95
00:04:56,030 --> 00:04:58,573
Então nós realmente querem
colocar os dados na fila.

96
00:04:58,573 --> 00:05:01,490
Neste caso, colocando-o no
local correto da nossa matriz,

97
00:05:01,490 --> 00:05:05,040
e então nós queremos mudar o tamanho
da fila, quantos elementos que

98
00:05:05,040 --> 00:05:07,050
tem atualmente.

99
00:05:07,050 --> 00:05:07,990
>> Então, vamos começar.

100
00:05:07,990 --> 00:05:10,890
Aqui está, mais uma vez, que em geral
declaração de função forma

101
00:05:10,890 --> 00:05:13,980
para o que enqueue pode parecer.

102
00:05:13,980 --> 00:05:14,910
E aqui vamos nós.

103
00:05:14,910 --> 00:05:18,335
Vamos enfileirar o número
28 para dentro da fila.

104
00:05:18,335 --> 00:05:19,460
Então, o que vamos fazer?

105
00:05:19,460 --> 00:05:23,390
Bem, a frente da nossa fila é
a 0, eo tamanho da nossa fila

106
00:05:23,390 --> 00:05:29,680
é a 0, e por isso, provavelmente quer colocar
o número 28 na matriz número elemento

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

108
00:05:31,124 --> 00:05:32,540
Então, nós temos agora que colocou lá.

109
00:05:32,540 --> 00:05:34,820
Então agora o que precisamos mudar?

110
00:05:34,820 --> 00:05:37,090
Nós não querem mudar
a frente da fila,

111
00:05:37,090 --> 00:05:40,850
porque queremos saber o elemento
que poderá ser necessário para retirar da fila mais tarde.

112
00:05:40,850 --> 00:05:44,020
Assim, a razão pela qual temos frente há
é uma espécie de um indicador do que é

113
00:05:44,020 --> 00:05:46,439
a coisa mais antiga do array.

114
00:05:46,439 --> 00:05:49,730
Bem, a coisa mais antiga do array-- em
verdade, a única coisa na matriz direita

115
00:05:49,730 --> 00:05:53,540
agora-- é 28, que é
a matriz localização 0.

116
00:05:53,540 --> 00:05:56,160
Então, nós não queremos
alterar esse número verde,

117
00:05:56,160 --> 00:05:57,910
porque esse é o elemento mais antigo.

118
00:05:57,910 --> 00:06:00,510
Em vez disso, queremos mudar o tamanho.

119
00:06:00,510 --> 00:06:04,110
Portanto, neste caso, vamos
incrementar tamanho 1.

120
00:06:04,110 --> 00:06:08,430
>> Agora, um tipo geral da ideia de onde o
próximo elemento está indo para ir em uma fila

121
00:06:08,430 --> 00:06:12,310
é para adicionar esses dois números
juntos, frente e tamanho,

122
00:06:12,310 --> 00:06:16,390
e que vai lhe dizer onde o próximo
elemento na fila está a ir.

123
00:06:16,390 --> 00:06:18,130
Então agora vamos enfileirar outro número.

124
00:06:18,130 --> 00:06:20,250
Vamos enfileirar 33.

125
00:06:20,250 --> 00:06:24,480
Então 33 vai entrar em
matriz localização 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Portanto, neste caso, ele vai
para entrar em um local da matriz,

127
00:06:26,840 --> 00:06:29,500
e agora o tamanho da nossa fila é 2.

128
00:06:29,500 --> 00:06:31,840
>> Mais uma vez, nós não estamos mudando
a frente da nossa fila,

129
00:06:31,840 --> 00:06:34,730
porque 28 é ainda o
mais antigo elemento, e nós

130
00:06:34,730 --> 00:06:38,220
quer a-- quando finalmente chegar
para dequeuing, remoção de elementos

131
00:06:38,220 --> 00:06:43,300
a partir desta fila, queremos saber
onde o elemento mais antigo é.

132
00:06:43,300 --> 00:06:48,620
E assim temos sempre que manter
algum indicador de onde é.

133
00:06:48,620 --> 00:06:50,410
Então é isso que a 0 está lá para.

134
00:06:50,410 --> 00:06:52,910
Isso é o que está lá para frente.

135
00:06:52,910 --> 00:06:55,022
>> Vamos em enqueue um elemento a mais, 19.

136
00:06:55,022 --> 00:06:56,980
Tenho certeza que você pode adivinhar
onde 19 está a ir.

137
00:06:56,980 --> 00:06:59,860
Vai entrar em
matriz número de posição 2.

138
00:06:59,860 --> 00:07:01,570
Isso é 0 + 2.

139
00:07:01,570 --> 00:07:03,199
E agora o tamanho da nossa fila é 3.

140
00:07:03,199 --> 00:07:04,240
Temos 3 elementos nele.

141
00:07:04,240 --> 00:07:08,490
Então, se fôssemos, e nós não vamos
para a direita agora, enfileirar outro elemento,

142
00:07:08,490 --> 00:07:11,370
ele iria entrar em local da matriz
número 3, eo tamanho da nossa fila

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

144
00:07:13,160 --> 00:07:15,279
Então, nós temos enfileirado vários elementos agora.

145
00:07:15,279 --> 00:07:16,570
Agora vamos começar a removê-los.

146
00:07:16,570 --> 00:07:19,450
Vamos desenfileirar-los a partir da fila.

147
00:07:19,450 --> 00:07:23,340
>> Assim, semelhante ao pop, que é uma espécie
do análogo deste para pilhas,

148
00:07:23,340 --> 00:07:26,180
dequeue precisa aceitar uma
ponteiro para o queue-- novamente,

149
00:07:26,180 --> 00:07:28,140
a menos que seja declarado globalmente.

150
00:07:28,140 --> 00:07:31,610
Agora queremos alterar o local
de a frente da fila.

151
00:07:31,610 --> 00:07:35,050
Este é o lugar onde tipo de vem
em jogo, essa variável frente,

152
00:07:35,050 --> 00:07:37,310
porque uma vez que remover
um elemento, queremos

153
00:07:37,310 --> 00:07:40,720
para movê-lo para o próximo elemento mais antigo.

154
00:07:40,720 --> 00:07:44,180
>> Então nós queremos diminuir
o tamanho da fila,

155
00:07:44,180 --> 00:07:47,130
e então nós queremos devolver o valor
que foi removido da fila.

156
00:07:47,130 --> 00:07:48,921
Mais uma vez, nós não queremos apenas descartá-lo.

157
00:07:48,921 --> 00:07:51,170
Nós provavelmente está extraindo
lo a partir do queue-- estamos

158
00:07:51,170 --> 00:07:54,170
dequeuing-lo porque nos preocupamos com isso.

159
00:07:54,170 --> 00:08:01,080
Então, nós queremos esta função para retornar
um elemento de dados de valor tipo.

160
00:08:01,080 --> 00:08:04,360
Mais uma vez, neste caso, é o valor inteiro.

161
00:08:04,360 --> 00:08:05,670
>> Então agora vamos retirar da fila algo.

162
00:08:05,670 --> 00:08:09,310
Vamos remover um elemento da fila.

163
00:08:09,310 --> 00:08:15,970
Se dissermos int x é igual a & q, comercial q--
mais uma vez que é um ponteiro para este dados q

164
00:08:15,970 --> 00:08:20,177
structure-- o elemento
vai ser será?

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

166
00:08:23,840 --> 00:08:29,480
Neste caso, uma vez que é um primeiro
in, first out estrutura de dados, FIFO,

167
00:08:29,480 --> 00:08:33,690
a primeira coisa que dedicou a este
fila foi de 28, e portanto, neste caso,

168
00:08:33,690 --> 00:08:37,245
nós estamos indo tomar 28 de
a fila, não 19, que é o que

169
00:08:37,245 --> 00:08:38,870
teríamos feito se isso era uma pilha.

170
00:08:38,870 --> 00:08:42,220
Nós vamos levar 28 para fora da fila.

171
00:08:42,220 --> 00:08:44,960
>> À semelhança do que fizemos com
uma pilha, não estamos, na verdade,

172
00:08:44,960 --> 00:08:47,345
vai eliminar 28
a partir da própria fila,

173
00:08:47,345 --> 00:08:49,470
nós apenas estamos indo para tipo
de fingir que não está lá.

174
00:08:49,470 --> 00:08:51,678
Então ele vai ficar lá
na memória, mas nós somos apenas

175
00:08:51,678 --> 00:08:57,820
vai tipo de ignorá-lo, movendo
os outros dois campos de dados Q nosso

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

177
00:08:58,830 --> 00:09:00,230
Nós vamos mudar a parte dianteira.

178
00:09:00,230 --> 00:09:04,290
Q.front vai agora
ser 1, porque essa é agora

179
00:09:04,290 --> 00:09:07,740
o elemento mais antigo que temos em nosso
fila, porque já removeu 28,

180
00:09:07,740 --> 00:09:10,460
que foi o ex-elemento mais antigo.

181
00:09:10,460 --> 00:09:13,540
>> E agora, nós queremos mudar
o tamanho da fila

182
00:09:13,540 --> 00:09:15,780
de dois elementos em vez de três.

183
00:09:15,780 --> 00:09:20,450
Agora lembre-se, eu disse mais cedo, quando nós
deseja adicionar elementos para a fila,

184
00:09:20,450 --> 00:09:26,000
vamos colocá-la em um local matriz
que é a soma da frente e tamanho.

185
00:09:26,000 --> 00:09:29,050
Portanto, neste caso, ainda estamos colocando
ele, o elemento seguinte na fila,

186
00:09:29,050 --> 00:09:33,360
no local da matriz 3, e
vamos ver isso em um segundo.

187
00:09:33,360 --> 00:09:35,730
>> Então, nós temos agora a nossa dequeued
primeiro elemento da fila.

188
00:09:35,730 --> 00:09:36,480
Vamos fazer de novo.

189
00:09:36,480 --> 00:09:38,696
Vamos remover outra
elemento da fila.

190
00:09:38,696 --> 00:09:42,400
No caso, a corrente mais antigo
elemento é um local da matriz.

191
00:09:42,400 --> 00:09:44,220
Isso é o que nos diz q.front.

192
00:09:44,220 --> 00:09:46,980
Essa caixa verde nos diz que
que é o elemento mais antigo.

193
00:09:46,980 --> 00:09:49,310
E assim, se tornará x 33.

194
00:09:49,310 --> 00:09:52,130
Vamos apenas uma espécie de esquecer
33 que existe na matriz,

195
00:09:52,130 --> 00:09:55,100
e vamos dizer que agora, o
novo elemento mais antigo na fila

196
00:09:55,100 --> 00:09:58,900
está no local da matriz 2, e do tamanho
da fila, o número de elementos

197
00:09:58,900 --> 00:10:02,152
temos na fila, é 1.

198
00:10:02,152 --> 00:10:05,110
Agora vamos enfileirar alguma coisa, e eu
tipo de deu este fora um segundo atrás,

199
00:10:05,110 --> 00:10:10,340
mas se queremos colocar 40 no
fila, onde está 40 indo para ir?

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

201
00:10:12,880 --> 00:10:17,730
Bem, nós estivemos colocando-
em q.front mais fila de tamanho,

202
00:10:17,730 --> 00:10:20,850
e por isso faz sentido para
realmente colocar 40 aqui.

203
00:10:20,850 --> 00:10:22,840
Agora note que pelo
algum momento, nós vamos

204
00:10:22,840 --> 00:10:27,980
para chegar ao fim de
nossa matriz dentro de q,

205
00:10:27,980 --> 00:10:32,010
mas que desapareceu 28 e 33--
eles são realmente, tecnicamente

206
00:10:32,010 --> 00:10:33,300
espaços abertos, certo?

207
00:10:33,300 --> 00:10:36,040
E assim, podemos eventually--
essa regra de adicionar

208
00:10:36,040 --> 00:10:40,390
aqueles dois together-- podemos, eventualmente,
precisa modificação pelo tamanho da capacidade

209
00:10:40,390 --> 00:10:41,410
por isso, pode envolver em torno.

210
00:10:41,410 --> 00:10:43,620
>> Então, se chegarmos ao elemento
número 10, se estamos

211
00:10:43,620 --> 00:10:48,790
substituindo-o no elemento número 10, estaríamos
realmente colocá-lo em ordem de localização 0.

212
00:10:48,790 --> 00:10:50,997
E se nós íamos
matriz localização-- me desculpar,

213
00:10:50,997 --> 00:10:53,080
se nós adicionamos-los juntos,
e chegamos ao número

214
00:10:53,080 --> 00:10:56,330
11 estaria onde teríamos que colocar
ele, que não existe no presente array--

215
00:10:56,330 --> 00:10:58,200
ele estaria indo para fora dos limites.

216
00:10:58,200 --> 00:11:03,367
Poderíamos mod em 10 e colocá-
em que local da matriz 1.

217
00:11:03,367 --> 00:11:04,450
Então é assim que as filas de trabalho.

218
00:11:04,450 --> 00:11:08,540
Eles estão sempre indo para ir a partir da esquerda
para a direita e, possivelmente, envolver em torno.

219
00:11:08,540 --> 00:11:11,280
E você sabe que eles são
se em tamanho grande, que a caixa vermelha,

220
00:11:11,280 --> 00:11:13,710
torna-se igual à capacidade.

221
00:11:13,710 --> 00:11:16,720
E assim, depois nós adicionamos 40 para o
fila, bem o que precisamos fazer?

222
00:11:16,720 --> 00:11:19,890
Bem, o elemento mais antigo
na fila é ainda 19,

223
00:11:19,890 --> 00:11:21,990
por isso não quer mudar
a frente da fila,

224
00:11:21,990 --> 00:11:23,820
mas agora temos dois
elementos na fila,

225
00:11:23,820 --> 00:11:28,710
e por isso queremos aumentar
nosso tamanho 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Isso é muito bonito isso com
trabalhar com filas baseadas em matrizes,

227
00:11:31,820 --> 00:11:33,630
e semelhante para empilhar,
Há também uma maneira

228
00:11:33,630 --> 00:11:36,450
para implementar uma fila como uma lista ligada.

229
00:11:36,450 --> 00:11:40,150
Agora, se este tipo de estrutura de dados
parece familiar para você, é.

230
00:11:40,150 --> 00:11:43,780
Não é uma lista vinculada isoladamente,
é uma lista duplamente ligada.

231
00:11:43,780 --> 00:11:46,790
E agora, como um aparte, é
realmente possível implementar

232
00:11:46,790 --> 00:11:50,160
uma fila como uma lista vinculada isoladamente, mas
Eu acho que em termos de visualização,

233
00:11:50,160 --> 00:11:53,350
ele realmente pode ajudar a visualizar
isto como uma lista duplamente ligada.

234
00:11:53,350 --> 00:11:56,850
Mas é definitivamente possível
fazer isso como uma lista vinculada isoladamente.

235
00:11:56,850 --> 00:12:00,110
>> Então vamos dar uma olhada
o que isso pode parecer.

236
00:12:00,110 --> 00:12:02,750
Se queremos enquue--
agora, estamos novamente

237
00:12:02,750 --> 00:12:05,360
a mudança para uma lista ligada
modelo baseado aqui.

238
00:12:05,360 --> 00:12:08,420
Se queremos enfileirar, queremos
para adicionar um novo elemento, bem

239
00:12:08,420 --> 00:12:09,730
o que precisamos fazer?

240
00:12:09,730 --> 00:12:12,770
Bem, em primeiro lugar, porque
estamos adicionando ao fim

241
00:12:12,770 --> 00:12:15,520
e a remoção a partir da
começando, nós provavelmente

242
00:12:15,520 --> 00:12:20,050
querem manter ponteiros para ambos os
cabeça ea cauda da lista ligada?

243
00:12:20,050 --> 00:12:22,660
Cauda sendo outro termo para
o fim da lista ligada,

244
00:12:22,660 --> 00:12:24,496
o último elemento da lista ligada.

245
00:12:24,496 --> 00:12:26,620
E estes, provavelmente,
mais uma vez, ser benéfico para nós

246
00:12:26,620 --> 00:12:28,477
se eles são variáveis ​​globais.

247
00:12:28,477 --> 00:12:31,060
Mas agora, se queremos adicionar um novo
elemento que é que temos de fazer?

248
00:12:31,060 --> 00:12:35,262
O que nós apenas [? Malak?] ou dinamicamente
alocar o nosso novo nó para nós mesmos.

249
00:12:35,262 --> 00:12:38,220
E então, assim como quando nós adicionamos qualquer
elemento de uma lista duplamente ligada nós,

250
00:12:38,220 --> 00:12:40,410
só tem que classificar de--
esses três últimos passos aqui

251
00:12:40,410 --> 00:12:43,330
são apenas tudo sobre como mover o
ponteiros na maneira correta

252
00:12:43,330 --> 00:12:46,710
de modo que o elemento é adicionado ao
a cadeia sem quebrar a cadeia

253
00:12:46,710 --> 00:12:49,580
ou fazer algum tipo de erro
ou ter algum tipo de acidente

254
00:12:49,580 --> 00:12:54,505
acontecer pelo qual acidentalmente
órfãos alguns elementos da nossa fila.

255
00:12:54,505 --> 00:12:55,880
Aqui está o que isso pode parecer.

256
00:12:55,880 --> 00:13:00,980
Queremos adicionar o elemento
10 para a extremidade desta fila.

257
00:13:00,980 --> 00:13:03,380
Assim, o elemento mais antigo aqui
é representado pela cabeça.

258
00:13:03,380 --> 00:13:06,800
Essa é a primeira coisa que colocamos
para esta fila hipotético aqui.

259
00:13:06,800 --> 00:13:10,430
E cauda, ​​13, é o mais
recentemente adicionou elemento.

260
00:13:10,430 --> 00:13:17,030
E por isso, se queremos enfileirar 10 em
esta fila, queremos colocá-lo depois de 13.

261
00:13:17,030 --> 00:13:19,860
E assim vamos dinamicamente
atribuir espaço para um novo nó

262
00:13:19,860 --> 00:13:23,280
e verificar se há nula para se certificar
não temos uma falha na memória.

263
00:13:23,280 --> 00:13:27,040
Então nós vamos
10 colocar em que nó,

264
00:13:27,040 --> 00:13:30,030
e agora nós precisamos ter cuidado
sobre como podemos organizar ponteiros

265
00:13:30,030 --> 00:13:32,180
assim que nós não quebrar a cadeia.

266
00:13:32,180 --> 00:13:38,910
>> Podemos definir 10 do campo anterior
para apontar de volta ao velho cauda,

267
00:13:38,910 --> 00:13:41,620
e uma vez que será a '10
nova cauda em algum momento

268
00:13:41,620 --> 00:13:44,459
no momento em que todos esses
cadeias estão conectados,

269
00:13:44,459 --> 00:13:46,250
nada vai vir
após 10 agora.

270
00:13:46,250 --> 00:13:49,880
E assim 10 do próximo ponteiro
irá apontar para null,

271
00:13:49,880 --> 00:13:53,580
e, em seguida, depois de se fazer isso, depois de termos
ligado 10 para trás para a corrente,

272
00:13:53,580 --> 00:13:57,780
podemos tomar a velha cabeça, ou, desculpa
me, o velho cauda da fila.

273
00:13:57,780 --> 00:14:02,980
O velho final da fila,
13, e fazê-lo apontar a 10.

274
00:14:02,980 --> 00:14:08,220
E agora, neste momento, temos
enfileirado o número 10 para essa fila.

275
00:14:08,220 --> 00:14:14,740
Tudo o que precisamos fazer agora é apenas mover o
cauda para apontar para, em vez de 10 a 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing é, na verdade,
muito semelhantes para avançar

277
00:14:17,630 --> 00:14:21,710
a partir de uma pilha que está
implementada como uma lista ligada

278
00:14:21,710 --> 00:14:24,040
se você já viu o vídeo stacks.

279
00:14:24,040 --> 00:14:27,280
Tudo o que precisamos fazer é começar no
começando, encontrar o segundo elemento,

280
00:14:27,280 --> 00:14:30,480
libertar o primeiro elemento,
e depois mover a cabeça

281
00:14:30,480 --> 00:14:32,930
para apontar para o segundo elemento.

282
00:14:32,930 --> 00:14:37,920
Provavelmente melhor para visualizá-lo
apenas para ser mais claro sobre isso.

283
00:14:37,920 --> 00:14:39,230
Então aqui está a nossa fila novamente.

284
00:14:39,230 --> 00:14:42,600
12 é o elemento mais antigo
em nossa fila, a cabeça.

285
00:14:42,600 --> 00:14:46,210
10 é o elemento mais novo
em nossa fila, o nosso rabo.

286
00:14:46,210 --> 00:14:49,310
>> E assim, quando nós queremos
para retirar da fila um elemento,

287
00:14:49,310 --> 00:14:52,202
queremos remover o elemento mais antigo.

288
00:14:52,202 --> 00:14:52,910
Então, o que fazemos?

289
00:14:52,910 --> 00:14:55,243
Bem, nós definir um ponteiro de passagem
que começa na cabeça,

290
00:14:55,243 --> 00:14:57,840
e movê-lo para que ele
aponta para o segundo elemento

291
00:14:57,840 --> 00:15:02,290
desta queue-- algo por dizer trav
é igual a trav seta próxima, por exemplo,

292
00:15:02,290 --> 00:15:07,170
moveria trav para apontar para lá
15, que, depois de nos retirar da fila 12,

293
00:15:07,170 --> 00:15:13,030
ou depois de remover 12, vontade
tornar-se o elemento mais velho então.

294
00:15:13,030 --> 00:15:16,360
>> Agora temos um poder sobre o primeiro
elemento através da cabeça do ponteiro

295
00:15:16,360 --> 00:15:19,440
e o segundo elemento
através do trav ponteiro.

296
00:15:19,440 --> 00:15:25,170
Podemos cabeça agora está livre, e então nós podemos
dizer nada vem antes de 15 de anymore.

297
00:15:25,170 --> 00:15:29,990
Assim, podemos mudar 15 do anterior
ponteiro para apontar para null,

298
00:15:29,990 --> 00:15:31,874
e nós apenas mover a cabeça sobre.

299
00:15:31,874 --> 00:15:32,540
E lá vamos nós.

300
00:15:32,540 --> 00:15:35,840
Agora nós temos com sucesso
dequeued 12, e agora nós

301
00:15:35,840 --> 00:15:39,180
tem outra fila de 4 elementos.

302
00:15:39,180 --> 00:15:41,700
Isso é muito bonito tudo
existe a filas,

303
00:15:41,700 --> 00:15:45,810
tanto baseada em array e-lista ligada baseado.

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

305
00:15:46,860 --> 00:15:49,100
Este é CS 50.

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