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

2
00:00:05,204 --> 00:00:07,370
Даг Lloyd: Так што, калі ў Вас ёсць
глядзеў відэа на стэку,

3
00:00:07,370 --> 00:00:09,870
гэта, верагодна, будзе адчуваць сябе
як трохі дэжа вю.

4
00:00:09,870 --> 00:00:13,850
Гэта будзе вельмі падобнай канцэпцыі,
толькі з невялікай паварот на ім.

5
00:00:13,850 --> 00:00:15,530
Мы будзем казаць цяпер аб чэргах.

6
00:00:15,530 --> 00:00:19,350
Так чаргу, падобны на стос,
іншы выгляд структуры дадзеных

7
00:00:19,350 --> 00:00:22,412
што мы можам выкарыстоўваць, каб захаваць
дадзеныя ў арганізаваным парадку.

8
00:00:22,412 --> 00:00:24,120
Падобна стэку,
ён можа быць рэалізаваны

9
00:00:24,120 --> 00:00:27,000
ў выглядзе масіва або звязанага спісу.

10
00:00:27,000 --> 00:00:30,320
У адрозненне ад стэка, правілы
што мы выкарыстоўваем, каб вызначыць,

11
00:00:30,320 --> 00:00:34,210
калі рэчы дадаў атрымаць і выдаляецца з
чаргу з'яўляюцца трохі адрозніваецца.

12
00:00:34,210 --> 00:00:36,590
>> У адрозненне ад стэка, які
гэта структура ЛИФО,

13
00:00:36,590 --> 00:00:45,610
апошні прыйшоў, першы, чэргі FIFO з'яўляецца
Структура, FIFO, першы ў першы выйшаў.

14
00:00:45,610 --> 00:00:49,320
Цяпер у чаргу, вы, верагодна,
ёсць аналогіі з чэргамі.

15
00:00:49,320 --> 00:00:52,820
Калі вы калі-небудзь у чарзе ў
парк забаў або ў банку,

16
00:00:52,820 --> 00:00:56,430
ёсць свайго роду справядлівасці
рэалізацыі структуры.

17
00:00:56,430 --> 00:00:59,160
Першы чалавек у чарзе ў
банк з'яўляецца першым чалавекам,

18
00:00:59,160 --> 00:01:00,760
хто атрымлівае, каб пагаварыць з касірам.

19
00:01:00,760 --> 00:01:03,522
>> Гэта будзе свайго роду гонкі
на дно, калі адзіны спосаб

20
00:01:03,522 --> 00:01:06,730
Вы павінны гаварыць з касірам на
Банк павінен быў быць апошні чалавек у лініі.

21
00:01:06,730 --> 00:01:09,146
Усе заўсёды хочуць
каб быць апошнім чалавекам у лініі,

22
00:01:09,146 --> 00:01:12,580
і чалавек, які быў там першым
хто чакаў некаторы час,

23
00:01:12,580 --> 00:01:14,715
можа быць там на працягу некалькіх гадзін,
і гадзіны, і гадзіны

24
00:01:14,715 --> 00:01:17,590
перш чым яны маюць шанец на самой справе
зняць грошы ў банку.

25
00:01:17,590 --> 00:01:22,510
І так Чэргі з роду
справядлівасць рэалізацыі структуры.

26
00:01:22,510 --> 00:01:25,780
Але гэта не абавязкова азначае,
што стэкі дрэнна, проста

27
00:01:25,780 --> 00:01:28,160
што чэргі яшчэ адзін спосаб зрабіць гэта.

28
00:01:28,160 --> 00:01:32,420
Так зноў чэргі першым прыйшоў, першым
з, у параўнанні з крамай, які будзе доўжыцца на,

29
00:01:32,420 --> 00:01:34,440
першым выйшаў.

30
00:01:34,440 --> 00:01:36,190
Падобна стэку,
у нас ёсць дзве аперацыі

31
00:01:36,190 --> 00:01:38,470
што мы можам выканаць у чарзе.

32
00:01:38,470 --> 00:01:43,910
Імёны паставіць у чаргу, якая з'яўляецца даданне
новы элемент у канец чаргі,

33
00:01:43,910 --> 00:01:47,330
і выдалення з чаргі, якая
выдаліць найстарэйшы

34
00:01:47,330 --> 00:01:49,670
Элемент з пярэдняй чарзе.

35
00:01:49,670 --> 00:01:53,600
Такім чынам, мы збіраемся, каб дадаць элементы
на канец чаргі,

36
00:01:53,600 --> 00:01:57,220
і мы збіраемся, каб выдаліць элементы
ад пярэдняй часткі чарзе.

37
00:01:57,220 --> 00:02:00,790
Зноў жа, са стэкам, мы дадавалі
Элементы да вяршыні стэка

38
00:02:00,790 --> 00:02:03,380
і выдаленне элементаў
ад верхняй часткі стэка.

39
00:02:03,380 --> 00:02:07,570
Так што з Enqueue, гэта даданне да
канец, выдаляючы з фронту.

40
00:02:07,570 --> 00:02:10,639
Так найстарэйшых рэчы ў там
заўсёды побач, што

41
00:02:10,639 --> 00:02:13,620
каб выйсці, калі мы паспрабуем
і з чаргі нешта.

42
00:02:13,620 --> 00:02:18,330
>> Такім чынам, яшчэ раз, з чэргамі, мы можам
рэалізацыі масіваў на аснове

43
00:02:18,330 --> 00:02:20,110
і звязаныя-спіс, заснаваны рэалізацый.

44
00:02:20,110 --> 00:02:24,620
Мы пачнем зноў
масіў на аснове рэалізацыі.

45
00:02:24,620 --> 00:02:27,070
Вызначэнне структуры
выглядае вельмі падобна.

46
00:02:27,070 --> 00:02:30,720
У нас ёсць яшчэ адзін масіў
ёсць з значэння тыпу дадзеных,

47
00:02:30,720 --> 00:02:32,690
таму ён можа трымаць адвольныя тыпы дадзеных.

48
00:02:32,690 --> 00:02:35,570
Мы зноў збіраемся выкарыстоўваць
цэлыя лікі ў гэтым прыкладзе.

49
00:02:35,570 --> 00:02:39,830
>> І гэтак жа, як з нашым
Рэалізацыя стэка на базе масіва,

50
00:02:39,830 --> 00:02:42,340
таму што мы выкарыстоўваючы
Масіў, мы абавязкова

51
00:02:42,340 --> 00:02:46,850
ёсць гэта абмежаванне, што З роду
з навязвае нам, што мы

52
00:02:46,850 --> 00:02:51,670
не маюць ніякага дынамізм ў нашых
здольнасць расці і змяншацца масіў.

53
00:02:51,670 --> 00:02:55,710
Мы павінны вырашыць, у пачатку
якое максімальную колькасць рэчаў

54
00:02:55,710 --> 00:02:59,300
што мы можам паставіць у гэта
Чаргу, і ў гэтым выпадку,

55
00:02:59,300 --> 00:03:02,070
Аб'ём б некаторыя фунт
вызначаецца канстанта ў нашым кодзе.

56
00:03:02,070 --> 00:03:05,430
А для мэтаў гэтага
відэа, магутнасць будзе 10.

57
00:03:05,430 --> 00:03:07,690
>> Мы павінны сачыць за
пярэдняя частка чарзе

58
00:03:07,690 --> 00:03:11,160
так што мы ведаем, які элемент
мы хочам, каб з чаргі,

59
00:03:11,160 --> 00:03:15,070
і мы таксама павінны сачыць за
Што else-- колькасць элементаў

60
00:03:15,070 --> 00:03:16,690
што мы маем у нашай чаргі.

61
00:03:16,690 --> 00:03:19,360
Звярніце ўвагу, мы не адсочваць
у канец чаргі, проста

62
00:03:19,360 --> 00:03:21,150
памер чаргі.

63
00:03:21,150 --> 00:03:24,310
І прычына для гэтага, мы спадзяемся,
стаць трохі ясней ў дадзены момант.

64
00:03:24,310 --> 00:03:26,143
Пасля таго, як мы скончылі
гэта вызначэнне тыпу,

65
00:03:26,143 --> 00:03:29,080
у нас ёсць новы тып дадзеных
называецца чарзе, якія мы цяпер можам

66
00:03:29,080 --> 00:03:30,630
аб'яўляць зменныя гэтага тыпу дадзеных.

67
00:03:30,630 --> 00:03:35,350
І некалькі цьмяна, я вырашыў
назваць гэтую Чарга Q, ліст

68
00:03:35,350 --> 00:03:38,090
в замест тыпу дадзеных в.

69
00:03:38,090 --> 00:03:39,600
>> Дык вось наш чарзе.

70
00:03:39,600 --> 00:03:40,700
Гэта структура.

71
00:03:40,700 --> 00:03:45,730
Ён змяшчае тры члена або тры
Поля, масіў памеру ёмістасці.

72
00:03:45,730 --> 00:03:47,340
У гэтым выпадку, магутнасць складае 10.

73
00:03:47,340 --> 00:03:49,580
І гэты масіў
збіраецца правесці цэлых лікаў.

74
00:03:49,580 --> 00:03:55,240
У зялёны фронт нашай чарзе,
Наступны элемент павінен быць выдалены, а ў чырвоным

75
00:03:55,240 --> 00:03:58,610
будзе памер чарзе,
колькі элементаў у цяперашні час

76
00:03:58,610 --> 00:04:01,190
існуючых у чарзе.

77
00:04:01,190 --> 00:04:05,300
Так што, калі мы гаворым q.front роўна
0, і памер q.size роўная 0--

78
00:04:05,300 --> 00:04:07,120
мы ўкладваем у 0s гэтых абласцях.

79
00:04:07,120 --> 00:04:11,070
І ў гэты момант, мы ў значнай ступені
гатовыя прыступіць да працы з нашай чаргі.

80
00:04:11,070 --> 00:04:14,140
>> Такім чынам, першая аперацыя, мы можам
выканаць, каб паставіць у чаргу нешта,

81
00:04:14,140 --> 00:04:16,860
дадаць новы элемент у
канец чаргі.

82
00:04:16,860 --> 00:04:19,089
Ну што ж, мы павінны
зрабіць у агульным выпадку?

83
00:04:19,089 --> 00:04:23,690
Ну гэтая функцыя ў чаргу патрэбы
прыняць паказальнік на нашай чаргі.

84
00:04:23,690 --> 00:04:26,370
Зноў жа, калі мы абвясцілі
наша чарга ў глабальным маштабе,

85
00:04:26,370 --> 00:04:29,490
мы не павінны былі б зрабіць гэта
абавязкова, але ў цэлым, мы

86
00:04:29,490 --> 00:04:32,330
трэба прыняць паказальнікі
да структур дадзеных

87
00:04:32,330 --> 00:04:35,040
як гэта, таму што інакш,
мы міма value-- мы

88
00:04:35,040 --> 00:04:38,140
перадаючы копіі чарзе,
і такім чынам, мы на самай справе не мяняецца

89
00:04:38,140 --> 00:04:41,050
чаргу, што мы маем намер змяніць.

90
00:04:41,050 --> 00:04:44,860
>> Іншая справа, што трэба зрабіць, гэта прыняць
элемент дадзеных адпаведнага тыпу.

91
00:04:44,860 --> 00:04:46,818
Зноў жа, у гэтым выпадку, гэта
будзе цэлыя лікі,

92
00:04:46,818 --> 00:04:49,330
але вы маглі б адвольна
абвясціць тып дадзеных у якасці значэння

93
00:04:49,330 --> 00:04:51,160
і выкарыстоўваць гэта ў цэлым.

94
00:04:51,160 --> 00:04:56,030
Гэта элемент, мы хочам паставіць у чаргу,
мы хочам, каб дадаць у канец чаргі.

95
00:04:56,030 --> 00:04:58,573
Тады мы сапраўды хочам, каб
размясціць гэтыя дадзеныя ў чарзе.

96
00:04:58,573 --> 00:05:01,490
У гэтым выпадку, змясціўшы яго ў
правільнае размяшчэнне нашага масіва,

97
00:05:01,490 --> 00:05:05,040
і то мы хочам, каб змяніць памер
чарзе, колькі элементаў мы

98
00:05:05,040 --> 00:05:07,050
У цяперашні час ёсць.

99
00:05:07,050 --> 00:05:07,990
>> Такім чынам, давайце пачнем.

100
00:05:07,990 --> 00:05:10,890
Тут, зноў жа, што агульная
Функцыя Форма дэкларацыі

101
00:05:10,890 --> 00:05:13,980
за тое, што паставіць у чаргу можа выглядаць.

102
00:05:13,980 --> 00:05:14,910
І тут мы ідзем.

103
00:05:14,910 --> 00:05:18,335
Давайце ў чаргу лік
28 у чарзе.

104
00:05:18,335 --> 00:05:19,460
Так што мы будзем рабіць?

105
00:05:19,460 --> 00:05:23,390
Ну, перад нашай чарзе
0, і з памерамі нашай чарзе

106
00:05:23,390 --> 00:05:29,680
ў стане 0, і так мы, верагодна, хочаце, каб пакласці
лік 28 у масіў колькасці элементаў

107
00:05:29,680 --> 00:05:31,124
0, праўда?

108
00:05:31,124 --> 00:05:32,540
Такім чынам, мы ў цяперашні час размешчаны, што там.

109
00:05:32,540 --> 00:05:34,820
Так што цяпер нам трэба змяніць?

110
00:05:34,820 --> 00:05:37,090
Мы не хочам, каб змяніць
фронт чарзе,

111
00:05:37,090 --> 00:05:40,850
таму што мы хочам ведаць, што элемент
мы, магчыма, спатрэбіцца з чаргі пазней.

112
00:05:40,850 --> 00:05:44,020
Так што прычына ў нас ёсць фронт ёсць
з'яўляецца свайго роду індыкатарам што

113
00:05:44,020 --> 00:05:46,439
найстарэйшы рэч у масіве.

114
00:05:46,439 --> 00:05:49,730
Ну самы стары рэч у array-- ў
Фактычна, адзіная рэч, у масіве права

115
00:05:49,730 --> 00:05:53,540
now-- 28, які з'яўляецца
на месцы масіва 0.

116
00:05:53,540 --> 00:05:56,160
Такім чынам, мы не хочам, каб
змяніць гэтую зялёную нумар,

117
00:05:56,160 --> 00:05:57,910
таму што гэта самы стары элемент.

118
00:05:57,910 --> 00:06:00,510
Хутчэй за ўсё, мы хочам, каб змяніць памер.

119
00:06:00,510 --> 00:06:04,110
Такім чынам, у гэтым выпадку, мы будзем
павялічыць памер 1.

120
00:06:04,110 --> 00:06:08,430
>> Цяпер наогул-то ідэі, дзе
Наступны элемент будзе ісці ў чарзе

121
00:06:08,430 --> 00:06:12,310
гэта дадаць гэтыя два нумары
разам, пярэдні і памер,

122
00:06:12,310 --> 00:06:16,390
і што скажу вам, дзе наступны
элемент у чарзе будзе ісці.

123
00:06:16,390 --> 00:06:18,130
Так што цяпер давайце ў чаргу іншы нумар.

124
00:06:18,130 --> 00:06:20,250
Давайце ў чаргу 33.

125
00:06:20,250 --> 00:06:24,480
Так 33 будзе ісці ў
Масіў месца 0 плюс 1.

126
00:06:24,480 --> 00:06:26,840
Такім чынам, у гэтым выпадку, гэта будзе
перайсці ў месцы масіва 1,

127
00:06:26,840 --> 00:06:29,500
і ў цяперашні час памер нашага чарзе 2.

128
00:06:29,500 --> 00:06:31,840
>> Зноў жа, мы не мяняем
пярэдняя нашай чарзе,

129
00:06:31,840 --> 00:06:34,730
таму што 28-ранейшаму
найстарэйшы элемент, і мы

130
00:06:34,730 --> 00:06:38,220
хачу, мэтай якіх, калі мы ў канчатковым выніку атрымаць
каб выманне з чаргі, выдаленне элементаў

131
00:06:38,220 --> 00:06:43,300
з гэтай чарзе, мы хочам ведаць,
дзе самы стары элемент.

132
00:06:43,300 --> 00:06:48,620
І таму мы заўсёды павінны падтрымліваць
некаторыя паказчыкам, дзе гэта.

133
00:06:48,620 --> 00:06:50,410
Дык вось тое, што 0 ёсць для.

134
00:06:50,410 --> 00:06:52,910
Гэта тое, што фронт там.

135
00:06:52,910 --> 00:06:55,022
>> Давайце ў Дадае яшчэ адзін элемент, 19.

136
00:06:55,022 --> 00:06:56,980
Я ўпэўнены, што вы можаце здагадацца,
дзе 19 будзе ісці.

137
00:06:56,980 --> 00:06:59,860
Гэта збіраецца ісці ў
Масіў месца № 2.

138
00:06:59,860 --> 00:07:01,570
Гэта плюс 2 0.

139
00:07:01,570 --> 00:07:03,199
І ў цяперашні час памер нашага чарзе 3.

140
00:07:03,199 --> 00:07:04,240
У нас ёсць 3 элемента ў ім.

141
00:07:04,240 --> 00:07:08,490
Так што, калі мы павінны былі, і мы не збіраемся
каб прама цяпер, у чаргу яшчэ адзін элемент,

142
00:07:08,490 --> 00:07:11,370
яна будзе ісці ў месцы масіва
Колькасць 3, а памер чарзе нашай

143
00:07:11,370 --> 00:07:13,160
будзе 4.

144
00:07:13,160 --> 00:07:15,279
Такім чынам, мы ў чарзе некалькі элементаў у цяперашні час.

145
00:07:15,279 --> 00:07:16,570
Зараз давайце пачнем, каб выдаліць іх.

146
00:07:16,570 --> 00:07:19,450
Давайце з чаргі іх з чаргі.

147
00:07:19,450 --> 00:07:23,340
>> Так падобна на поп, які з'яўляецца свайго роду
аналага гэтага для стэкаў,

148
00:07:23,340 --> 00:07:26,180
з чаргі неабходна прыму ў
паказальнік на queue-- раз,

149
00:07:26,180 --> 00:07:28,140
калі гэта не глабальна абвешчаныя.

150
00:07:28,140 --> 00:07:31,610
Цяпер мы хочам, каб змяніць месцазнаходжанне
у пярэдняй частцы чарзе.

151
00:07:31,610 --> 00:07:35,050
Гэта дзе ён накшталт ідзе
у гульню, што пярэдняя пераменная,

152
00:07:35,050 --> 00:07:37,310
таму што як толькі мы прыбіраем
элемент, мы хочам

153
00:07:37,310 --> 00:07:40,720
каб перанесьці яго на наступны найстарэйшы элемент.

154
00:07:40,720 --> 00:07:44,180
>> Затым мы хочам, каб паменшыць
памер чарзе,

155
00:07:44,180 --> 00:07:47,130
і то мы хочам, каб вярнуць значэнне
які быў выдалены з чаргі.

156
00:07:47,130 --> 00:07:48,921
Зноў жа, мы не хочам, каб проста выкінуць яго.

157
00:07:48,921 --> 00:07:51,170
Мы, верагодна, здабываюць
гэта ад queue-- мы знаходзімся

158
00:07:51,170 --> 00:07:54,170
выманне з чаргі, таму што мы клапоцімся пра яго.

159
00:07:54,170 --> 00:08:01,080
Такім чынам, мы хочам, каб гэтая функцыя вяртала
элемент дадзеных з значэння тыпу.

160
00:08:01,080 --> 00:08:04,360
Зноў жа, у гэтым выпадку значэнне цэлы лік.

161
00:08:04,360 --> 00:08:05,670
>> Так што цяпер давайце з чаргі нешта.

162
00:08:05,670 --> 00:08:09,310
Давайце выдаліць элемент з чаргі.

163
00:08:09,310 --> 00:08:15,970
Калі мы кажам, INT х роўны & Q, Ампэрсанд q--
яшчэ раз, што гэта паказальнік на гэты в дадзеных

164
00:08:15,970 --> 00:08:20,177
structure-- які элемент
збіраецца быць з чаргі?

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

166
00:08:23,840 --> 00:08:29,480
У гэтым выпадку, так як ён з'яўляецца першым
увайшоў, першым выйшаў структуры дадзеных, FIFO,

167
00:08:29,480 --> 00:08:33,690
Першае, што мы ўкладваем у гэта
Чарга была 28, так што ў гэтым выпадку,

168
00:08:33,690 --> 00:08:37,245
мы збіраемся ўзяць 28 з
чаргу, не 19, гэта тое, што

169
00:08:37,245 --> 00:08:38,870
мы зрабілі б, калі гэта было стэк.

170
00:08:38,870 --> 00:08:42,220
Мы збіраемся ўзяць 28 з чаргі.

171
00:08:42,220 --> 00:08:44,960
>> Падобна таму, што мы зрабілі з
стэк, мы на самай справе не

172
00:08:44,960 --> 00:08:47,345
збіраецеся выдаліць 28
ад самага чарзе,

173
00:08:47,345 --> 00:08:49,470
мы толькі збіраемся роду
з прыкінуцца, што гэта не існуе.

174
00:08:49,470 --> 00:08:51,678
Так што збіраецца застацца там
ў памяці, але мы проста

175
00:08:51,678 --> 00:08:57,820
збіраецца роду ігнаруюць яго, перамяшчаючы
іншыя два полі нашага кв дадзеных

176
00:08:57,820 --> 00:08:58,830
Структура.

177
00:08:58,830 --> 00:09:00,230
Мы збіраемся змяніць фронт.

178
00:09:00,230 --> 00:09:04,290
Q.front цяпер збіраецца
быць 1, таму што гэта цяпер

179
00:09:04,290 --> 00:09:07,740
найстарэйшы элемент у нас у
Чаргу, таму што мы ўжо выдаленыя 28,

180
00:09:07,740 --> 00:09:10,460
які быў былы найстарэйшым элементам.

181
00:09:10,460 --> 00:09:13,540
>> А цяпер, мы хочам змяніць
памер чарзе

182
00:09:13,540 --> 00:09:15,780
двух элементаў замест трох.

183
00:09:15,780 --> 00:09:20,450
Цяпер успомніце, раней я сказаў, калі мы
Каб дадаць элементы ў чаргу,

184
00:09:20,450 --> 00:09:26,000
мы ставім яго ў месцы масіва
які з'яўляецца сумай пярэдняй і памеру.

185
00:09:26,000 --> 00:09:29,050
Такім чынам, у гэтым выпадку, мы да гэтага часу пакласці
гэта, наступны элемент у чарзе,

186
00:09:29,050 --> 00:09:33,360
ў месцы масіва 3 і
мы ўбачым, што ў секунду.

187
00:09:33,360 --> 00:09:35,730
>> Такім чынам, мы ў цяперашні час з чаргі нашай
Першы элемент з чаргі.

188
00:09:35,730 --> 00:09:36,480
Давайце зробім гэта зноў.

189
00:09:36,480 --> 00:09:38,696
Давайце здымем іншы
Элемент з чаргі.

190
00:09:38,696 --> 00:09:42,400
У выпадку, цяперашні найстарэйшых
элемент размяшчэнне масіў 1.

191
00:09:42,400 --> 00:09:44,220
Вось што кажа нам q.front.

192
00:09:44,220 --> 00:09:46,980
Гэта зялёны скрыню кажа нам, што
гэта самы стары элемент.

193
00:09:46,980 --> 00:09:49,310
І так, х стане 33.

194
00:09:49,310 --> 00:09:52,130
Мы проста выгляд забудзьцеся
што 33 існуе ў масіве,

195
00:09:52,130 --> 00:09:55,100
і мы будзем казаць, што цяпер, то
Новы найстарэйшы элемент у чарзе

196
00:09:55,100 --> 00:09:58,900
знаходзіцца ў месцазнаходжанні рашоткі 2, і памеру
чарзе, колькасць элементаў

197
00:09:58,900 --> 00:10:02,152
у нас у чарзе, 1.

198
00:10:02,152 --> 00:10:05,110
Зараз давайце ў чаргу нешта, і я
накшталт даў гэта далёка секунду назад,

199
00:10:05,110 --> 00:10:10,340
але калі мы хочам, каб пакласці 40 Into The
Чаргу, дзе гэта 40 пойдзе?

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

201
00:10:12,880 --> 00:10:17,730
Ну, мы былі пакласці яе
у q.front плюс памер чарзе,

202
00:10:17,730 --> 00:10:20,850
і таму мае сэнс, каб
на самай справе паставіць 40 тут.

203
00:10:20,850 --> 00:10:22,840
Зараз звернеце ўвагу, што ў
некаторая кропка, мы ідзем

204
00:10:22,840 --> 00:10:27,980
каб дабрацца да канца
наш масіў ўнутры Q,

205
00:10:27,980 --> 00:10:32,010
але знік з 28 і 33--
яны на самой справе, тэхнічна

206
00:10:32,010 --> 00:10:33,300
адкрытыя прасторы, правільна?

207
00:10:33,300 --> 00:10:36,040
І так, мы можам eventually--
гэтае правіла дадання

208
00:10:36,040 --> 00:10:40,390
гэтыя два together-- мы ў канчатковым выніку можа
трэба мод памерам ёмістасці

209
00:10:40,390 --> 00:10:41,410
так што мы можам абгарнуць вакол.

210
00:10:41,410 --> 00:10:43,620
>> Так што, калі мы атрымліваем элемент
№ 10, калі мы

211
00:10:43,620 --> 00:10:48,790
замяніўшы яго ў элемент нумар 10, мы б
на самай справе паклаў яго ў масіў размяшчэння 0.

212
00:10:48,790 --> 00:10:50,997
І калі мы збіраемся
Масіў location-- прабачце,

213
00:10:50,997 --> 00:10:53,080
калі мы дадалі іх разам,
і мы атрымалі на нумар

214
00:10:53,080 --> 00:10:56,330
11 будзе, дзе мы павінны былі б паставіць
яго, што не існуе ў гэтым array--

215
00:10:56,330 --> 00:10:58,200
яна будзе выходзіць за межы.

216
00:10:58,200 --> 00:11:03,367
Мы маглі б мода на 10 і паставіць
гэта ў месцы масіва 1.

217
00:11:03,367 --> 00:11:04,450
Дык вось, як чарзе працуюць.

218
00:11:04,450 --> 00:11:08,540
Яны заўсёды будуць ісці злева
направа і, магчыма, абгарнуць вакол.

219
00:11:08,540 --> 00:11:11,280
І вы ведаеце, што яны
поўным аб'ёме, калі памер, што чырвонай скрынцы,

220
00:11:11,280 --> 00:11:13,710
становіцца роўным ёмістасці.

221
00:11:13,710 --> 00:11:16,720
І так пасля таго як мы дадалі 40 да
Чаргу, добра, што мы павінны рабіць?

222
00:11:16,720 --> 00:11:19,890
Ну, самы стары элемент
у чарзе яшчэ 19,

223
00:11:19,890 --> 00:11:21,990
такім чынам, мы не хочам, каб змяніць
фронт чарзе,

224
00:11:21,990 --> 00:11:23,820
але цяпер у нас ёсць два
элементы ў чарзе,

225
00:11:23,820 --> 00:11:28,710
і таму мы хочам, каб павялічыць
наш памер ад 1 да 2.

226
00:11:28,710 --> 00:11:31,820
>> Гэта даволі шмат, яго
працы з масівамі на аснове чэргаў,

227
00:11:31,820 --> 00:11:33,630
і падобны на стэк,
ёсць таксама спосаб

228
00:11:33,630 --> 00:11:36,450
ажыццявіць чаргу ў якасці звязанага спісу.

229
00:11:36,450 --> 00:11:40,150
Цяпер, калі гэтая структура дадзеных тыпу
выглядае знаёмым для вас, гэта так.

230
00:11:40,150 --> 00:11:43,780
Гэта не односвязанны спіс,
гэта ўдвая звязаны спіс.

231
00:11:43,780 --> 00:11:46,790
А цяпер, як у бок, гэта
на самай справе можна рэалізаваць

232
00:11:46,790 --> 00:11:50,160
чэргі ў односвязный спіс, але
Я думаю, што з пункту гледжання візуалізацыі,

233
00:11:50,160 --> 00:11:53,350
гэта на самай справе можа дапамагчы, каб паглядзець
гэта як двойчы звязанага спісу.

234
00:11:53,350 --> 00:11:56,850
Але гэта, безумоўна, можна
зрабіць гэта як односвязный спіс.

235
00:11:56,850 --> 00:12:00,110
>> Такім чынам, давайце паглядзім на
што гэта можа выглядаць.

236
00:12:00,110 --> 00:12:02,750
Калі мы хочам, каб enquue--
так што цяпер, раз мы

237
00:12:02,750 --> 00:12:05,360
пераход на звязаны спіс
тут на аснове мадэлі.

238
00:12:05,360 --> 00:12:08,420
Калі мы хочам, каб паставіць у чаргу, мы хочам
каб дадаць новы элемент, а

239
00:12:08,420 --> 00:12:09,730
тое, што нам трэба рабіць?

240
00:12:09,730 --> 00:12:12,770
Ну, у першую чаргу, таму, што
мы дадаем у канец

241
00:12:12,770 --> 00:12:15,520
і выдаленне ад
пачатак, мы, верагодна,

242
00:12:15,520 --> 00:12:20,050
хочаце захаваць паказальнікі на абодва
галава і хвост сувязнога спісу?

243
00:12:20,050 --> 00:12:22,660
Хвост з'яўляецца іншы тэрмін для
канец звязанага спісу,

244
00:12:22,660 --> 00:12:24,496
апошні элемент ў звязаным спісе.

245
00:12:24,496 --> 00:12:26,620
І гэта будзе магчыма,
зноў, быць карысным для нас

246
00:12:26,620 --> 00:12:28,477
калі яны з'яўляюцца глабальнымі зменнымі.

247
00:12:28,477 --> 00:12:31,060
Але цяпер, калі мы хочам, каб дадаць новы
элемент, што мы павінны рабіць?

248
00:12:31,060 --> 00:12:35,262
Тое, што мы проста [? Малако?] Або дынамічна
вылучыць наш новы вузел для сябе.

249
00:12:35,262 --> 00:12:38,220
А потым, як і калі мы дадаем любы
элемент двойчы звязанага спісу мы,

250
00:12:38,220 --> 00:12:40,410
проста трэба адсартаваць of--
гэтыя апошнія тры крокі тут

251
00:12:40,410 --> 00:12:43,330
проста ўсё пра перасоўванне
ўказальнікі ў правільным шляху

252
00:12:43,330 --> 00:12:46,710
так, што элемент будзе дададзены
ланцуг без разрыву ланцугу

253
00:12:46,710 --> 00:12:49,580
або зрабіць нейкі памылцы
або якія маюць нейкія аварыі

254
00:12:49,580 --> 00:12:54,505
адбылося ў выніку чаго мы выпадкова
сіротам некаторыя элементы нашай чаргі.

255
00:12:54,505 --> 00:12:55,880
Вось тое, што гэта можа выглядаць.

256
00:12:55,880 --> 00:13:00,980
Мы хочам, каб дадаць элемент
10 у канцы гэтай чарзе.

257
00:13:00,980 --> 00:13:03,380
Такім чынам, самы стары элемент тут
прадстаўлена галавы.

258
00:13:03,380 --> 00:13:06,800
Гэта першае, што мы ставім
у гэтым гіпатэтычным чарзе тут.

259
00:13:06,800 --> 00:13:10,430
І хвост, 13, з'яўляецца найбольш
нядаўна дадалі элемент.

260
00:13:10,430 --> 00:13:17,030
І таму, калі мы хочам, каб паставіць у чаргу 10 у
гэтая чаргу, мы хочам, каб пакласці яго пасля 13 гадоў.

261
00:13:17,030 --> 00:13:19,860
І таму мы збіраемся, каб дынамічна
вылучыць месца для новага вузла

262
00:13:19,860 --> 00:13:23,280
і праверыць нуль, каб пераканацца,
мы не маем правал памяці.

263
00:13:23,280 --> 00:13:27,040
Тады мы ідзем да
размясціць 10 у гэтым вузле,

264
00:13:27,040 --> 00:13:30,030
і зараз мы павінны быць асцярожныя,
аб тым, як мы арганізуем паказальнікі

265
00:13:30,030 --> 00:13:32,180
такім чынам, мы не разарваць ланцуг.

266
00:13:32,180 --> 00:13:38,910
>> Мы можам ўсталяваць 10 ў папярэдняе поле
пазначыць вярнуцца да старога хвост,

267
00:13:38,910 --> 00:13:41,620
і так '10 будзе
Новы хвост нейкі момант

268
00:13:41,620 --> 00:13:44,459
да таго часу, усе гэтыя
ланцугі звязаныя,

269
00:13:44,459 --> 00:13:46,250
нічога не прыйдзе
пасля 10 прама цяпер.

270
00:13:46,250 --> 00:13:49,880
І так 10 у наступным паказальнік
будзе паказваць на нуль,

271
00:13:49,880 --> 00:13:53,580
а затым, пасля мы зробім гэта, пасля таго як мы
10 падлучаны таму ў ланцугу,

272
00:13:53,580 --> 00:13:57,780
мы можам узяць старую галаву, або, прабачце
я, стары хвост чаргі.

273
00:13:57,780 --> 00:14:02,980
Старая канец чаргі,
13 і каб яна паказвала на 10.

274
00:14:02,980 --> 00:14:08,220
А цяпер, у гэты момант, у нас ёсць
ў чаргу лік 10 у гэтай чарзе.

275
00:14:08,220 --> 00:14:14,740
Усё, што мы павінны зрабіць цяпер, гэта проста перанесьці
хвост паказваюць на 10 замест 13.

276
00:14:14,740 --> 00:14:17,630
>> Выманне з чаргі на самай справе
вельмі падобны на выскокваюць

277
00:14:17,630 --> 00:14:21,710
з чаркі, якая
рэалізаваны ў выглядзе звязанага спісу

278
00:14:21,710 --> 00:14:24,040
калі вы бачылі відэа стэкі.

279
00:14:24,040 --> 00:14:27,280
Усё, што мы павінны зрабіць, гэта пачаць на
пачынаючы, знайсці другі элемент,

280
00:14:27,280 --> 00:14:30,480
вызваліць першы элемент,
а затым перамесціце галаву

281
00:14:30,480 --> 00:14:32,930
каб паказаць на другі элемент.

282
00:14:32,930 --> 00:14:37,920
Напэўна лепш візуалізаваць яго
проста быць вельмі зразумела.

283
00:14:37,920 --> 00:14:39,230
Дык вось наша чарга зноў.

284
00:14:39,230 --> 00:14:42,600
12 з'яўляецца найстарэйшым элементам
ў нашай чарзе, галавы.

285
00:14:42,600 --> 00:14:46,210
10 з'яўляецца найноўшым элементам
ў нашай чарзе, наш хвост.

286
00:14:46,210 --> 00:14:49,310
>> І таму, калі мы хочам
каб з чаргі элемент,

287
00:14:49,310 --> 00:14:52,202
мы хочам, каб выдаліць самы стары элемент.

288
00:14:52,202 --> 00:14:52,910
Дык што ж нам рабіць?

289
00:14:52,910 --> 00:14:55,243
Ну, мы павінны ўсталяваць паказальнік абыходу
які пачынаецца ў галаве,

290
00:14:55,243 --> 00:14:57,840
і мы перамясціць яго так, каб ён
паказвае на другі элемент

291
00:14:57,840 --> 00:15:02,290
гэта нешта queue-- кажучы TRAV
Trav роўная стрэлку побач, напрыклад,

292
00:15:02,290 --> 00:15:07,170
будзе рухацца TRAV ёсць, каб паказаць на
15, якая, пасля таго як мы з чаргі 12,

293
00:15:07,170 --> 00:15:13,030
або пасля таго як мы выдаліць 12, будзе
стаць тое найстарэйшы элемент.

294
00:15:13,030 --> 00:15:16,360
>> Цяпер у нас ёсць ўлада над першым
элемент з дапамогай паказальніка галавы

295
00:15:16,360 --> 00:15:19,440
а другі элемент
з дапамогай паказальніка Trav.

296
00:15:19,440 --> 00:15:25,170
Цяпер мы можам бясплатна галаву, і тады мы можам
кажуць нічога не прыходзіць да 15 больш.

297
00:15:25,170 --> 00:15:29,990
Такім чынам, мы можам змяніць папярэдняе 15
паказальнік, каб паказаць на нуль,

298
00:15:29,990 --> 00:15:31,874
і мы проста перанесьці галаву над.

299
00:15:31,874 --> 00:15:32,540
І мы ідзем.

300
00:15:32,540 --> 00:15:35,840
Цяпер у нас ёсць паспяхова
з чаргі 12, а цяпер мы

301
00:15:35,840 --> 00:15:39,180
ёсць іншы чарзе 4 элементаў.

302
00:15:39,180 --> 00:15:41,700
Гэта даволі шмат, усё
ёсць у чэргах,

303
00:15:41,700 --> 00:15:45,810
і на аснове масіва і звязанага спісу на базе.

304
00:15:45,810 --> 00:15:46,860
Я Дуг Лойд.

305
00:15:46,860 --> 00:15:49,100
Гэта CS 50.

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