キュー


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