スタックとキューは、プログラミングコンセプトの誕生時から使用される最も古典的なデータ構造の1つであり、スタックはほとんどのアプリケーションの作成時に使用されるデータ構造です.
スタックはLIFOとして処理され、キューはFIFOとして処理される.
Pythonではスタックタイプは提供されませんが、リストは実際にスタックのすべての演算をサポートします.Qも同じです.リストは、キュー内のすべての演算をサポートします.ただし、リストは動的に配置されているため、キュー演算を実行する効率は高くありません.そのため、キューのためにDequeという独立したデータ型を使用すると、パフォーマンスが向上します.しかし、パフォーマンスを得たくない場合は、リストはスタックとキューのすべての演算をサポートするので、実際にはリストをうまく使うだけで十分です.

スタック

スタックは、次の2つの主要な演算をサポートする要素の集合の抽象データ型です.

push():要素をコレクションに追加します.

pop():削除されていない最近挿入された要素を削除します.

質問です。

有効なかっこ-かっこの入力値が正しいかどうかを決定します.
入力

-()[]{}
-{{]

出力
-true
-false

典型的な積み重ね問題は、基本的な仕事をチェックする良い問題です.(,{,[スタックをプッシュ],},]の場合、スタックでポップアップされた結果がマッピングテーブルの結果と一致することを確認します.ポップアップで結果が一致しない場合は、カットバックを実行できます.

stack = []
table = {
    ')':'(',
    '}':'{',
    ']':'['
}
...
    if char not in table:
        stack.append(char)
    elif not stack or table[char] != stack.pop():
        return False

ここでstackは簡単なPython動的配列実装リストを用いた.Python listはスタック演算プッシュとpop操作O(1)を用いるため,性能に大きな問題はない.現在、実際に運転するためには、異常処理が必要です.以下の例外処理が可能です.

    elif not stack or table[char] != stack.pop():
        return False
return len(stack) == 0

このコードでは、ポップアップ結果が一致しているかどうかを確認するとともに、スタックが空であるかどうかを確認し、True、Falseであるかどうかを確認します.このような例外処理を含まなければならない.コード全体を以下に示します.

    def isValid(self, s: str) -> bool:
        stack = []
        table = {
            ')':'(',
            '}':'{',
            ']':'['
        }
        
        for char in s:
            if char not in table:
                stack.append(char)
            elif not stack or table[char] != stack.pop():
                return False
        return len(stack) == 0

質問です。

毎日温度-毎日の華氏温度計Tを入力し、より暖かい天気のために数日待つ必要があると印刷します.
入力

-[73,74,75,71,69,72,76,73]

出力
-[1, 1, 4, 2, 1, 1, 0, 0]

現在のインデックスをスタックに積み上げ続け、以前より上昇したポイントで現在の温度とスタックに積み上げられたインデックスポイントの温度差を比較します.さらに高い場合は、スタック内の値をpop()として次のようにして取り、スタック内の現在のインデックスとスタック内のインデックスの違いを正しい処理とします.

while stack and cur > temperatures[stack[-1]]:
    last = stack.pop()
    answer[last] = i - last
stack.append(i)

また、答えのデフォルト値は0です.より高い温度がないとスタックが空にならない場合、解単インデックスは存在しません.つまり、問題で要求される解単インデックスはゼロに維持されます.この解答のすべてのコードは以下の通りです.

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        stack = []
        for i, cur in enumerate(temperatures):
            #현재 온도가 스택 값보다 높다면 정답처리
            while stack and cur > temperatures[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)
        return answer

キュー

キューは、シーケンスの一端にエンティティを追加し、他端に削除できるエンティティの集合です.
スタックと比較して,FIFO(先入先出)処理のキューの使い道が小さいことにたとえることができる.しかし、スタックに比べて、これは単なる言い方であり、サイズや優先順位キューなど、後で検討するいくつかの変形は、多くの分野で非常に有用である.実際、Pythonのリストはキュー内のすべての演算をサポートするため、そのまま使用する必要はありませんが、より良い性能のために、O(1)で後で表示する双方向挿入と削除機能を使用することが望ましいです.

質問です。

**キューを使用したスタックの実装-計算をサポートするスタックをキューを使用して実装します.
push(x):要素xをスタックに挿入します.
pop():スタック内の最初の要素を削除します.
top():スタックの最初の要素を取得します.
Empty():スタックが空であるかどうかを返します.
Pythonのリストや要約はスタックやキューのすべての機能を提供するため,この問題は本来キューADTには存在しないが,Pythonのデータ型サポート機能を用いることで非常に容易に解決できる.しかし,ここでは,問題の意図に応じてキューFIFOに対応する演算のみを用いて実現する.まずQの宣言はDecro.

self.q = collections.deque()

キューはDeckとして宣言されていますが、問題の意図に合致するようにキューの演算のみが使用されます.push()のみの場合は複雑ですが、次の要素を挿入した後、挿入したばかりの要素を一番前に置いて、要素全体を並べ替えます.

self.q.append(x)
for _ in range(len(self.q) - 1):
	self.q.append(self.q.popleft())

これにより、キューから一番前の要素をドラッグすると、スタックのように最初に挿入される要素が表示されます.もちろん,要素を挿入すると時間的複雑度がO(n)となるため効率はやや低いが,スタックをキューとして実現することは難しくない.コード全体を以下に示します.

import collections
class Mystack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        #요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0