Python Language => スタック

前書き

スタックは、ラスト・イン・ファーストアウト（LIFO）原理に従って挿入および除去されるオブジェクトのコンテナです。プッシュダウンスタックでは、アイテムをスタックにプッシュし、スタックからアイテムをポップするという 2つの操作だけが許可されます 。スタックは、制限されたアクセスデータ構造です。 要素は、スタックの最上部でのみ追加または削除できます 。スタックの構造的定義は次のとおりです。スタックは空であるか、スタックで構成され、スタックはスタックで構成されます。

構文

stack = []＃スタックを作成する
stack.append（object）＃スタックの先頭にオブジェクトを追加する
stack.pop（） - > object＃スタックから一番上のオブジェクトを返し、それも削除します
list [-1] - > object＃一番上のオブジェクトを削除せずにそのオブジェクトを拾い読みします

備考

ウィキペディアから：

コンピュータサイエンスでは、 スタックは、要素をコレクションに追加するpushと 、まだ削除されていない最も最近追加された要素を削除するpopの 2つの主要な操作を持つ、要素のコレクションとして機能する抽象データ型です。

それらの要素がアクセスされる方法により、スタックはラスト・イン・ファーストアウト （ LIFO ） スタックとも呼ばれます。

Pythonでは、リストをスタックとして使用し、 append()をpushおよびpop()としてpop操作として使用できます。両方の操作は一定時間O（1）で実行されます。

Pythonのdequeデータ構造は、スタックとしても使用できます。デキューはリストと比較して、 dequeから一定の時間の複雑さでプッシュ操作とポップ操作を可能にします。

Listオブジェクトを使用したStackクラスの作成

listオブジェクトを使用すると、スタックが空であるかどうかを調べたり確認したりするヘルパーメソッドを使って、完全に機能するジェネリックスタックを作成できます。使用のための公式のPythonドキュメントチェックlistとしてStack こちらを。

#define a stack class
class Stack:
    def __init__(self):
        self.items = []
    
    #method to check the stack is empty or not
    def isEmpty(self):
        return self.items == []
    
    #method for pushing an item 
    def push(self, item):
        self.items.append(item)

    #method for popping an item 
    def pop(self):
        return self.items.pop()
    
    #check what item is on top of the stack without removing it
    def peek(self):
        return self.items[-1]

    #method to get the size
    def size(self):
        return len(self.items)

    #to view the entire stack
    def fullStack(self):
        return self.items

実行例：

stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())

出力：

Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False

括弧の解析

多くの場合、スタックは解析に使用されます。単純な解析作業は、カッコの文字列が一致しているかどうかを確認することです。

たとえば、文字列([])は、外側と内側の括弧がペアを形成するため、一致しています。 ()<>)は一致しません。最後にはパートナーがないためです) 。 ([)]もマッチしません。なぜなら、ペアは完全に他のペアの内側か外側でなければならないからです。

def checkParenth(str):
    stack = Stack()
    pushChars, popChars = "<({[", ">)}]"
    for c in str:
        if c in pushChars:
            stack.push(c)
        elif c in popChars:
            if stack.isEmpty():
                return False
            else:
                stackTop = stack.pop()
                # Checks to see whether the opening bracket matches the closing one
                balancingBracket = pushChars[popChars.index(c)]
                if stackTop != balancingBracket:
                    return False
        else:
            return False

    return not stack.isEmpty()

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

Python Language
スタック

サーチ…

前書き

構文

備考

Listオブジェクトを使用したStackクラスの作成

括弧の解析