回答編集履歴
1
逆にすればいいか
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
stackの実現には
|
|
5
|
+
stackの実現には通常
|
|
6
6
|
|
|
7
7
|
|
|
8
8
|
|
|
@@ -14,8 +14,20 @@
|
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
が必要です。
|
|
17
|
+
が必要です。が、単方向リストだと、任意の要素へのアクセスには`O(n)`のコストが掛かってしまいます。言い換えるとstack操作をなにかしようとするたびに要素数Nに比例するコストが掛かるということです。
|
|
18
18
|
|
|
19
19
|
|
|
20
20
|
|
|
21
|
+
なので発想を切り替えて
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
- 先頭要素の前に追加(stackに積む操作)
|
|
26
|
+
|
|
27
|
+
- 先頭要素の削除(stackを取る操作)
|
|
28
|
+
|
|
29
|
+
- 先頭要素の取得(stackを取る操作)
|
|
30
|
+
|
|
31
|
+
|
|
32
|
+
|
|
21
|
-
|
|
33
|
+
で実現させましょう。これなら`O(1)`です。
|