<エンコードテストレベル1>9日-開始

📌 キュー

スタックとともに基本データ構造を担当する큐について説明します.
一般的に、Qはスタックと一緒に勉強します.どうしてかな
前回学스택は後入先出です.큐はこれに対して、先入先出特性を有する資料構造である.

すなわち,挿入データの順にデータを抽出する.

📌 キュー実装

スタックと同様に、キューにも2つの変数が必要です.データ挿入とデータ抽出です.
データを挿入するには、キューがいっぱいであることを確認し、データ抽出はキューが空であることを確認する必要があります.
しかし,Qとスタックは詳細コードの内容においてやや異なる.스택ではtop変数を用いて最後の入力データの原理を表すが、큐は最近挿入されたデータ位置と最も古いデータ位置を記憶する必要がある.
最近挿入するデータの場所を挿入します.
最も古いデータが必要な場所を抽出します.

MAX_QUEUE_SIZE = 5

class Queue:
    def __init__(self):
        self.arr = [None] * MAX_QUEUE_SIZE
        # head : 가장 오래된 데이터의 위치
        # tail : 가장 최근 추가된 데이터의 위치
        self.head = -1
        self.tail = -1

    def is_empty(self):
        if self.head == self.tail:
            return True
        return False

    def is_full(self):
        if self.tail >= MAX_QUEUE_SIZE - 1:
            return True
        return False

    def enqueue(self, item):
        if self.is_full():
            print("큐에 더이상 데이터를 넣을 수 없습니다.")
        else:
            self.tail += 1
            self.arr[self.tail] = item

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
            return None;
        else:
            self.head += 1
            return self.arr[self.head]

queue = Queue()
queue.enqueue("data 1")
queue.enqueue("data 2")
queue.enqueue("data 3")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

--

📌 線形キューの問題

👉 実行コード

enqueue(1);
enqueue(2);
enqueue(3);
enqueue(4);
enqueue(5);

dequeue();
dequeue();
dequeue();
dequeue();
dequeue();

enqueue(1);
enqueue(2);
enqueue(3);

👉 実行結果

큐에 더이상 데이터를 넣을 수 없습니다.
큐에 더이상 데이터를 넣을 수 없습니다.
큐에 더이상 데이터를 넣을 수 없습니다.

明らかに、enqueueは5回実行され、dequeueは5回実行されたので、キューは空ですが、enqueueを再実行すると、文が出力され、キューにデータを入れられないことを示します.





キューを円形に作成すると、データを挿入しても元の位置に戻るので、キューが満たされていない限り、データを挿入し続けることができます.
この丸いキューは원형 큐と呼ばれています.

📌 えんけいキュー

원형 큐はQを原型として作成された資料構造である.
head、tailが配列の最後のインデックスに到達すると、配列の最初の部分に戻り、キューが円形のように見えます.
その2つの奥Qの大きさは5であると仮定する.
では、tailとheadの値が4を超えるとエラーが発生します.
キューを構成する配列には0から4までのインデックスしか存在しないからです.
では**tailは0から4まで変わらず、5で0を返します.모듈 연산자 (%)を使用します.
trail、headをキューのサイズで割って変更します.

📌 循環キューの実装

MAX_QUEUE_SIZE = 5

class Queue:
    def __init__(self):
        self.arr = [None] * MAX_QUEUE_SIZE
        # head : 가장 오래된 데이터의 위치
        # tail : 가장 최근 추가된 데이터의 위치
        self.head = 0
        self.tail = 0

    def is_empty(self):
        if self.head == self.tail:
            return True
        return False

    def is_full(self):
        if (self.tail + 1) % MAX_QUEUE_SIZE == self.head:
            return True
        return False

    def enqueue(self, item):
        if self.is_full():
            print("큐에 더이상 데이터를 넣을 수 없습니다.")
        else:
            self.tail = (self.tail + 1) % MAX_QUEUE_SIZE
            self.arr[self.tail] = item

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
        else:
            self.head = (self.head + 1) % MAX_QUEUE_SIZE
            return self.arr[self.head]

queue = Queue()
queue.enqueue("data 1")
queue.enqueue("data 2")
queue.enqueue("data 3")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

queue.enqueue("data 4")
queue.enqueue("data 5")
queue.enqueue("data 6")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

tailとheadを配列の最初のインデックスに戻すので、十分なスペースがあればデータを入れ続けることができます.

📌 キューの使用

ヒント実際にどこで使うか
BFSは、幅優先ナビゲーションで処理するノードリストを格納するために使用される.
しかし,キュー自体が容易に実現できるため,アルゴリズムでキューを単独で使用する問題はあまり解決されない.