큐(Queue)

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조

큐는 선입선출 FIFO(First in First Out)이라고 부른다

 

코드 리뷰

from collections import deque

class Queue:
    def __init__(self):
        self.data = deque()

    def enqueue(self, x):
        self.data.append(x)

    def dequeue(self):
        return self.data.popleft() if self.data else None

    def is_empty(self):
        return not self.data

파이썬에서 queue는 deque로 충분히 구현 가능하므로 deque 모듈을 사용한다

Queue 클래스에서 내부적으로 deque를 사용하여 큐를 구현한다

큐에 값을 추가하려면 enqueue()을 사용해서 deque.append()를 사용한다

deque에서 값을 출력할때는 dequeue()를 사용해서 deque.popleft()를 사용한다

 

시간 복잡도

연산	일반 큐 (Queue)	원형 큐 (Circular Queue)	덱 (Deque)	우선순위 큐 (Priority Queue)
삽입 (enqueue)	O(1)	O(1)	O(1)	O(log N)
삭제 (dequeue)	O(1)	O(1)	O(1)	O(log N)
접근 (peek)	O(1)	O(1)	O(1)	O(1)
임의 삭제/검색	X	X	O(N)	O(N)

 

• 일반 큐 : 선입선출, 가장 먼저 들어온 데이터가 나감

• 원형 큐 : front와 rear 포인터가 배열 끝에 도달하면 다시 처음으로 순환함

• 덱 : 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐

• 우선순위 큐 : 우선순위(priority)가 높은 요소가 먼저 나가는 큐

 

일반 큐는 뒤에서 삽입(enqueue), 앞에서 삭제(dequeue)만 가능하다

접근은 보통 front(첫 원소)만 허용되므로 제한적이다