queue

キューは、エントリが入る順にアクセスできます.すなわち,最初に入力したデータは,先進先出(FIFO)構造である.
Ex)ジェットコースターを待つ人

enqueue:キューの後ろに項目を挿入

dequeue:キューの先頭にあるアイテムを返し、

を削除します.

peek/front:クエリーキューのフロントエンドのアイテム(最古)

hut:クエリーキューの一番後ろの項目(一番近い)

empty:キューが空であるかどうかを確認

size:キューのサイズを確認

🎈 リスト・メソッドを使用したキューの作成

from collections import deque
queue = deque(["Eric", "John", "Michael"])
print('queue Before : ', queue)
queue.append("Terry")           
queue.append("Graham")          
print('queue.popleft() : ',queue.popleft())

print('queue.popleft() : ',queue.popleft())

print('queue After : ', queue)

#결과
queue Before :  deque(['Eric', 'John', 'Michael'])
queue.popleft() :  Eric
queue.popleft() :  John
queue After :  deque(['Michael', 'Terry', 'Graham'])

時間と空間の複雑さ

Enqueue(キュー)

キューにデータを追加する(キューの後ろにデータを追加する)にはO(1)時間かかります.

Dequeue(キューから削除)

キューからデータを削除する(キューの先端からデータを削除する)にはO(1)時間かかります.

実際には、値を減算または削除する指示概念ではありません.
Enqueueの概念は、新しいノードのストレージスペース(変数)を作成し、ノードをストレージスペースに入れることです.
dequeueは、削除するノードのストレージスペース(変数)を作成し、削除するノードをストレージスペースに入れる概念です.

コード実装

class node():
  def __init__(self, value, next):
    self.value = value
    self.next = None

class Queue:
  def __init__(self):
    self.front = None # 제일 앞에 있는 친구
    self.rear = None # 제일 마지막 친구

  def enqueue(self, value): # 큐에 값을 넣음
    new_node = node(value)

    if self.rear is None: # 안에 아무도 없을 때
      self.front = new_node
      self.rear = new_node
    
    else : #안에 누가 있을 때
      self.rear.next = new_node # 새로운 노드를 rear 다음에 삽입
      self.rear = new_node # 새로운 노드를 rear 재할당

  def dequeue(self): # 큐에 값을 뺌
    if self.front is not None: #안에 값 있을 때
      old_front = self.front # front값을 old_front에 삽입
      self.front = old.front.next #old front 다음 값을 front 값에 삽입

    else : # 안에 값 없을 때
      self.rear = None # rear를 None으로 지정

    return old_front