CS with Python - Queue

큐 (Queue)

• 큐는 삽입은 뒤에서만, 삭제는 앞에서만 가능한 선입선출의 구조를 가진 자료구조

큐의 특징

1. 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조이다.
2. 큐는 enQueue를 통해 원소를 삽입, deQueue를 통해 원소를 삭제하고 반환하는 연산을 수행한다.
3. 큐의 종류로 선형큐, 원형큐, 우선순위 큐가 존재한다.

큐의 중요성

1. 큐를 통해 버퍼를 이해할 수 있다.
2. 큐와 버퍼의 이해를 스택에 대한 이해와 결합시키면 Breadth-First Search, 즉 BFS에 대해 이해할 수 있다. 이는 우리가 기초적으로 이해해야 할 스택 - 재귀호출 - DFS - Memoization - DP 흐름을 이해하는 데 크나큰 도움이 된다.

큐의 구현

1. 선형 큐

   • 인덱스 활용

   Q = [0] * 10000  # 공간을 미리 만들어두기
   front = -1  # front가 가르키는 곳은 첫번째 요소의 앞
   rear = -1  # rear가 가르키는 곳은 마지막 요소의 위치
   
   # enQueue(5)  enQueue는 끝에서!
   rear += 1
   Q[rear] = 5
   
   # deQueue(5)  deQueue는 앞에서!
   front += 1
   Q[front]

   • 라이브러리 활용

   from colletions import deque
   
   Q = deque()  # 큐를 덱(deque)으로 만든다!
   
   # enQueue(5)
   Q.append(5)
   
   # deQueue(5)
   Q.popleft(5)  # 이거는 Q.pop(0)랑 같으나, 속도는 popleft가 빠름!
   

   • 원형 큐
     to be added

   ver 230425 - 원형 큐 전까지 작성