9日目キュー

スタック:後入先出(LIFO)
キュー:先入先出(FIFO)
キュー実装

のデータを挿入し、2つの関数

を抽出する必要があります.

データの挿入:キューがいっぱいであることを確認し、最近挿入したデータを

に配置する必要があります.

データ抽出:キューが空かどうかを確認し、最も古いデータが必要な場所

.

#출처 : 코드 메이트 
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関数:キュー内の空白の位置にデータを入れる関数

ではなくtailの次の位置にデータを入れる.
したがって、0番の位置が空であっても、tailが4にある場合、tail+1はキューにデータを入れることができません.
->循環キューを作成することで、を解決できます.
*円形キュー

head,tailがアレイの最後のインデックスに到達すると、アレイの最初の部分

に戻る.
演算子

モジュール(%):tail、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())

キューの使用:

BFS(幅優先ナビゲーション)で処理するノードリストを格納する