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

2
00:00:05,204 --> 00:00:07,370
داگ لوید: بنابراین اگر شما
تماشای ویدئو بر روی پشته،

3
00:00:07,370 --> 00:00:09,870
این است که احتمالا رفتن به احساس
مانند یک کمی از deja vu به.

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
>> بر خلاف یک پشته، که
ساختار LIFO است،

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
و dequeue است که
به حذف از قدیمی ترین

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
بنابراین با در نوبت قراردادن، آن را با اضافه کردن به
پایان، از بین بردن از جلو.

40
00:02:07,570 --> 00:02:10,639
بنابراین قدیمی ترین چیزی که در آن وجود دارد
همیشه چیزی که بعد از

41
00:02:10,639 --> 00:02:13,620
به بیرون آمدن اگر ما سعی
و dequeue چیزی.

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
که محدودیت این نوع C
از به اجرا می گذارد بر ما است که ما

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
بنابراین ما می دانیم که عنصر
ما می خواهیم به dequeue،

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
Q به جای نوع داده q است.

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
چرا که ما می خواهند بدانند چه عنصر
ما ممکن است نیاز به dequeue بعد.

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
خوب قدیمی ترین چیزی که در آرایه در
واقع، تنها چیزی که در آرایه سمت راست

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
می خواهید to-- هنگامی که ما در نهایت
به dequeuing، از بین بردن عناصر

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
که 0 به علاوه 2 است.

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
بنابراین ما در حال حاضر چند عنصر را enqueued است.

145
00:07:15,279 --> 00:07:16,570
حالا اجازه دهید شروع به آنها را حذف کنید.

146
00:07:16,570 --> 00:07:19,450
اجازه دهید آنها را از صف dequeue.

147
00:07:19,450 --> 00:07:23,340
>> بسیار شبیه به موسیقی پاپ، که نوعی
از آنالوگ از این آمدن،

148
00:07:23,340 --> 00:07:26,180
dequeue نیاز به پذیرش یک
اشاره گر به 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
dequeuing چون ما در مورد آن اهمیت می دهند.

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
>> بنابراین در حال حاضر اجازه دهید چیزی dequeue.

162
00:08:05,670 --> 00:08:09,310
بیایید یک عنصر از صف حذف.

163
00:08:09,310 --> 00:08:15,970
اگر ما می گویند INT x برابر و Q، علامت q--
دوباره که یک اشاره گر به این اطلاعات Q است

164
00:08:15,970 --> 00:08:20,177
structure-- چه عنصر
در حال رفتن به dequeued شود؟

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
رفتن به نوع آن را با حرکت چشم پوشی
دو رشته دیگر داده Q ما

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
>> بنابراین ما در حال حاضر dequeued به ما
اولین عنصر از صف.

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
و به این ترتیب، X تبدیل خواهد شد 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 به
صف، که در آن 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 می شود که در آن ما باید برای قرار دادن
آن را، که در این آرایه وجود ندارد

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
و بررسی برای NULL مطمئن شوید
ما یک شکست حافظه ندارد.

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 به این صف را enqueued.

275
00:14:08,220 --> 00:14:14,740
همه ما نیاز به انجام اکنون فقط حرکت
دم به نقطه را به 10 به جای 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing است که در واقع
بسیار شبیه به ظاهر

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
>> و تا زمانی که ما می خواهیم
به dequeue یک عنصر،

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، که، پس از ما dequeue 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
در حال حاضر ما موفقیت
dequeued 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