25. Design Circular Queue

道しるべ

の円形クラブをデザインします.

1.配列で解く

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0
        
        
    #enQueue(): rear포인터 이동
    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
    
    #deQueue(): front 포인터 이동
    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:
        return -1 if self.q[self.p1] is None else self.q[self.p1]
        

    def Rear(self) -> int:
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]
        #인덱스이기에 -1을 해준다.

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

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


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

円形キューを実装する方法はいくつかありますが、ここでは最も一般的な方法アレイを使用して実装します.

のレイアウトから見ると,空間再利用のプロトタイプ優位性も体現できる.

まず初期化すると、キューサイズkが入力値として受け入れられる.

kの値はもちろん最大長のmaxlenです.

前のポインタはp 1,後のポインタはp 2とする.

の両方の初期値は0です.

次に,要素を挿入するenQueue()演算を実現する.

後ポインタp 2の位置に値を入力し、ポインタを1つ前に移動させる.

ただし、母チューリップ(残り)の全長を用いて演算を行い、ポインタの位置が全長からずれないようにします.

backポインタの位置がNoneでない場合はfalseを返します.他の要素が存在する空間がいっぱいまたは正常ではないためです.

この実装deQueue()演算が行われた.

この問題で要求されるDeQueue()演算は、要素を取り出さずに削除のみを実行するように定義されます.

キューから要素を取り出します.問題の例に示すように、前はFront()で、後ろはRear()で、異なる演算として定義されます.

Noneをfrontポインタp 1の位置に入れて削除し、ポインタを1つ前に移動します.
次に

であり,同様にモジュール化演算であり,最大長を超えない.

『Introtecoon to Algorithms』という本やリスト9-1で整理されているワシントン州立大学課程の資料首都コードを見ると、同じプロトタイプキューを実現すると同時に、DeQueue()は要素を削除するだけでなく、抽出も実行することが明らかになった.

Enqueue(Q,x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
        
    else
        Q.tail = Q.tail + 1
        
Dequeue(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
        
    else 
        Q.head = Q.head + 1
        
    return x
 

整理

後、enQueue()移動後ポインタ、Decue移動前ポインタ.