1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
داگ لوید: همه حق است،
بنابراین این نقطه شما

3
00:00:05,990 --> 00:00:09,020
احتمالا بسیار آشنا
با آرایه ها و لیست های پیوندی

4
00:00:09,020 --> 00:00:10,950
است که دو اولیه
ساختمان داده ایم

5
00:00:10,950 --> 00:00:16,810
در مورد برای نگه داشتن مجموعه ای از صحبت
داده ها از انواع داده های مشابه سازمان یافته است.

6
00:00:16,810 --> 00:00:19,080
>> در حال حاضر ما قصد داریم به بحث
در مورد یک زن و شوهر از تغییرات

7
00:00:19,080 --> 00:00:20,330
در آرایه ها و لیست های پیوندی.

8
00:00:20,330 --> 00:00:22,362
در این فیلم ما در حال رفتن
به مورد پشته صحبت کنید.

9
00:00:22,362 --> 00:00:25,320
به طور خاص ما قصد داریم به بحث
در مورد ساختار داده به نام پشته.

10
00:00:25,320 --> 00:00:28,510
به یاد بیاورید از بحث های قبلی
در مورد اشاره گر و حافظه،

11
00:00:28,510 --> 00:00:32,060
که پشته است که همچنین
نام برای یک بخش از حافظه

12
00:00:32,060 --> 00:00:34,980
که در آن استاتیک اعلام
حافظه حافظه که شما

13
00:00:34,980 --> 00:00:38,730
نام، متغیرها که شما نام، ET
غیره و عملکرد فریم که ما نیز

14
00:00:38,730 --> 00:00:41,000
قاب پشته پاسخ وجود داشته باشد.

15
00:00:41,000 --> 00:00:45,421
بنابراین این یک ساختمان داده پشته است
یک قطعه پشته در حافظه.

16
00:00:45,421 --> 00:00:45,920
باشه.

17
00:00:45,920 --> 00:00:46,890
>> اما آنچه که یک پشته است؟

18
00:00:46,890 --> 00:00:49,220
بنابراین آن را بسیار بسیار تنها
نوع خاصی از ساختار

19
00:00:49,220 --> 00:00:51,190
که حفظ داده ها در یک روش سازمان یافته.

20
00:00:51,190 --> 00:00:53,760
و نیز دو بسیار وجود دارد
روش معمول برای پیاده سازی

21
00:00:53,760 --> 00:00:57,380
پشته با استفاده از دو ساختمان داده
که ما در حال حاضر با آن آشنا هستید،

22
00:00:57,380 --> 00:01:00,340
آرایه ها و لیست های پیوندی.

23
00:01:00,340 --> 00:01:04,430
چه چیزی یک ویژه پشته است که
روشی که در آن ما اطلاعات قرار

24
00:01:04,430 --> 00:01:08,200
را به پشته، و راه ما
حذف اطلاعات از پشته.

25
00:01:08,200 --> 00:01:11,600
به طور خاص با پشته
حکومت تنها ترین است

26
00:01:11,600 --> 00:01:15,830
اخیرا عنصر اضافه شده می تواند حذف شود.

27
00:01:15,830 --> 00:01:17,660
>> بنابراین فکر می کنم در مورد آن به عنوان یک پشته است.

28
00:01:17,660 --> 00:01:21,170
ما در حال آلات اطلاعات
در بالای خود،

29
00:01:21,170 --> 00:01:24,271
و تنها چیزی که در بالای
از شمع تواند حذف شود.

30
00:01:24,271 --> 00:01:27,020
ما می توانیم چیزی را حذف کنید زیر
چرا که همه چیز دیگری

31
00:01:27,020 --> 00:01:28,020
سقوط و سقوط بیش از.

32
00:01:28,020 --> 00:01:32,580
بنابراین ما واقعا در حال ایجاد یک پشته که
ما پس از آن باید برای حذف قطعه قطعه.

33
00:01:32,580 --> 00:01:36,590
به این دلیل ما معمولا مراجعه
به یک پشته به عنوان یک ساختار LIFO،

34
00:01:36,590 --> 00:01:38,940
آخرین در، اولین بار.

35
00:01:38,940 --> 00:01:42,290
LIFO، آخرین در، اولین بار.

36
00:01:42,290 --> 00:01:45,635
>> بنابراین به خاطر این محدودیت در
چگونه اطلاعات را می توان به اضافه

37
00:01:45,635 --> 00:01:49,080
و از پشته برداشته است، واقعا وجود دارد
تنها دو چیز ما می توانیم با یک پشته را انجام دهد.

38
00:01:49,080 --> 00:01:52,010
ما می توانیم فشار است، که
مدت ما برای اضافه کردن استفاده

39
00:01:52,010 --> 00:01:55,130
یک عنصر جدید به بالای
پشته، و یا اگر پشته وجود ندارد

40
00:01:55,130 --> 00:01:58,550
و ما آن را ایجاد، از ابتدا،
ایجاد پشته در وهله اول

41
00:01:58,550 --> 00:02:00,110
می شود هل دادن.

42
00:02:00,110 --> 00:02:04,990
و سپس پاپ، که آن نوع CS است
مدت استفاده می کنیم برای حذف اخیرا

43
00:02:04,990 --> 00:02:08,330
اضافه شدن عنصر از بالای پشته.

44
00:02:08,330 --> 00:02:11,130
>> بنابراین ما در حال رفتن به نگاه در هر دو
پیاده سازی، بر اساس هر دو آرایه

45
00:02:11,130 --> 00:02:13,120
و لیست پیوندی است.

46
00:02:13,120 --> 00:02:14,870
و ما قصد داریم به
با آرایه بر اساس شروع می شود.

47
00:02:14,870 --> 00:02:19,990
بنابراین در اینجا ایده اولیه از چه
ساختار داده پشته آرایه بر اساس

48
00:02:19,990 --> 00:02:21,140
نگاه می خواهم.

49
00:02:21,140 --> 00:02:23,740
ما تعریف تایپ کنید.

50
00:02:23,740 --> 00:02:27,790
داخل که ما دو تن از اعضای
و یا زمینه های از ساختار.

51
00:02:27,790 --> 00:02:29,880
ما یک آرایه.

52
00:02:29,880 --> 00:02:32,400
و دوباره من با استفاده از
دلخواه ارزش نوع داده.

53
00:02:32,400 --> 00:02:35,180
>> بنابراین این می تواند هر نوع داده ها،
کاراکتر int یا برخی اطلاعات دیگر

54
00:02:35,180 --> 00:02:37,080
نوع شما قبلا ایجاد شده است.

55
00:02:37,080 --> 00:02:39,861
بنابراین ما باید یک آرایه از ظرفیت اندازه.

56
00:02:39,861 --> 00:02:44,010
ظرفیت که یک پوند ثابت تعریف شده،
شاید در جایی دیگر در فایل ما.

57
00:02:44,010 --> 00:02:47,550
بنابراین با این خاص متوجه حال حاضر
اجرای ما محدوده

58
00:02:47,550 --> 00:02:49,800
خودمان را به عنوان به طور معمول بود
در مورد آرایه ها،

59
00:02:49,800 --> 00:02:53,170
که ما به صورت پویا نمی توانید تغییر اندازه،
که در آن یک تعداد معینی وجود دارد

60
00:02:53,170 --> 00:02:55,450
حداکثر عناصر است که
ما می توانیم در پشته ما قرار داده است.

61
00:02:55,450 --> 00:02:57,930
در این مورد آن عناصر ظرفیت است.

62
00:02:57,930 --> 00:03:00,310
>> ما همچنین پیگیری
بالای پشته.

63
00:03:00,310 --> 00:03:04,350
چه عنصر است که بسیاری از
به تازگی اضافه شده به پشته؟

64
00:03:04,350 --> 00:03:07,470
و بنابراین ما پیگیری که
در یک متغیر به نام بالا.

65
00:03:07,470 --> 00:03:11,692
و همه از این می شود تا با هم پیچیده شده
به یک نوع داده جدید به نام پشته.

66
00:03:11,692 --> 00:03:13,400
و زمانی که ما در حال ایجاد
این نوع داده جدید

67
00:03:13,400 --> 00:03:15,410
ما می توانیم آن مانند درمان
هر نوع اطلاعات دیگر.

68
00:03:15,410 --> 00:03:20,970
ما می توانیم پشته درست مانند اعلام،
ما می تواند نوع int x، یا کاراکتر Y را انجام دهد.

69
00:03:20,970 --> 00:03:22,990
و وقتی می گوییم پشته
بازدید کنندگان، به خوبی چه اتفاقی می افتد

70
00:03:22,990 --> 00:03:26,420
است که ما یک مجموعه ای از
حافظه کنار گذاشته برای ما تعیین شده است.

71
00:03:26,420 --> 00:03:28,770
>> در این ظرفیت مورد
من ظاهرا تصمیم گرفته اید

72
00:03:28,770 --> 00:03:33,470
10 دلیل است که من یک
متغیر از نوع پشته

73
00:03:33,470 --> 00:03:35,320
که شامل دو حوزه یاد می آورند.

74
00:03:35,320 --> 00:03:38,330
یک آرایه، در این مورد است که
به یک آرایه از اعداد صحیح

75
00:03:38,330 --> 00:03:40,440
به عنوان مورد در بسیاری از نمونه من است.

76
00:03:40,440 --> 00:03:43,996
و متغیر عدد صحیح دیگر
قادر به ذخیره سازی بالا،

77
00:03:43,996 --> 00:03:45,870
اخیرا اضافه شده
عنصر به پشته.

78
00:03:45,870 --> 00:03:50,290
بنابراین یکی پشته از آنچه که ما
فقط تعریف به نظر می رسد مثل این.

79
00:03:50,290 --> 00:03:53,190
این جعبه حاوی این
آرایه ای از 10 چه

80
00:03:53,190 --> 00:03:57,280
خواهد بود اعداد صحیح در این مورد و
یکی دیگر از متغیرهای عدد صحیح وجود دارد به رنگ سبز

81
00:03:57,280 --> 00:04:00,010
نشان می دهد که بالای پشته.

82
00:04:00,010 --> 00:04:02,600
>> به مجموعه ای از بالای
پشته ما فقط می گویند s.top.

83
00:04:02,600 --> 00:04:04,890
این که چگونه دسترسی ما
درست فراخوان ساختار.

84
00:04:04,890 --> 00:04:10,460
s.top برابر با 0 موثر
این کار را به پشته ما.

85
00:04:10,460 --> 00:04:12,960
پس باز هم ما دو عملیات
که ما هم اکنون می توانید انجام دهید.

86
00:04:12,960 --> 00:04:14,270
ما می توانیم فشار و ما می توانیم پاپ.

87
00:04:14,270 --> 00:04:15,635
بیایید با فشار شروع می شود.

88
00:04:15,635 --> 00:04:18,260
باز هم، هل دادن است اضافه کردن یک جدید
عنصر به بالای پشته.

89
00:04:18,260 --> 00:04:21,460
>> بنابراین چه چیزی ما باید انجام دهید در
این آرایه پیاده سازی بر اساس؟

90
00:04:21,460 --> 00:04:23,210
به خوبی در عمومی
تابع فشار است که

91
00:04:23,210 --> 00:04:26,160
به نیاز به قبول
اشاره گر به پشته.

92
00:04:26,160 --> 00:04:28,610
در حال حاضر یک ثانیه و فکر می کنم در مورد آن.

93
00:04:28,610 --> 00:04:32,840
چرا ما می خواهیم به قبول
یک اشاره گر به پشته؟

94
00:04:32,840 --> 00:04:36,830
به یاد بیاورید از فیلم قبلی در
دامنه متغیر و اشاره گر،

95
00:04:36,830 --> 00:04:42,350
چه اتفاقی خواهد افتاد اگر ما فقط ارسال
پشته، ها و نه به عنوان یک پارامتر؟

96
00:04:42,350 --> 00:04:45,770
آنچه در واقع وجود دارد در منتقل می شود؟

97
00:04:45,770 --> 00:04:49,430
به یاد داشته باشید که ما در حال ایجاد یک کپی
هنگامی که ما آن را به یک تابع

98
00:04:49,430 --> 00:04:51,160
مگر اینکه ما استفاده از اشاره گر.

99
00:04:51,160 --> 00:04:55,380
و بنابراین این تابع فشار نیازهای
به قبول یک اشاره گر به پشته

100
00:04:55,380 --> 00:04:59,160
به طوری که ما در واقع در حال تغییر
پشته ما قصد داریم به تغییر دهید.

101
00:04:59,160 --> 00:05:03,060
>> نکته دیگر فشار می خواهد احتمالا به
قبول یک عنصر داده ها از ارزش نوع است.

102
00:05:03,060 --> 00:05:06,970
در این مورد، دوباره، یک عدد صحیح است که
ما قصد داریم برای اضافه کردن به بالای پشته.

103
00:05:06,970 --> 00:05:08,680
بنابراین ما دو پارامتر ما است.

104
00:05:08,680 --> 00:05:11,310
چه هستند که ما را به رفتن
حال حاضر در داخل از فشار را انجام دهد؟

105
00:05:11,310 --> 00:05:14,860
خوب، به سادگی، ما فقط رفتن به اضافه کردن
که عنصر به بالای پشته

106
00:05:14,860 --> 00:05:22,860
و پس از آن تغییر که در آن بالای
پشته، که S نقطه ارزش بالا.

107
00:05:22,860 --> 00:05:25,639
بنابراین این چه یک تابع است
اعلامیه برای فشار

108
00:05:25,639 --> 00:05:27,680
ممکن است مانند در یک نگاه
مبتنی بر آرایه پیاده سازی.

109
00:05:27,680 --> 00:05:30,967
>> باز هم این یک قانون سخت و سریع نیست
که شما می توانید این را تغییر دهید و

110
00:05:30,967 --> 00:05:32,050
آن را در راه های مختلف متفاوت است.

111
00:05:32,050 --> 00:05:33,840
شاید بازدید کنندگان در سطح جهان اعلام کرد.

112
00:05:33,840 --> 00:05:36,180
و بنابراین شما حتی نمی نیاز
به عبور از آن به عنوان یک پارامتر است.

113
00:05:36,180 --> 00:05:39,125
این است که دوباره تنها
حالت کلی برای فشار.

114
00:05:39,125 --> 00:05:41,000
و مختلف وجود دارد
راه هایی برای پیاده سازی آن.

115
00:05:41,000 --> 00:05:42,810
اما در این مورد ما
فشار می گذرد را به

116
00:05:42,810 --> 00:05:48,540
دو استدلال، یک اشاره گر به پشته و
یک عنصر داده ها از ارزش نوع، عدد صحیح

117
00:05:48,540 --> 00:05:49,840
در این مورد.

118
00:05:49,840 --> 00:05:52,100
>> بنابراین ما اعلام، ما
گفت s.top برابر با 0.

119
00:05:52,100 --> 00:05:55,969
حالا اجازه دهید فشار
شماره 28 را بر روی پشته.

120
00:05:55,969 --> 00:05:57,010
خب به چه معنا است؟

121
00:05:57,010 --> 00:05:59,600
خوب در حال حاضر
بالای پشته 0 است.

122
00:05:59,600 --> 00:06:01,350
و بنابراین، آنچه اساسا
رفتن به است

123
00:06:01,350 --> 00:06:05,820
ما در حال رفتن به چوب تعداد
28 به محل آرایه 0.

124
00:06:05,820 --> 00:06:09,540
بسیار ساده، راست، که
بالا بود و در حال حاضر ما خوب به آن بروید.

125
00:06:09,540 --> 00:06:12,910
و پس از آن ما نیاز به تغییر چه
بالای پشته خواهد بود.

126
00:06:12,910 --> 00:06:15,130
به طوری که در کنار هم
ما فشار یک عنصر در،

127
00:06:15,130 --> 00:06:18,017
ما قصد داریم به ذخیره آن در
محل آرایه، احتمالا 0.

128
00:06:18,017 --> 00:06:20,100
ما نمی خواهیم به بازنویسی
آنچه که ما فقط قرار داده است.

129
00:06:20,100 --> 00:06:23,510
و بنابراین ما فقط حرکت بالا به 1.

130
00:06:23,510 --> 00:06:24,890
که احتمالا حس می کند.

131
00:06:24,890 --> 00:06:28,940
>> حال اگر ما خواهید برای قرار دادن عنصر دیگری
بر روی پشته، می گویند ما می خواهیم به فشار 33،

132
00:06:28,940 --> 00:06:33,190
خوب در حال حاضر ما فقط رفتن به 33
و آن را در شماره محل آرایه

133
00:06:33,190 --> 00:06:37,580
1، و پس از آن تغییر بالای ما
پشته به آرایه شماره محل دو.

134
00:06:37,580 --> 00:06:40,650
بنابراین اگر دفعه بعد ما می خواهیم
فشار یک عنصر را بر روی پشته،

135
00:06:40,650 --> 00:06:43,087
آن را در محل آرایه 2 قرار داده است.

136
00:06:43,087 --> 00:06:44,420
و اجازه دهید که یک بار دیگر انجام دهید.

137
00:06:44,420 --> 00:06:45,753
ما 19 را از پشته فشار.

138
00:06:45,753 --> 00:06:48,940
ما 19 در محل آرایه 2 قرار
و تغییر بالای پشته ما

139
00:06:48,940 --> 00:06:51,220
به محل آرایه 3
بنابراین اگر زمان ما بعدی

140
00:06:51,220 --> 00:06:54,780
نیاز به ایجاد یک فشار ما خوب به آن بروید.

141
00:06:54,780 --> 00:06:56,980
>> OK، به طوری که هل دادن به طور خلاصه.

142
00:06:56,980 --> 00:06:57,830
چه در مورد ظاهر؟

143
00:06:57,830 --> 00:07:00,240
بنابراین ظاهر مرتب کردن بر اساس است
همتای هل دادن.

144
00:07:00,240 --> 00:07:02,720
آن که ما چگونه داده ها را حذف از پشته.

145
00:07:02,720 --> 00:07:04,610
و در نیازهای پاپ
به انجام موارد زیر است.

146
00:07:04,610 --> 00:07:07,600
به آن نیاز دارد را به قبول یک اشاره گر به
پشته، دوباره در حالت کلی.

147
00:07:07,600 --> 00:07:10,480
در برخی از موارد دیگر شما ممکن است
پشته اعلام کرده اند در سطح جهان،

148
00:07:10,480 --> 00:07:13,910
که در این صورت شما لازم نیست که به تصویب آن
در حال حاضر دارای دلیل آن دسترسی به آن

149
00:07:13,910 --> 00:07:15,541
به عنوان یک متغیر جهانی است.

150
00:07:15,541 --> 00:07:17,040
اما پس از آن چه چیز دیگری ما باید انجام دهید؟

151
00:07:17,040 --> 00:07:21,000
خوب ما افزایش شد
بالای پشته در فشار،

152
00:07:21,000 --> 00:07:24,050
بنابراین ما در حال احتمالا می خواهید
خانمها با کاهش بالای پشته

153
00:07:24,050 --> 00:07:25,009
در موسیقی پاپ، درست است؟

154
00:07:25,009 --> 00:07:26,800
و سپس از درس
ما نیز در حال رفتن به می خواهم

155
00:07:26,800 --> 00:07:29,240
برای بازگشت به ارزش که ما را حذف کنید.

156
00:07:29,240 --> 00:07:32,125
اگر ما در حال اضافه کردن عناصر، ما می خواهیم
برای به دست آوردن عناصر خارج بعد از آن،

157
00:07:32,125 --> 00:07:34,000
ما احتمالا در واقع
می خواهید به آنها را ذخیره بنابراین ما

158
00:07:34,000 --> 00:07:36,490
نه تنها آنها را از حذف
پشته و سپس هیچ چیز با آنها.

159
00:07:36,490 --> 00:07:38,500
به طور کلی اگر ما
هل دادن و ظاهر اینجا

160
00:07:38,500 --> 00:07:41,250
ما می خواهیم برای ذخیره این
اطلاعات در راه معنی دار

161
00:07:41,250 --> 00:07:43,250
و پس از آن باعث نمی شود
حس به آن را فقط دور بیندازید.

162
00:07:43,250 --> 00:07:46,380
بنابراین این تابع باید
احتمالا یک مقدار را به ما بازگرداند.

163
00:07:46,380 --> 00:07:51,040
>> بنابراین این یک اعلان پاپ است
ممکن است مانند وجود دارد در بالا سمت چپ نگاه کنید.

164
00:07:51,040 --> 00:07:53,870
این تابع برمی گرداند
داده ها از ارزش نوع.

165
00:07:53,870 --> 00:07:56,320
باز هم ما با استفاده از اس ام اس
اعداد صحیح در سراسر.

166
00:07:56,320 --> 00:08:01,916
و آن را یک اشاره گر به یک پشته به عنوان پذیرد
بحث تنها آن و یا تنها پارامتر.

167
00:08:01,916 --> 00:08:03,040
پس چه شده است پاپ کاری انجام دهید؟

168
00:08:03,040 --> 00:08:07,990
بیایید می گویند ما می خواهیم به حال
پاپ یک عنصر خارج از بازدید کنندگان.

169
00:08:07,990 --> 00:08:14,000
بنابراین به یاد داشته باشید من گفت که پشته گذشته
در، اولین بار، LIFO ساختمان داده.

170
00:08:14,000 --> 00:08:17,855
کدام عنصر است که به
از پشته حذف شده باشد؟

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
آیا شما حدس می زنم 19؟

173
00:08:24,150 --> 00:08:25,290
از آنجا که شما می شود، راست.

174
00:08:25,290 --> 00:08:28,836
19 آخرین عنصر به اضافه شد
پشته هنگامی که ما عناصر هل دادن در،

175
00:08:28,836 --> 00:08:31,210
و پس از آن را به رفتن به اولین
عنصری است که می شود حذف خواهند شد.

176
00:08:31,210 --> 00:08:34,780
آن را به عنوان اگر ما گفت: 28 و
پس از آن ما 33 در بالای آن قرار داده است،

177
00:08:34,780 --> 00:08:36,659
و ما 19 در بالا از آن قرار داده است.

178
00:08:36,659 --> 00:08:40,650
تنها عنصر ما می توانیم را خاموش 19 است.

179
00:08:40,650 --> 00:08:45,019
>> در حال حاضر در نمودار در اینجا من چه کرده ام
مرتب سازی بر اساس 19 از آرایه حذف شده است.

180
00:08:45,019 --> 00:08:46,810
که در واقع نه
آنچه که ما قصد انجام دهید.

181
00:08:46,810 --> 00:08:48,934
ما فقط در حال رفتن به نوع
از تظاهر آن است وجود ندارد.

182
00:08:48,934 --> 00:08:51,441
هنوز هم وجود دارد در
آن مکان حافظه،

183
00:08:51,441 --> 00:08:54,190
اما ما فقط رفتن به آن را نادیده گرفت
با تغییر بالای پشته ما

184
00:08:54,190 --> 00:08:56,080
از 3 به 2.

185
00:08:56,080 --> 00:08:58,720
بنابراین اگر ما به در حال حاضر فشار
عنصر دیگری را بر روی پشته،

186
00:08:58,720 --> 00:09:00,720
آن را بیش از نوشتن 19.

187
00:09:00,720 --> 00:09:03,990
>> اما اجازه دهید از طریق مشکل نیست
حذف 19 از پشته.

188
00:09:03,990 --> 00:09:05,830
ما فقط می توانید تظاهر آن است وجود ندارد.

189
00:09:05,830 --> 00:09:11,107
برای اهداف از پشته آن را اگر رفته
ما تغییر بالا به 2 به جای 3.

190
00:09:11,107 --> 00:09:12,690
همه حق است، به طوری که تقریبا از آن.

191
00:09:12,690 --> 00:09:15,080
که همه ما باید انجام دهیم
به موسیقی پاپ روی یک عنصر.

192
00:09:15,080 --> 00:09:16,090
اجازه دهید دوباره آن را انجام.

193
00:09:16,090 --> 00:09:18,610
پس من آن را در قرمز مشخص کردم که در اینجا به
نشان می دهد ما در حال ساخت یک تماس دیگر.

194
00:09:18,610 --> 00:09:19,720
ما قصد داریم به انجام همان چیزی.

195
00:09:19,720 --> 00:09:20,803
>> پس چه اتفاقی خواهد افتاد؟

196
00:09:20,803 --> 00:09:23,670
خب، ما در حال رفتن به فروشگاه اینترنتی
33 در X و ما قصد داریم

197
00:09:23,670 --> 00:09:26,217
برای تغییر بالای پشته به 1.

198
00:09:26,217 --> 00:09:29,050
به طوری که اگر ما در حال حاضر به اجرای یک بود
عنصر به پشته که ما در حال

199
00:09:29,050 --> 00:09:31,610
رفتن به انجام در حال حاضر،
چه اتفاقی خواهد افتاد

200
00:09:31,610 --> 00:09:36,367
است ما قصد داریم بازنویسی
آرایه شماره محل 1.

201
00:09:36,367 --> 00:09:38,950
به طوری که 33 که مرتب سازی بر باقی مانده بود
پشت که ما فقط وانمود

202
00:09:38,950 --> 00:09:44,390
وجود ندارد دیگر، ما فقط رفتن
به آن کتک زدن و 40 وجود دارد به جای آن.

203
00:09:44,390 --> 00:09:46,290
و پس از درس،
از آنجایی که ما یک فشار،

204
00:09:46,290 --> 00:09:48,780
ما قصد داریم به افزایش
بالای پشته 1-2

205
00:09:48,780 --> 00:09:50,950
به طوری که اگر ما در حال حاضر اضافه
عنصر دیگری آن را خواهید

206
00:09:50,950 --> 00:09:54,700
رفتن به آرایه شماره محل دو.

207
00:09:54,700 --> 00:09:57,590
>> در حال حاضر لیست های پیوندی دیگر است
راه برای پیاده سازی پشته.

208
00:09:57,590 --> 00:10:01,210
و اگر این تعریف در
صفحه نمایش در اینجا به نظر می رسد برای شما آشنا،

209
00:10:01,210 --> 00:10:04,260
این به دلیل آن به نظر می رسد تقریبا
دقیقا همان است، در واقع،

210
00:10:04,260 --> 00:10:07,790
آن را بسیار است که دقیقا
همان یک لیست تنهایی مرتبط،

211
00:10:07,790 --> 00:10:11,990
اگر شما از بحث ما از فراخوان
تنهایی لیست در یک ویدیو دیگر مرتبط است.

212
00:10:11,990 --> 00:10:15,510
تنها محدودیت این
برای ما به عنوان برنامه نویسان،

213
00:10:15,510 --> 00:10:17,900
ما به اجازه
قرار دادن به طور تصادفی حذف و یا

214
00:10:17,900 --> 00:10:20,620
از لیست تنهایی مرتبط
که ما قبلا تواند انجام دهد.

215
00:10:20,620 --> 00:10:25,820
ما فقط می توانید وارد و در حال حاضر حذف از
جلو یا بالای مرتبط

216
00:10:25,820 --> 00:10:26,320
لیست.

217
00:10:26,320 --> 00:10:28,028
این واقعا تنها
تفاوت است.

218
00:10:28,028 --> 00:10:29,700
این در غیر این صورت یک لیست تنهایی مرتبط.

219
00:10:29,700 --> 00:10:32,060
این تنها محدودیت است
جایگزین در خودمان

220
00:10:32,060 --> 00:10:35,770
به عنوان برنامه نویسان که
آن را تغییر را به یک پشته.

221
00:10:35,770 --> 00:10:39,280
>> قانون اینجا این است که همیشه حفظ
اشاره گر به رئیس یک لیست پیوندی.

222
00:10:39,280 --> 00:10:41,520
این البته به طور کلی
قانون مهم است.

223
00:10:41,520 --> 00:10:44,260
برای تنهایی لیست پیوندی به هر حال شما
تنها نیاز به یک اشاره گر به سر

224
00:10:44,260 --> 00:10:46,160
به منظور که
زنجیره ای قادر به مراجعه

225
00:10:46,160 --> 00:10:48,596
به هر عنصر دیگر
در لیست پیوندی.

226
00:10:48,596 --> 00:10:50,470
اما آن را به خصوص
با یک پشته مهم است.

227
00:10:50,470 --> 00:10:52,386
و بنابراین به طور کلی شما
رفتن به واقع می خواهم

228
00:10:52,386 --> 00:10:54,090
این اشاره گر به یک متغیر جهانی است.

229
00:10:54,090 --> 00:10:56,574
این احتمالا رفتن به
بود حتی ساده تر است که راه.

230
00:10:56,574 --> 00:10:58,240
پس چه آنالوگ فشار و پاپ هستند؟

231
00:10:58,240 --> 00:10:58,740
درست.

232
00:10:58,740 --> 00:11:01,812
بنابراین فشار دادن دوباره اضافه کردن
یک عنصر جدید به پشته.

233
00:11:01,812 --> 00:11:03,770
در یک لیست پیوندی که
معنی است که ما در حال رفتن به

234
00:11:03,770 --> 00:11:07,770
برای ایجاد یک گره جدید است که ما
رفتن به اضافه کردن به لیست پیوندی،

235
00:11:07,770 --> 00:11:10,500
و سپس مراحل دقیق دنبال
که ما پیش از این ذکر را

236
00:11:10,500 --> 00:11:16,050
در لیست تنهایی مرتبط به آن اضافه کنید
زنجیره ای بدون شکستن زنجیره ای

237
00:11:16,050 --> 00:11:18,900
و از دست دادن و یا هر یتیم
عناصر از لیست پیوندی.

238
00:11:18,900 --> 00:11:21,820
و اساسا این که
لکه کوچک از متن خلاصه شده است.

239
00:11:21,820 --> 00:11:23,740
و اجازه دهید یک نگاهی از
در آن را به عنوان یک نمودار.

240
00:11:23,740 --> 00:11:24,823
>> بنابراین در اینجا لیست پیوندی ما است.

241
00:11:24,823 --> 00:11:26,620
این به صورت همزمان شامل چهار عنصر است.

242
00:11:26,620 --> 00:11:30,420
و کاملا تر در اینجا ما
پشته حاوی چهار عنصر است.

243
00:11:30,420 --> 00:11:36,030
و اجازه دهید بگویم ما اکنون می خواهیم
فشار یک آیتم جدید بر روی این پشته.

244
00:11:36,030 --> 00:11:39,792
و ما می خواهیم به فشار یک جدید
مورد که ارزش داده 12 است.

245
00:11:39,792 --> 00:11:41,000
خب چه می خواهیم کاری انجام دهید؟

246
00:11:41,000 --> 00:11:43,420
خب اول ما قصد داریم به
فضای از malloc، به صورت پویا

247
00:11:43,420 --> 00:11:45,411
اختصاص فضا برای یک گره جدید.

248
00:11:45,411 --> 00:11:48,160
و البته بلافاصله پس از
ما را یک به malloc ما همیشه

249
00:11:48,160 --> 00:11:52,989
مطمئن شوید که به برای NULL را بررسی کنید،
چرا که اگر ما مقدار null کردم

250
00:11:52,989 --> 00:11:54,280
بود به نوعی از مشکل وجود دارد.

251
00:11:54,280 --> 00:11:57,570
ما برای ارجاع دوباره به که تهی می خواهید
اشاره گر و یا شما یک گسل SEG رنج می برند.

252
00:11:57,570 --> 00:11:58,510
این خوب نیست.

253
00:11:58,510 --> 00:11:59,760
بنابراین ما از گره malloced است.

254
00:11:59,760 --> 00:12:01,260
ما باید فرض کنیم ما موفقیت در اینجا بود.

255
00:12:01,260 --> 00:12:06,090
ما در حال رفتن به قرار دادن 12 به
فیلد داده از آن گره.

256
00:12:06,090 --> 00:12:11,570
در حال حاضر شما را به یاد که از اشاره گر ما
حرکت بعدی بنابراین ما شکستن زنجیره ای نیست؟

257
00:12:11,570 --> 00:12:15,100
ما یک زن و شوهر از گزینه اینجا اما
تنها کسی است که برای رفتن به امن

258
00:12:15,100 --> 00:12:19,330
این است که مجموعه اخبار اشاره گر به
نقطه به نقطه سر قدیمی از لیست

259
00:12:19,330 --> 00:12:21,360
و یا چه به زودی خواهد بود
رئیس قدیمی از لیست.

260
00:12:21,360 --> 00:12:23,610
و حالا که همه ما
عناصر با هم زنجیر،

261
00:12:23,610 --> 00:12:27,370
ما فقط می توانید لیست حرکت به نقطه
به همان محل می کند که جدید است.

262
00:12:27,370 --> 00:12:33,550
و ما در حال حاضر به طور موثر تحت فشار قرار دادند
عنصر جدید را بر روی جلو از پشته.

263
00:12:33,550 --> 00:12:36,420
>> به موسیقی پاپ ما فقط می خواهید
حذف کنید که عنصر اول.

264
00:12:36,420 --> 00:12:38,150
و بنابراین اساسا چه
ما باید انجام دهیم در اینجا،

265
00:12:38,150 --> 00:12:40,050
همچنین ما باید برای پیدا کردن عنصر دوم.

266
00:12:40,050 --> 00:12:43,540
در نهایت تبدیل خواهد شد که جدید
سر پس از ما یکی از اولین حذف کنید.

267
00:12:43,540 --> 00:12:47,300
بنابراین ما فقط نیاز به از شروع
آغاز، حرکت یک جلو.

268
00:12:47,300 --> 00:12:50,340
هنگامی که ما تا رو نگه دارید در یکی
رو به جلو که در آن ما در حال حاضر

269
00:12:50,340 --> 00:12:53,850
ما می توانید با خیال راحت یکی از اولین حذف
و پس از آن ما فقط می توانید حرکت سر

270
00:12:53,850 --> 00:12:57,150
به نقطه را به آنچه بود
دوره دوم و پس از آن در حال حاضر

271
00:12:57,150 --> 00:12:59,170
اولین بعد از آن
گره حذف شده است.

272
00:12:59,170 --> 00:13:01,160
>> پس دوباره، گرفتن یک نگاه
در آن را به عنوان یک نمودار ما

273
00:13:01,160 --> 00:13:05,022
می خواهید به حال پاپ
عنصر از این پشته.

274
00:13:05,022 --> 00:13:05,730
پس چه کار کنیم؟

275
00:13:05,730 --> 00:13:08,188
ما در حال رفتن به اولین ایجاد
یک اشاره گر است که رفتن

276
00:13:08,188 --> 00:13:10,940
به نقطه را به همان نقطه به عنوان رئیس.

277
00:13:10,940 --> 00:13:13,790
ما قصد داریم آن را به حرکت یک موقعیت
رو به جلو با گفتن برابر TRAV

278
00:13:13,790 --> 00:13:17,510
TRAV بعدی به عنوان مثال،
به یک اشاره گر TRAV پیشبرد

279
00:13:17,510 --> 00:13:19,324
موقعیت رو به جلو.

280
00:13:19,324 --> 00:13:21,240
حالا که ما باید یک
نگه بر روی عنصر اول

281
00:13:21,240 --> 00:13:24,573
از طریق اشاره گر به نام لیست، و
عنصر دوم از طریق یک اشاره گر به نام

282
00:13:24,573 --> 00:13:28,692
TRAV، ما با خیال راحت می توانید حذف کنید که
اولین عنصر از پشته

283
00:13:28,692 --> 00:13:30,650
بدون از دست دادن بقیه
از زنجیره ای چون ما

284
00:13:30,650 --> 00:13:32,358
یک راه برای مراجعه
به عنصر دوم

285
00:13:32,358 --> 00:13:34,780
رو به جلو از طریق
اشاره گر TRAV نامیده می شود.

286
00:13:34,780 --> 00:13:37,100
>> بنابراین در حال حاضر ما می توانیم آن گره آزاد.

287
00:13:37,100 --> 00:13:38,404
ما می توانید لیست آزاد.

288
00:13:38,404 --> 00:13:41,320
و پس از آن که همه ما نیاز به انجام اکنون
انتقال لیست به نقطه به همان محل

289
00:13:41,320 --> 00:13:44,482
که TRAV کند، و ما مرتب سازی بر هستید از تماس
که در آن ما آغاز شده قبل از ما تحت فشار قرار دادند 12

290
00:13:44,482 --> 00:13:45,690
در وهله اول، سمت راست.

291
00:13:45,690 --> 00:13:46,940
این دقیقا همان جایی است که ما بود.

292
00:13:46,940 --> 00:13:48,840
ما این چهار عنصر پشته بود.

293
00:13:48,840 --> 00:13:49,690
ما یک پنجم اضافه شده است.

294
00:13:49,690 --> 00:13:51,910
ما تحت فشار قرار دادند یک پنجم
عنصر در، و سپس ما

295
00:13:51,910 --> 00:13:55,980
ظهور که اخیرا
اضافه شدن عنصر پشت کردن.

296
00:13:55,980 --> 00:13:58,816
>> این واقعا بسیار
همه این است که پشته وجود دارد.

297
00:13:58,816 --> 00:14:00,190
شما می توانید آنها را به عنوان آرایه پیاده سازی.

298
00:14:00,190 --> 00:14:01,815
شما می توانید آنها را به عنوان لیست های پیوندی پیاده سازی.

299
00:14:01,815 --> 00:14:04,810
وجود دارد، البته، دیگر
راه هایی برای پیاده سازی آنها و همچنین.

300
00:14:04,810 --> 00:14:09,060
اساسا به همین دلیل ما استفاده
پشته است برای حفظ داده ها در چنین راهی

301
00:14:09,060 --> 00:14:12,090
که اخیرا اضافه شده
عنصر اولین چیزی که ما هستیم

302
00:14:12,090 --> 00:14:14,980
رفتن به می خواهم به عقب بر گردیم.

303
00:14:14,980 --> 00:14:17,900
من داگ لوید هستم، این CS50 است.

304
00:14:17,900 --> 00:14:19,926