Queue란?

→ 간단히 말해 한쪽 끝에서 값을 추가할 수 있고 다른 한쪽에서 값을 제거할 수 있는 컬렉션

→ First in First out 선입선출로 처리된다.

python deque 객체

→ deck ( double ended queue ) : 양쪽에서 추가와 제거가 가능한 리스트류

→ doc :https://docs.python.org/ko/3/library/collections.html

→ 데크는 스택과 큐를 일반화한것

→ 파이썬의 리스트보다 비용이 굉장히 저렴하다.

stack 구현하기

→ 노드 생성

• 먼저 노드를 생성해준다. 스택과 동일하게 값과 다음값을 참조한다.

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

→ Queue 생성

• queue는 FIFO이기 때문에 front를 가지도록 한다.

  class Queue :
      def __init__(self):
          self.front = None
  

→ is_empty : 큐가 비어있는지 확인해주는 함수

• 단순히 front가 있는지 없는지 반환해준다.

  def is_empty(self):
          return self.front is None
  

→ push : 큐에 값을 추가해주는 함수

• front가 없을 경우 바로 front에 node를 연결해준다.

• front가 이미 있을 경우에는 끝자리에 가서 노드를 연결해준다.

  def push(self, value) :
  		if not self.front :
  				self.front = Node(value, None)
  				return
  	
  		node = self.front
  		while node.next :
  				node = node.next
  		node.next = Node(value, None)
  

→ pop : 큐에 front (제일 앞자리) 를 제거해주는 함수

• front가 없으면 None을 반환

• front가 있으면 front를 다음 노드로 바꿔준다.

• 제거된 값을 반환해준다.

  def pop(self) :
  		if not self.front :
  				return None
  		node = self.front
  		self.front = self.front.next
  		return node