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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD：すべての権利、
ので、この点によって、あなたはしています

3
00:00:05,990 --> 00:00:09,020
おそらくかなりおなじみの
配列やリンクリストで

4
00:00:09,020 --> 00:00:10,950
主要な2つはあります
私たちがしたデータ構造

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
静的に宣言場所
そのあなたmemory--メモリ

13
00:00:34,980 --> 00:00:38,730
名前は、名前の変数、ら
これはまた、我々セテラと機能フレーム

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
OK。

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
スタックから削除、本当にあります
2つだけのものは、我々は、スタックで行うことができます。

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
その内では、メンバーが2つ
または構造体のフィールド。

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型のcharまたは他のいくつかのデータ

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
私たちは同じように、スタックSを宣言することができます
我々は、int型のx、またはchar yを行うことができます。

69
00:03:20,970 --> 00:03:22,990
そして、我々は、スタックを言うとき
Sは、よく何が​​起こります

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
これはリコール2つのフィールドが含まれています。

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
だからもう一度、私たちは2つの操作を持っています
私たちが今実行できます。

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
だから我々は我々の2つのパラメータを持っています。

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
して、どこの上部変更
スタックは、それがトップの値をドットだ、です。

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
おそらくsがグローバルに宣言されています。

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を宣言しました
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
我々は数を固執するつもりです
アレイ位置0に28。

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、およびその後の上部を変更私たち
配列の位置番号2であることを積み重ねます。

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
私たちは、アレイ位置2で19を出してあげます
私たちのスタックの先頭を変更

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
>> だから、これはPOPの何宣言です
左上の存在のようになります。

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
さて、私たちは店に行っています
xの33、我々はつもりです

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
配列の位置番号2に入ります。

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
それは、同時に4つの要素が含まれています。

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
我々は、ヌル参照解除したくありません
ポインタまたはあなたはワンセグ障害を被るだろう。

252
00:11:57,570 --> 00:11:58,510
それはよくないのです。

253
00:11:58,510 --> 00:11:59,760
だから我々は、ノードのmallocさました。

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
だから我々はちょうどから開始する必要があります
初めは、1前方に移動します。

268
00:12:47,300 --> 00:12:50,340
我々は1の保留を持ってたら、
どこ現在の前方

269
00:12:50,340 --> 00:12:53,850
私たちが安全に最初のものを削除することができています
し、我々はただ頭を移動することができます

270
00:12:53,850 --> 00:12:57,150
だったものを指すように
今、第2項及び

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ポインタ1を進めう

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
ポインタと呼ばれるリスト、貫通
呼ばれるポインタを介して第2の要素

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
我々は、この4要素のスタックを持っていました。

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