回答編集履歴
1
逆にすればいいか
answer
CHANGED
|
@@ -1,11 +1,17 @@
|
|
|
1
1
|
リストって双方向リストじゃなくて単方向リストなのね。
|
|
2
2
|
|
|
3
|
-
stackの実現には
|
|
3
|
+
stackの実現には通常
|
|
4
4
|
|
|
5
5
|
- 末尾への追加
|
|
6
6
|
- 末尾の削除
|
|
7
7
|
- 末尾の取得
|
|
8
8
|
|
|
9
|
-
が必要です。
|
|
9
|
+
が必要です。が、単方向リストだと、任意の要素へのアクセスには`O(n)`のコストが掛かってしまいます。言い換えるとstack操作をなにかしようとするたびに要素数Nに比例するコストが掛かるということです。
|
|
10
10
|
|
|
11
|
+
なので発想を切り替えて
|
|
12
|
+
|
|
13
|
+
- 先頭要素の前に追加(stackに積む操作)
|
|
14
|
+
- 先頭要素の削除(stackを取る操作)
|
|
15
|
+
- 先頭要素の取得(stackを取る操作)
|
|
16
|
+
|
|
11
|
-
|
|
17
|
+
で実現させましょう。これなら`O(1)`です。
|