スタック

スタックはアルゴリズムでよく使われる代表的なデータ構造の一つです。最後に追加した要素から先に取り出すという仕組みになっており、まるでお皿が積み重なっている様子をイメージすると分かりやすいです。一番上にある皿を取り除かない限り、その下にある皿は取り出せません。

スタックはさまざまな場面で利用できます。たとえばウェブブラウザでページを開き、「戻る」ボタンをクリックすると前のページに戻れますが、これはスタック構造にページ履歴を保存しているイメージです。「戻る」を押すたびにスタックの一番上にあるページが取り除かれ、その下にあるページが表示されるという仕組みになっています。

このスタックをPythonのようなプログラミング言語で実装する方法はいくつかあります。

list を使う方法 - リストの末尾をスタックのトップとみなし、追加は append 、削除は pop 、要素の取得は [-1] を利用します。

collections の deque を使う方法 - 両端からの要素の追加・削除をサポートしています。

queue の LifoQueue を使う方法 - 「最後に入れたものが最初に出る」というスタックの定義に沿ったキューです。

from queue import LifoQueue
stack = LifoQueue()

# プッシュ
stack.put(1)
stack.put(2)
stack.put(3)

# ポップ
print(stack.get())      # 3が表示される
print(stack.get())      # 2が表示される

# 先頭要素の確認 (peek)
print(stack.queue[-1])  # 1が表示される
print(stack.empty())    # 空かどうかの確認 -> Falseが表示される

# list を使う方法
stack = []

# プッシュ
stack.append(1)
stack.append(2)
stack.append(3)

# ポップ
print(stack.pop())      # 3が表示される
print(stack.pop())      # 2が表示される

# 先頭要素の確認 (peek)
print(stack[-1])        # 1が表示される
print(len(stack) == 0)  # 空かどうかの確認 -> Falseが表示される

チャレンジ: 括弧列が正しいかどうか判定する

数学的な式などで登場する括弧列（例: (()())）が与えられたとき、それが正しいかどうかを判定してください。ここで「正しい」とは、すべての開き括弧に対して正しい閉じ括弧が対応しており、余分な開き括弧や閉じ括弧がない状態を指します。

入力 (Input)

入力はただ1行で、括弧列が含まれる b (1 ≤ |b| ≤ ) が与えられます。

出力 (Output)

もし括弧列が正しければ Yes、そうでなければ No を出力してください。

例 (Examples)

Input	Output
()()	Yes
())()(	No
((()())())	Yes

チャレンジ: 括弧列が正しいかどうか判定する

入力 (Input)

出力 (Output)

例 (Examples)

Constraints

To check your solution you need to sign in

Sign in to continue