この記事では、Pythonを使用して2つのスタックが等しいかどうかをチェックするためのさまざまなアプローチについて説明します。
スタックって何？
Python のスタックは LIFO の原理で動作する線形データ構造です。
LIFO の原則によると、スタックの最後に挿入された要素は最初に削除/アクセスされます。
これが Last In First Out と呼ばれる所以です。
これは、スタックに対するさまざまな操作は、一方向にしか行えないことを意味します。
スタックは Python を含むどのようなプログラミング言語でも実装することができます。
Python では、スタックはリスト、デク、そして LifoQueue を使って実装することができます。
簡単のために、ここでは Python のリストを使ってスタックを実装することにします。
この記事もチェック：Pythonの双方向連結リストの実装方法を解説する
Python スタックの特性
- スタックは単方向性です。つまり、スタックの要素はその一端からのみ挿入または削除できます。
- スタックは、スタックの最後の要素を指すトップポインタを保持します。
- スタックの (i) 番目の要素にアクセスするには、最後の (N-i) 番目の要素を削除する必要があります。
- スタックは、オーバーフロー条件を持たない動的なものと、オーバーフロー条件を持つ静的なものがあります。
Pythonで2つのスタックの等価性をチェックする
2 つのスタックが与えられて、2 つのスタックが同じかどうかをチェックする必要があります。
2 つのスタックは、同じ値で同じ数の要素を持ち、同じ順序またはシーケンスであるときのみ、等しいと呼ばれます。
stack1 = [1, 5, 7, 9]stack2 = [1, 5, 7, 9](stack1 & stack2) are the same.stack3 = [9, 5, 7, 1](stack1 & stack3) and (stack2 & stack3) are not the same. |
方法1：2つのスタックの先頭の要素を比較し、ポップする
Pythonで、与えられた2つのスタックの等質性をチェックする方法1のアルゴリズムを見てみましょう。
-
- まず、checker 変数を作成し、True に設定します（最初は、両方のスタックが等しいと仮定します）。
-
- 両方のスタックの大きさを比較し、等しくない場合は checker 変数を False に設定し、制御を返します。
-
- 一方、両方のスタックの先頭要素を比較します。もし等しければ、両方のスタックからそれらをポップします。
-
- スタックの先頭要素が等しくない場合、checker 変数を False に設定し、コントロールを返します。
-
- 両方のスタックが空になるまで、つまりスタックの要素がすべてポップアウトされるまで、ステップ 3 と 4 を繰り返します。
- 最後に、ステップ 1 で定義したチェッカー変数の値を確認します。それが True の場合、2 つのスタックが等しいことを意味し、それ以外の場合は等しくない (または不等) ことを意味します。
上記のアルゴリズムをPythonのコードで実装してみましょう。
# Define a function in Python# To check if the two stacks# Equal or notdef equal_stacks(s1, s2):
# Create a checker variable
# And initialize it with True
val = True
# Check the size of both stacks
# Passed as arguments
if len(s1) != len(s2):
val = False
return val
# Compare the top of each stack
while(len(s1)):
if s1[-1] == s2[-1]:
s1.pop()
s2.pop()
else:
val = False
break
# Return the final value
# Of checker variable val
return val
# Driver Code# Define two stacksstack1 = [8, 15, 7, 11]
stack2 = [8, 15, 9, 11]
# Pass the above two Stacks to equal_stacks() function# And check their equalityif equal_stacks(stack1, stack2):
print("Two stacks are equal!")
else:
print("Two stacks are not equal!!")
# Print the contents of both the stacks# After their comparisonprint(f')
print(f')
|
結果は以下の通りです。
Two stacks are not equal!Stack-1 after comparison: [8, 15, 7] Stack-2 after comparison: [8, 15, 9] |
上の出力では、両方のスタックの内容が比較後に変更されていることがよくわかります。
Methods
おわりに
この記事では、Python で 2 つのスタックの等質性をチェックするさまざまな方法について学びました。
- 最初の方法では、2つのスタックを変更した後に、2つのスタックの等質性をチェックしました。
- 2番目の方法は、2つのスタックを変更せずに、2つのスタックの等質性をチェックするものです。