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
>> בניגוד לערימה, ש
הוא מבנה 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
השמות Enqueue, אשר הוא להוסיף
אלמנט חדש לסוף התור,

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
אז עם Enqueue, זה מוסיף ל
הסוף, הסרת מהחזית.

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
>> אז הפעולה הראשונה שאנחנו יכולים
לבצע הוא Enqueue משהו,

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
ובכן פונקציה זו Enqueue צרכי
לקבל מצביע לתורנו.

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
זה האלמנט שאנחנו רוצים Enqueue,
אנחנו רוצים להוסיף לסוף התור.

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
למה Enqueue עשוי להיראות.

102
00:05:13,980 --> 00:05:14,910
וכאן אנחנו הולכים.

103
00:05:14,910 --> 00:05:18,335
בואו Enqueue המספר
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
ובכן הדבר העתיק ביותר ב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
אז עכשיו בואו Enqueue מספר אחר.

124
00:06:18,130 --> 00:06:20,250
בואו Enqueue 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
רוצה צריכה-- כאשר אנו סופו של דבר לקבל
ל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
>> בוא בEnqueue אלמנט אחד יותר, 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
אז אם היינו, ואנחנו לא הולכים
לעכשיו, Enqueue אלמנט אחר,

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
בואו 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
עכשיו בואו Enqueue משהו, ואני
סוג של נתן זה משם לפני שנייה,

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-- סופו של דבר עשוי
צריך mod על ידי הגודל של קיבולת

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
אנחנו יכולים mod על ידי 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
אם אנחנו רוצים Enqueue, אנחנו רוצים
כדי להוסיף אלמנט חדש, גם

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
מה אנחנו פשוט [? malak?] או באופן דינמי
להקצות הצומת החדשה שלנו לעצמנו.

249
00:12:35,262 --> 00:12:38,220
ואז, בדיוק כמו כאשר אנו מוסיפים כל
אלמנט לנו רשימה מקושרת כפול,

250
00:12:38,220 --> 00:12:40,410
רק צריך למיין ל--
אלה שלושה הצעדים האחרונים כאן

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
ולכן אם אנחנו רוצים Enqueue 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 מצביע הבא
יצביע על null,

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
>> 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-- משהו באומר טראב
שווה טראב החץ הבא, למשל,

292
00:15:02,290 --> 00:15:07,170
יעבור טראב יש להצביע על
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
והמרכיב השני
באמצעות טראב המצביע.

296
00:15:19,440 --> 00:15:25,170
אנחנו יכולים ראש עכשיו בחינם, ואז אנחנו יכולים
אומר שום דבר לא בא לפני 15 יותר.

297
00:15:25,170 --> 00:15:29,990
אז אנחנו יכולים לשנות את 15 של קודמים
מצביע להצביע על null,

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
זה 50 CS.

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