スタックとキュー

次に、スタックとキューの問題を使用してスタックとキューを熟知します.

LeetCode 225.Implement Stack using Queue

キューを使用して、次の操作をサポートするスタックを実装します.

まず自分でこの問題を解いてみます.

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        return self.q.pop()

    def top(self) -> int:
        return self.q[-1]

    def empty(self) -> bool:
        return not self.q

スタック構造ではなくスタック演算のみを考慮して記述した.

ソリューション1 push()の場合はキューを使用して並べ替えます

スタックの演算のみを考慮した場合,今回はスタックの構造を考慮すべきである.まず問題の意図によりQの宣言をDequeとする.その後、キューの演算のみを使用して実装されます.キューはFIFOに相当し、popleft()のみ可能です.popleft()を使用してスタック基準の最後の数を削除する場合は、スタックは逆の形式で格納する必要があります.したがって、スタックのpush()演算には、入力値を先頭に送信する演算が含まれる必要がある.

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

これによりpopleft()でスタックのpop()を実現できる.

class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

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

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

LeetCode 232.Implement Queue using Stacks

スタックを使用して、次の演算をサポートするキューを実装します.

今回も一人で解いてくれました.append()を使用して入力スタックに挿入し、出力スタックに直接ポップアップして転送します.この点では考えが浅く,間違っている.Inputスタックに入れるとoutputスタックに移行し、最終的にはスタックに書き込むことになります.2つのスタックを使用するのによく近いが,2つのスタックの値の移動過程は間違っている.2つのスタックの値遷移関数をそれぞれ実現し,popとpeekの前に呼び出すように記述した.

class MyQueue:

    def __init__(self):
        self.input=[]
        self.output=[]
        
    def shift(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.shift()
        return self.output.pop()

    def peek(self) -> int:
        self.shift()
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

2つのソリューション1スタックを使用

自分の解をヒントにするのとあまり違いません.popの前に、peekにinputスタックからoutputスタックに移行する演算を加え、peekを呼び出してデータを逆方向に移動しpopします.

class MyQueue:

    def __init__(self):
        self.input=[]
        self.output=[]

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return self.input==[] and self.output==[]

LeetCode 622.Design Circular Queue

丸いキューをデザインします.

ソリューション1のソリューショングループを使用して回答

ラウンドキューはキューと同様にFIFO構造を有しているが、前面と背面にはリング構造が連結されている.スペースがいっぱいになると、既存のキューに要素を追加することはできません.deQueue()のために前のスペースが残っていても、そのスペースに要素を追加することはできません.ただし,円形キューは上図のように前面にスペースがあれば前面に丸めて接続して追加することができ,リサイクル可能な構造となっている.
動作原理は二重ポインタに似ている.始点と終点を接続する円形構造を作成し、先端を指すポインタと後方を指すポインタが始点と終点に沿って移動します.EnQueue()は後方に移動し,deQueue()は前方に後方に移動する.enQueue()とdeQueue()が繰り返し続けると、前後が回転します.hundがfrontと同じ位置で出会った場合、円形キューにスペースが残っていないため、スペース不足のエラーが発生します.
円形キューを初期化する場合は、まず円形キューのサイズを受け入れます.そして受け取ったキューの大きさに合わせて配る.入力した円形キューのサイズを最大値に保存し、フロントエンドとバックエンドを表す2つのポインタを0に宣言します.
enQueue()の場合、後方を指すスペースが空の場合、スペースに入力した数字を加え、後方を(後方+1)%maxlenにリフレッシュします.これは、%で円を返すように次のセルに移動することを示します.hundが指すセルがいっぱいになった場合、falseが返されます.
DeQueue()の場合、enQueue()とは反対にfrontが指すセルが空の場合、Falseが返されます.frontが指す格子がいっぱいになった場合、この格子をNoneに更新し、frontを(front+1)%maxlenに更新します.元の円形キューのDeQueue()はクリアされた数を返さなければなりませんが、この問題ではTrueとFalseを返す必要があります.元の円形キューを実装する必要がある場合は、frontが指すセル数を空に保存し、Noneとして保存した数を返すだけです.

class MyCircularQueue:

    def __init__(self, k: int):
        self.q=[None]*k
        self.maxlen=k
        self.p1=0
        self.p2=0

    def enQueue(self, value: int) -> bool:
        if self.q[self.p2] is None:
            self.q[self.p2]=value
            self.p2=(self.p2+1)%self.maxlen
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1]=None
            self.p1=(self.p1+1)%self.maxlen
            return True

    def Front(self) -> int:
        if self.q[self.p1] is None:
            return -1
        return self.q[self.p1]

    def Rear(self) -> int:
        if self.q[self.p2-1] is None:
            return -1
        return self.q[self.p2-1]

    def isEmpty(self) -> bool:
        return self.q[self.p1] is None and self.q[self.p2] is None

    def isFull(self) -> bool:
        return self.p1==self.p2 and self.q[self.p1] is not None