LG트윈스 팬인 저는 경기 예매를 할 때마다 이런 화면을 자주 봅니다.

먼저 접속한 사람이 먼저 티켓팅을 할 수 있는데, 이게 바로 '큐'의 원리죠~

큐

• 스택과 같이 데이터를 임시 저장하는 구조
• 하지만 먼저 넣은 데이터를 가장 먼저 꺼내는, 선입선출 (FIFO, First In First Out) 구조
• 인큐 (enqueue): 큐에 데이터를 추가하는 작업
• 디큐 (dequeue): 가장 먼저 인큐했던 데이터를 꺼내는 작업
• 앞(front)은 데이터를 꺼내는 쪽, 뒤(rear)는 데이터를 넣는 쪽

deque(덱)을 이용한 큐 구현

• 파이썬에선 collections 모듈의 deque 클래스로 큐를 구현할 수 있음
  • deque는 디큐가 아니라 덱으로 읽음
• .append()로 인큐를, .popleft()로 디큐를 구현할 수 있음
  • .popleft()은 디큐한 원소를 반환
• 덱에 대한 자세한 설명은 이 글의 마지막 부분 참고

from collections import deque
queue = deque()

# 큐에 데이터 인큐: .append()
queue.append(33)
queue.append(9)
queue.append(41)

# 큐에서 데이터 디큐: .popleft()
print(queue.popleft())  # 33

# 다시 데이터 인큐
queue.append(1)
queue.append(10)

# 큐의 맨 앞 값 확인
print(queue[0])         # 9

# 큐의 크기 구하기
queue_size = len(queue) # 현재 큐는 [9, 41, 1, 10]
print(queue_size)       # 4

# 다시 데이터 디큐
print(queue.popleft())  # 9

시간 복잡도

• .append(), .popleft()의 시간 복잡도 모두 $O(1)$
  • 덱은 연결 리스트 기반이기 때문
• len: 길이 정보는 덱 객체에 저장되어 있음, $O(1)$
• queue[0]: 덱의 인덱싱은 순차 탐색으로 이루어지지만, 첫 인덱스인 만큼 바로 종료. $O(1)$

클래스를 이용한 큐 구현

• 직접 코딩 테스트에서 클래스로 큐를 구현할 일은 없지만, 알아두면 좋다~

• Queue 클래스 만들기

  • 크기, 즉 저장 가능한 최대 원소 수가 저장된 큐
  • 디큐, 인큐, 저장 원소 수 확인, 맨 앞 데이터 확인에 해당하는 기능만 구현해 보겠습니다

class Queue:
    def __init__(self, capacity=256):
        self.num = 0                    # 현재 원소 수
        self.capacity = capacity        # 큐의 크기 (최대 저장 가능 원소 수)
        self.queue = [None] * capacity  # 값을 저장할 배열
        self.front = 0                  # 맨 앞
        self.rear = 0                   # 맨 끝 다음

    def __len__(self):
        # 큐의 데이터 수를 반환
        # 함수 len(obj)로 본 메서드 호출 가능
        return self.num

    def enqueue(self, x):
        # 큐에 데이터 x를 인큐
        # 큐가 가득 찬 경우 아무것도 하지 않음
        if self.num >= self.capacity:
            return

        self.queue[self.rear] = x
        self.rear += 1

        # 맨 끝 다음 인덱스는 맨 앞
        if self.rear >= self.capacity:
            self.rear = 0
        self.num += 1

    def dequeue(self):
        # 큐에서 데이터를 디큐
        # 큐가 빈 경우 아무것도 하지 않음
        if self.num <= 0:
            return
        x = self.queue[self.front]
        self.front += 1

        # 맨 끝 다음 인덱스는 맨 앞
        if self.front >= self.capacity:
            self.front = 0
        self.num -= 1
        return x

    def peek(self):
        # 맨 앞 (다음에 꺼낼) 데이터 확인
        # 큐가 빈 경우 아무것도 하지 않음
        if self.num <= 0:
            return
        return self.queue[self.front]

속성 정의

• self.capacity개의 원소를 저장할 수 있는 배열 self.queue 생성
• self.front의 최초 값은 0: 큐의 맨 앞 원소의 인덱스를 나타냄
• self.rear의 최초 값은 0: 큐의 맨 끝 원소 바로 뒤의 인덱스를 나타냄
  • 다음 인큐되는 데이터가 저장되는 위치
• self.num으로 저장된 원소 수 세기

메서드 정의

• 인큐할 땐 self.rear 위치에 값 저장 후, self.rear을 1 증가
  • self.rear가 인덱스 범위를 넘는 경우 0으로 되돌림
• 디큐할 땐 self.front 위치의 값을 저장하고, self.front을 1 증가한 뒤, 저장한 값을 반환
  • self.front가 인덱스 범위를 넘는 경우 0으로 되돌림
• 맨 앞 데이터를 확인할 땐 self.front번째 인덱스를 확인
• 매번 인큐할 때 self.num += 1, 디큐할 때 self.num -= 1로 계산한 뒤, 길이를 확인할 때 self.num 반환
  • obj.__len__() 메서드를 정의하면, 이후엔 len(obj)로 호출 가능 (메서드 오버라이딩)

실제 동작과정

q = Queue(6)        # 크기가 6인 배열 만들기
q.enque(82)         # [82]
q.enque(95)         # [82, 95]
q.enque(17)         # [82, 95, 17]
print(q.dequeue())  # 맨 앞 82 디큐
q.enque(40)         # [95, 17, 40]
print(len(q))       # 3
print(q.peek())     # 맨 앞 95

문제풀이

3190. 뱀

별도 글로 대체