linked list를 이용한 queue 구현

• FIFO(First In First Out) 구조를 생각하며 구현해본다.

  class Node:
      def __init__(self, data=None):
          self.__data = data
          self.__next = None
          
      @property
      def data(self):
          return self.__data
      
      @data.setter
      def data(self, data):
          self.__data = data
          
      @property
      def next(self):
          return self.__next
      
      @next.setter
      def next(self, n):
          self.__next = n
  
  
  class LQueue:
  
      def __init__(self):
          self.front = None
          self.rear = None
          
      def empty(self):
          if self.front is None:
              return True
          else:
              return False
          
      def enqueue(self, data):
          new_node = Node(data)
          
          # 데이터가 하나도 없는 경우, front와 rear은 모두 None을 가리키게 된다.
          # 이 상태에서는 front와 rear에 데이터가 없기 때문에 다음 데이터를
          # 가리킬 수 없다.
          # 따라서 front와 rear가 처음 데이터가 들어왔을 때, 그 데이터를 가리키게
          # 조건을 추가해야 한다.
          
          if self.front is None and self.rear is None:
              self.front = new_node
              self.rear = new_node
              return
          
          self.rear.next = new_node
          self.rear = new_node
      
      def dequeue(self):
          if self.empty():
              return
          
          # 만약 데이터가 한 개 남았을 경우, front와 rear가 같은 데이터를 가리킴
          # front에 있는 데이터를 지역변수로 가리키게 하고 front를 front 다음 데이터로
          # 옮겨도 rear이 계속 지역변수가 가리키고 있는 데이터를 같이 가리키게 된다.
          # 이렇게 된다면 레퍼런스 카운트가 0이 되지 않아 데이터가 지워지지 않는다.
          # 따라서 데이터가 하나 남은 상황이라면 즉, front와 rear이 같은 데이터를
          # 가리키고 있다면 rear도 rear의 다음 데이터를 가리키게 조건을 추가해야 한다.
          
          if self.front is self.rear:
              self.rear = self.rear.next
          
          cur = self.front
          
          self.front = self.front.next
          
          return cur.data
          
      def peek(self):
          if self.empty():
              return
          
          return self.front.data
  
          
  if __name__ == '__main__':
  
      q = LQueue()
      
      q.enqueue(1)
      q.enqueue(2)
      q.enqueue(3)
      q.enqueue(4)
      q.enqueue(5)
      
      while not q.empty():
          print(q.dequeue(), end = " ")
  
  >> 1 2 3 4 5