queue

큐는 항목이 들어온 순서대로 접근가능하다. 즉, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조다.
Ex) 롤러코스터를 타는 것을 기다리는 사람들의 줄

• enqueue : 큐 뒤쪽에 항목을 삽입
• dequeue : 큐 앞쪽의 항목을 반환하고, 제거
• peek/front : 큐 앞쪽의 항목을 조회(가장 오래됨)
• rear : 큐 가장 뒤쪽의 항목 조회(가장 최근)
• 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'])

Time and Space Complexity(시간, 공간 복잡도)

• Enqueue(대기열에 넣기)

데이터를 큐에 추가하면 (데이터를 큐 rear에 추가) O(1) 시간이 걸린다.

• Dequeue(대기열에서 빼기)

데이터를 큐에서 빼면 (데이터를 큐 front에서 제거) 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