このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
ADTとは何か
- 抽象データ型 (ADT) は、データの集合とそれに対する操作のセットです。
- 内部構造は無視して、操作を使用します。
- スタック、キュー、連結リスト はすべてADTです。
ス塔はLIFOである
- スタックは Last In, First Out (LIFO) です。
- 最後に追加したアイテムが最初に除かれます。
- 皿の山を想像してください:一番上の皿を先に取り出します。
リストを用いたpushとpop
- Pythonのリストを使ってスタックを構築できます。
- push =
stack.append(x)— 末尾(トップ)に追加します。 - pop =
stack.pop()— 末尾(トップ)を削除して返します。
English
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peekとempty
- 削除せずにトップを確認する:
stack[-1]。 len(stack) == 0のとき、スタックは空です。- 空のスタックからpopするとエラーになるため、事前に確認する必要があります。
English
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
Cambridge擬似コードにおける表現
- 試験では、配列と
topポインタ(インデックス)を使ってスタックを構築します。
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
よくあるミス
- スタックは最後加入・最初除去です:トップにpushし、トップからpopします。
- popする前に空でないことを確認します。
あなたも試してみよう
- リストをスタックとして使用します(
appendでpush、popで除去)。 - 回答を確認 を押してコードを試してください。
探索
スタックはLIFOである
スタックは片側でのみpushとpopを行う——最後に入れたものが最初に出る(後入れ先出し)。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
空のスタックから始める。Push 1、次に 2、次に 3。その後 pop を一度行い、取り除かれた値を top に格納する。(top は 3 であるべきで、スタックは [1, 2] であるべきです。)
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
スタックを使ってリスト items を逆転させる。すべての要素をスタックにpushし、すべてpopして result に格納する。(result は [3, 2, 1] になるべき。)
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
top(stack) を記述し、トップのアイテム(最後に入ったもの)を取り出して返回するが、スタックからは取り除かない。スタックが空の場合は None を返回する。
実行ボタンをクリックして出力を確認してください。