큐 (Queue)

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

구현방법

1. Array list based (시간 복잡도 문제)

• array
• Dynamic array

2. Linked list based (요걸로 구현)

Queue

queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO (First In First Out)형식으로 데이터를 저장하는 자료구조입니다.
queue의 rear에 데이터를 추가하는 것을 enqueue라고 합니다.
queue의 front에서 데이터를 꺼내는 것을 dequeue라고 합니다.

List based Queue

# queue 선언
q = []
# enqueue - O(1)
q.append(1)
q.append(2)
q.append(3)
q.append(4)
# dequeue - O(n)
q.pop(0)
q.pop(0)
q.pop(0)

Linked List based Queue

파이썬에서 잘 구현된 deque 자료구조 사용 (Doubly Linked List로 되어있음)

deque:

• d(doubly)e(ended)queue = deque
• 양방향 enqueue, dequeue 가능

from collections import deque
queue = deque()
# enqueue() - O(1)
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
# dequeue() - O(1)
queue.popleft()
queue.popleft()
queue.popleft()

너비우선탐색 BFS에서 많이 쓰임