スタックとキュー

読了目安 約3分

LIFO と FIFO の 2 つの取り出し順。removeFirst が O(N) になる罠と括弧の対応判定。

要素を一時的にためる入れ物は、取り出す順番の違いで 2 種類に分かれます。

スタック

スタックは、最後に入れたものを最初に取り出す入れ物です。 この順番を LIFO (Last In, First Out) と呼びます。

Swift では配列がそのままスタックになります。 append で積み、popLast で取り出すだけです。

var stack: [Int] = []
stack.append(1)
stack.append(2)
stack.append(3)
while let top = stack.popLast() {
    print(top)
}

popLast() は末尾の要素を取り除いて返し、空のときは nil を返します。 while let と組み合わせると「空になるまで取り出す」が書けます。 append も popLast も O(1) です。

試してみよう: append する値を増やして、出力が必ず逆順になることを確かめてください。

キュー

キューは、最初に入れたものを最初に取り出す入れ物です。 この順番を FIFO (First In, First Out) と呼びます。

配列には先頭を取り除く removeFirst() がありますが、残りの要素を全部前へ詰め直すため O(N) かかります。 N 回繰り返すと全体で O(N²) になり、大きな入力では間に合いません。

そこで要素は取り除かず、先頭の位置を指す変数 head を進めます。

var queue = [10, 20, 30]
var head = 0
queue.append(40)
while head < queue.count {
    let front = queue[head]
    head += 1
    print(front)
}

取り出した要素は配列に残ったままですが、head より前は二度と見ないので問題ありません。 追加は append、取り出しは head += 1 で、どちらも O(1) です。

スタック 2 本でキューを作る方法もあります。 入力用のスタックに積み、出力用スタックが空になったら全部移し替えると、平均 O(1) で取り出せます。

代表例: 括弧の対応判定

括弧列の対応チェックは、スタックの代表的な使いどころです。

• 開き括弧が来たら、スタックに積む
• 閉じ括弧が来たら、スタックの一番上が対応する開き括弧かを確かめて取り出す
• 最後にスタックが空なら、対応が取れている

let s = "([()])"
var stack = [Character]()
var ok = true
for c in s {
    if c == "(" || c == "[" {
        stack.append(c)
    } else {
        let expected: Character = (c == ")") ? "(" : "["
        if stack.popLast() != expected {
            ok = false
        }
    }
}
if !stack.isEmpty {
    ok = false
}
print(ok ? "Yes" : "No")

閉じ括弧が余ると popLast() が nil を返すので、比較が失敗して ok が false になります。 開き括弧が余ると最後にスタックに残るので、こちらも検出できます。

試してみよう: s を "([)]" に変えて、No になることを確かめてください。

学びどころ

演習

1 行目に (、)、[、] からなる文字列 S が入力されます。 括弧の対応が取れていれば Yes、取れていなければ No を出力してください。

入力例:
([])

出力例:
Yes

let s = readLine()!
var stack = [Character]()
var ok = true
for c in s {
    if c == "(" || c == "[" {
        stack.append(c)
    } else {
        let expected: Character = (c == ")") ? "(" : "["
        if stack.popLast() != expected {
            ok = false
        }
    }
}
if !stack.isEmpty {
    ok = false
}
print(ok ? "Yes" : "No")