スタックの実装と応用
push/pop/peekを備えたスタックを実装し、valid-parentheses、min-stack、逆ポーランド記法の評価を解きます。
「スタックの実装と応用」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
スタックデータ構造
スタックは、後入れ先出し（LIFO）のデータ構造です。最後に push された要素が、最初に pop されます。皿を積み重ねた状態をイメージしてください。追加や削除は一番上からしかできません。基本操作は、push（一番上に追加）、pop（一番上から削除）、peek（削除せずに一番上を読み取る）です。適切に実装されたスタックでは、これら3つはすべて O(1) です。
Python では、リストがスタックとしてそのまま使えます。append が push、pop() が pop、[-1] が peek に相当します。
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Push、Pop、Peek、isEmpty を備えた Stack クラス
リストをクラスでラップすると、より明確なインターフェースを提供でき、insert や一番上以外の位置へのインデックスアクセスなど、スタックではない操作を誤って使うことを防げます。これは、面接官から「スタックをゼロから実装してください」と求められたときに期待される実装です。
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2有効な括弧（LeetCode 20）
LeetCode 20「有効な括弧」：括弧で構成された文字列が正しく対応しているかを判定します。開き括弧が現れるたびに push します。閉じ括弧が現れたら、スタックの一番上が対応する開き括弧か確認します。対応していない場合、またはスタックが空の場合は False を返します。最後にスタックが空なら、文字列は有効です。これは、コーディング面接におけるスタックの最も基本的な応用です。
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # False最小値スタック（LeetCode 155）
LeetCode 155「最小値スタック」：push、pop、peek、getMin をすべて O(1) でサポートするスタックを設計します。ポイントは、各時点での最小値を記録する2つ目のスタックを維持することです。push するときは、新しい値が現在の最小値以下（<=）の場合、または最小値スタックが空の場合に、その値も最小値スタックへ push します。pop するときは、取り出した値が現在の最小値と等しい場合に、最小値スタックからも pop します。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2逆ポーランド記法の評価
LeetCode 150「逆ポーランド記法の評価」（後置記法）：オペランドを push し、演算子が現れたら2つのオペランドを pop して演算を行い、結果を push します。減算と除算では順序が重要です。最初に pop した値が右オペランド、2番目に pop した値が左オペランドです。
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22文字列のデコード（LeetCode 394）
LeetCode 394「文字列のデコード」：3[a2[c]] のようなエンコードされた文字列を、accaccacc に展開します。2つのスタックを使い、1つは繰り返し回数、もう1つは蓄積した文字列を管理します。数字が現れたら、完全な数値を組み立てます。[ が現れたら、現在の文字列と回数を push します。] が現れたら、それらを pop して現在の部分文字列を繰り返します。文字が現れたら、現在の文字列に追加します。
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Daily Temperatures（単調スタックのプレビュー）
LeetCode 739「Daily Temperatures」：各日について、より高い気温になるまで何日かかるかを求めます。総当たり法では O(n²) です。スタックを使う場合は、気温を走査し、各日について、その日の気温より低い気温を持つスタック内の要素（各日のインデックス）をすべて pop します。取り出した日の答えは、(今日 - 取り出した日) です。現在の日を push します。残った要素は、より高い気温の日が見つからなかったため、答えは 0 です。
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]DFS走査にスタックを使う
再帰的な DFS の呼び出しスタックは明示的なスタックに置き換えることができ、アルゴリズムを反復的に実装できます。ルートを push し、スタックが空でない間、ノードを pop して処理し、その子ノードを push します（左から右へ処理する場合は右の子を左の子より先に push します）。この反復的な DFS は再帰的な DFS と動作が同じですが、深い木で Python の再帰制限に達することを避けられます。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]時間計算量と空間計算量
スタックのすべての操作（push、pop、peek、isEmpty）は償却 O(1)です。n 個の要素を持つスタックの構築には O(n) かかります。すべての要素が格納される最悪の場合、空間計算量は O(n) です。単調スタックを使う問題では、各要素が push される回数も pop される回数も高々1回なので、すべての反復を通した全体の計算量はO(n)です。素朴に外側のループだけを見ると O(n²) に思えるかもしれませんが、実際はそうではありません。
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000ヒストグラム内の最大長方形（プレビュー）
LeetCode 84「ヒストグラム内の最大長方形」は、典型的なスタック問題の中でも最も難しいものです。各棒を基準にできる長方形は、左側ではより短い棒が見つかるまで、右側でもより短い棒が見つかるまで広がります。単調スタックで、高さが昇順になるように棒のインデックスを管理します。より短い棒が現れたら pop し、取り出した棒の高さを使って長方形の面積を計算します。スタックにより、pop 1回あたり O(1) で左右の境界を求められます。
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4スタック問題への面接戦略
スタック問題は、「内側から外側へ処理する」や「次に現れるより大きい要素・小さい要素を見つける」といった形に姿を変えて出題されることがよくあります。スタックが役立つ可能性を示すサインは、直前に見た要素が必要な場合、ペア（括弧やタグ）を対応付ける場合、または素朴な方法では O(n²) の二重ループが必要な問題を O(n) で解きたい場合です。特に単調スタックを使うと、「すべての要素について最も近い、より大きい要素・小さい要素を見つける」処理を O(n²) から O(n) にできます。
面接では、スタックの不変条件を明確に説明してください。「高さが降順になるように、インデックスのスタックを維持します」と述べます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Python のリストは O(1) の push/pop/peek を実装しているため、スタックとして理想的であること、有効な括弧と最小値スタックが、スタックに関する面接問題の代表例であること、そして単調スタックは各要素を高々1回ずつ push と pop することで、次に大きい要素を求める問題を O(n) で解けることを学びました。次は Python の deque を使ってキューを作り、スライディングウィンドウの最大値を求めます。
よくある質問
「スタックの実装と応用」レッスンは無料ですか？
はい。「スタックの実装と応用」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「スタックの実装と応用」で何を学びますか？
push/pop/peekを備えたスタックを実装し、valid-parentheses、min-stack、逆ポーランド記法の評価を解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「スタックの実装と応用」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。