Name	Name	Last commit message	Last commit date
parent directory ..
Queue.py	Queue.py
README.md	README.md

Queue (큐)

1. 개념 및 정의

1.1 큐란?

큐(Queue)는 FIFO(First In First Out) 또는 LILO(Last In Last Out) 구조의 선형 자료구조입니다.

"선입선출" = 먼저 넣은 것이 먼저 나온다

1.2 일상 속 큐의 예

예시	설명
줄 서기	먼저 온 사람이 먼저 서비스 받음
프린터 출력	먼저 요청한 문서가 먼저 출력됨
은행 대기 번호	먼저 뽑은 번호가 먼저 호출됨
네트워크 패킷	먼저 도착한 패킷이 먼저 처리됨
콜센터 대기열	먼저 전화한 고객이 먼저 연결됨

1.3 스택 vs 큐 비교

특성	스택 (Stack)	큐 (Queue)
구조	FILO (후입선출)	FIFO (선입선출)
삽입 위치	top (한쪽 끝)	rear (뒤쪽)
삭제 위치	top (같은 끝)	front (앞쪽)
비유	접시 쌓기	줄 서기
대표 활용	DFS, 되돌리기	BFS, 대기열

2. 큐의 구조

2.1 Position (위치 포인터)

┌───────────────────────────────────────────────────┐
│                                                   │
│  front                              rear          │
│    ↓                                 ↓            │
│  ┌─────┬─────┬─────┬─────┬─────┐                 │
│  │  A  │  B  │  C  │  D  │  E  │                 │
│  └─────┴─────┴─────┴─────┴─────┘                 │
│    0      1     2     3     4                     │
│                                                   │
│  deQueue: front에서 제거 (A가 먼저 나감)          │
│  enQueue: rear에서 삽입 (E 다음에 추가)           │
│                                                   │
└───────────────────────────────────────────────────┘

2.2 front와 rear 포인터

포인터	설명	초기값
front	처음 들어온 데이터 (제거할 위치)	-1
rear	마지막에 들어온 데이터 (삽입할 위치)	-1

2.3 포인터 동작 원리

상태	front	rear	설명
빈 큐	-1	-1	초기 상태
첫 번째 enQueue	0	0	데이터 'A' 삽입
두 번째 enQueue	0	1	데이터 'B' 삽입
첫 번째 deQueue	1	1	'A' 제거, front 이동

3. 주요 연산

3.1 연산 개요

연산	설명	Python 구현
enQueue(data)	큐에 데이터 삽입 (rear)	`queue.append(data)`
deQueue()	큐에서 데이터 제거 (front)	`queue.popleft()`
front()	맨 앞 데이터 확인	`queue[0]`
rear()	맨 뒤 데이터 확인	`queue[-1]`
isEmpty()	비어있는지 확인	`len(queue) == 0`

3.2 enQueue vs deQueue 동작

from collections import deque

queue = deque()

# enQueue: 큐의 뒤(rear)에 데이터 추가
queue.append('A')  # [A]
queue.append('B')  # [A, B]
queue.append('C')  # [A, B, C]

# deQueue: 큐의 앞(front)에서 데이터 제거
queue.popleft()    # 'A' 반환, [B, C]
queue.popleft()    # 'B' 반환, [C]

3.3 peek vs deQueue 차이

연산	원본 데이터	반환값	사용 상황
deQueue	삭제	제거된 데이터	데이터를 꺼내서 사용할 때
peek (front)	유지	맨 앞 데이터	데이터를 확인만 할 때

4. 큐의 종류

4.1 종류 비교표

종류	설명	특징
일반 Queue	선형 큐	단방향 입출력
Circle Queue	원형 큐	메모리 효율적 활용
Deque	양방향 큐	양쪽에서 입출력 가능
Priority Queue	우선순위 큐	우선순위에 따라 출력

4.2 일반 Queue (Linear Queue)

┌─────────────────────────────────────────┐
│ 선형 큐 (Linear Queue)                  │
│                                         │
│  front           rear                   │
│    ↓               ↓                    │
│  ┌───┬───┬───┬───┬───┬───┬───┬───┐     │
│  │ X │ X │ A │ B │ C │   │   │   │     │
│  └───┴───┴───┴───┴───┴───┴───┴───┘     │
│    0   1   2   3   4   5   6   7        │
│                                         │
│  문제점: deQueue 시 앞쪽 공간 낭비      │
│         (X 표시된 공간 재사용 불가)     │
└─────────────────────────────────────────┘

특징

가장 기본적인 큐 형태
한쪽 끝(rear)에서만 삽입, 다른 쪽 끝(front)에서만 삭제
단점: deQueue할 때마다 앞쪽 메모리 공간이 낭비됨

4.3 Circle Queue (원형 큐)

┌─────────────────────────────────────────┐
│ 원형 큐 (Circular Queue)                │
│                                         │
│           ┌───────┐                     │
│         ╱ 0   1   2 ╲                   │
│        │  A   B   C  │                  │
│       7│     ↑       │3                 │
│        │   front     │                  │
│        │  H       D  │                  │
│         ╲ 6   5   4 ╱                   │
│            G   F   E                    │
│           └───↑───┘                     │
│             rear                        │
│                                         │
│  특징: 마지막 인덱스 다음은 0으로 순환  │
│       index = (index + 1) % size        │
└─────────────────────────────────────────┘

특징

선형 큐의 메모리 낭비 문제 해결
마지막 위치와 첫 위치가 연결된 것처럼 동작
중요: index 0을 제외하고 시작하는 경우도 있음
인덱스 계산: (현재 인덱스 + 1) % 전체 크기

구현 코드

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = 0
        self.rear = 0
        self.count = 0  # 현재 요소 개수

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.size

    def enqueue(self, data):
        if self.is_full():
            print("큐가 가득 찼습니다!")
            return False
        self.queue[self.rear] = data
        self.rear = (self.rear + 1) % self.size  # 순환
        self.count += 1
        return True

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다!")
            return None
        data = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.size  # 순환
        self.count -= 1
        return data

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[self.front]

# 사용 예시
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue())  # 1
cq.enqueue(4)
cq.enqueue(5)
cq.enqueue(6)  # 순환하여 0번 인덱스에 저장

4.4 Deque (Double-ended Queue, 덱/데크)

┌─────────────────────────────────────────────────┐
│ 덱 (Deque) - 양방향 큐                          │
│                                                 │
│  appendleft()                     append()      │
│       ↓                              ↓          │
│  ┌─────┬─────┬─────┬─────┬─────┐              │
│  │  A  │  B  │  C  │  D  │  E  │              │
│  └─────┴─────┴─────┴─────┴─────┘              │
│       ↑                              ↑          │
│   popleft()                        pop()        │
│                                                 │
│  특징: 양쪽 끝에서 삽입/삭제 모두 가능          │
│       (2개의 Queue를 합친 것과 같음)           │
│       시험에 가장 자주 출제!                   │
└─────────────────────────────────────────────────┘

특징

시험에 가장 자주 출제!
2개의 Queue를 합친 것
양쪽 끝에서 삽입/삭제 모두 O(1)
스택과 큐 모두 구현 가능

5. Python deque 모듈

5.1 deque 소개

collections.deque는 양방향으로 빠르게 추가/제거할 수 있는 큐 자료구조입니다.

모든 연산이 시간 복잡도 O(1)
스레드 안전 (Thread-safe)

5.2 deque import

from collections import deque

# 기본 생성
dq = deque()

# 리스트로 초기화
dq = deque([1, 2, 3, 4, 5])

# 최대 길이 제한
dq = deque(maxlen=5)  # 5개 초과 시 반대쪽에서 자동 제거

5.3 deque 주요 함수 정리

함수	설명	시간복잡도
`append(x)`	오른쪽(rear)에 요소 추가	O(1)
`appendleft(x)`	왼쪽(front)에 요소 추가	O(1)
`pop()`	오른쪽에서 요소 제거 및 반환	O(1)
`popleft()`	왼쪽에서 요소 제거 및 반환	O(1)
`extend(iterable)`	오른쪽에 여러 요소 추가	O(k)
`extendleft(iterable)`	왼쪽에 여러 요소 추가 (역순)	O(k)
`rotate(n)`	n만큼 회전 (양수: 오른쪽, 음수: 왼쪽)	O(k)
`maxlen`	큐의 최대 길이 반환	O(1)
`clear()`	모든 요소 제거	O(n)
`copy()`	얕은 복사본 생성	O(n)
`count(x)`	x의 개수 반환	O(n)
`index(x)`	x의 첫 번째 인덱스 반환	O(n)
`remove(x)`	첫 번째 x 제거	O(n)
`reverse()`	순서 뒤집기	O(n)

5.4 함수별 상세 설명 및 예제

5.4.1 append(x) - 오른쪽에 추가

from collections import deque

dq = deque([1, 2, 3])
dq.append(4)
print(dq)  # deque([1, 2, 3, 4])

5.4.2 appendleft(x) - 왼쪽에 추가

dq = deque([2, 3, 4])
dq.appendleft(1)
print(dq)  # deque([1, 2, 3, 4])

5.4.3 pop() - 오른쪽에서 제거

dq = deque([1, 2, 3, 4])
x = dq.pop()
print(x)   # 4
print(dq)  # deque([1, 2, 3])

5.4.4 popleft() - 왼쪽에서 제거 (큐의 핵심!)

dq = deque([1, 2, 3, 4])
x = dq.popleft()
print(x)   # 1
print(dq)  # deque([2, 3, 4])

5.4.5 extendleft(iterable) - 왼쪽에 여러 요소 추가

dq = deque([3, 4, 5])
dq.extendleft([1, 2])  # 역순으로 추가됨!
print(dq)  # deque([2, 1, 3, 4, 5])

# 주의: extendleft는 요소를 하나씩 왼쪽에 추가하므로
# [1, 2]를 추가하면 1이 먼저 추가되고 2가 그 왼쪽에 추가됨

5.4.6 rotate(n) - 회전

dq = deque([1, 2, 3, 4, 5])

# 오른쪽으로 2칸 회전
dq.rotate(2)
print(dq)  # deque([4, 5, 1, 2, 3])

# 왼쪽으로 1칸 회전
dq.rotate(-1)
print(dq)  # deque([5, 1, 2, 3, 4])

5.4.7 maxlen - 최대 길이 제한

# maxlen 설정 시 크기 초과하면 반대쪽에서 자동 제거
dq = deque([1, 2, 3], maxlen=5)
print(dq.maxlen)  # 5

dq.append(4)
dq.append(5)
print(dq)  # deque([1, 2, 3, 4, 5])

dq.append(6)  # maxlen 초과 → 왼쪽(1) 자동 제거
print(dq)  # deque([2, 3, 4, 5, 6])

5.5 deque 활용 패턴

큐로 사용 (FIFO)

from collections import deque

queue = deque()

# 삽입 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

# 제거 (dequeue)
queue.popleft()  # 1
queue.popleft()  # 2

스택으로 사용 (LIFO)

from collections import deque

stack = deque()

# 삽입 (push)
stack.append(1)
stack.append(2)
stack.append(3)

# 제거 (pop)
stack.pop()  # 3
stack.pop()  # 2

양방향 큐로 사용

from collections import deque

dq = deque()

# 양쪽 삽입
dq.append('right')
dq.appendleft('left')

# 양쪽 제거
dq.pop()      # 'right'
dq.popleft()  # 'left'

6. 구현 코드

6.1 리스트로 구현 (비효율적)

"""
리스트를 사용한 큐 구현
- 단점: popleft 시 O(n) 시간복잡도
- 실제 코딩테스트에서는 deque 사용 권장
"""

queue = []

# enqueue (삽입)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # [1, 2, 3]

# dequeue (제거) - 비효율적!
first = queue.pop(0)  # O(n) - 모든 요소 이동 필요
print(first)  # 1
print(queue)  # [2, 3]

6.2 deque로 구현 (권장)

"""
collections.deque를 사용한 큐 구현
- popleft가 O(1)로 효율적
- 코딩테스트에서 권장하는 방식
"""
from collections import deque

queue = deque()

# enqueue (삽입)
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # deque([1, 2, 3])

# dequeue (제거) - 효율적!
first = queue.popleft()  # O(1)
print(first)  # 1
print(queue)  # deque([2, 3])

6.3 클래스 기반 구현

"""
클래스를 사용한 큐 구현
- 객체지향적 접근
- 캡슐화로 데이터 보호
"""
from collections import deque

class Queue:
    def __init__(self, max_size=None):
        self.items = deque()
        self.max_size = max_size

    def enqueue(self, item):
        """데이터 삽입 (rear)"""
        if self.max_size and len(self.items) >= self.max_size:
            raise OverflowError("큐가 가득 찼습니다")
        self.items.append(item)

    def dequeue(self):
        """데이터 제거 및 반환 (front)"""
        if self.is_empty():
            raise IndexError("큐가 비어있습니다")
        return self.items.popleft()

    def front(self):
        """맨 앞 데이터 확인"""
        if self.is_empty():
            raise IndexError("큐가 비어있습니다")
        return self.items[0]

    def rear(self):
        """맨 뒤 데이터 확인"""
        if self.is_empty():
            raise IndexError("큐가 비어있습니다")
        return self.items[-1]

    def is_empty(self):
        """비어있는지 확인"""
        return len(self.items) == 0

    def is_full(self):
        """가득 찼는지 확인"""
        if self.max_size is None:
            return False
        return len(self.items) >= self.max_size

    def size(self):
        """크기 반환"""
        return len(self.items)

    def __str__(self):
        """문자열 표현"""
        return str(list(self.items))

# 사용 예시
q = Queue(max_size=5)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q)           # [1, 2, 3]
print(q.front())   # 1
print(q.rear())    # 3
print(q.dequeue()) # 1
print(q)           # [2, 3]

6.4 코딩테스트용 간단 구현

"""
코딩테스트에서 가장 자주 사용하는 패턴
"""
from collections import deque

# 큐 생성
queue = deque()

# 삽입 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

# 제거 (dequeue)
while queue:
    current = queue.popleft()
    print(current)

# 비어있는지 확인
if queue:  # 비어있지 않으면
    pass
if not queue:  # 비어있으면
    pass

7. 실전 문제

7.1 문제 1: 프린터 (프로그래머스)

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다.
그러나 중요도가 높은 문서를 먼저 인쇄하는 프린터가 있습니다.

인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
나머지 대기목록에서 J보다 중요도가 높은 문서가 있으면
  J를 대기목록의 가장 마지막에 넣습니다.
그렇지 않으면 J를 인쇄합니다.

예시:
priorities = [2, 1, 3, 2]
location = 2 (중요도 3인 문서)
return = 1 (첫 번째로 인쇄됨)

정답 코드

from collections import deque

def solution(priorities, location):
    """
    프린터 문제

    Args:
        priorities: 중요도 목록
        location: 찾고자 하는 문서의 현재 위치

    Returns:
        int: 몇 번째로 인쇄되는지
    """
    # (인덱스, 중요도) 형태로 큐 생성
    queue = deque(enumerate(priorities))
    answer = 0  # 인쇄 순서

    while queue:
        # 맨 앞 문서 꺼내기
        current = queue.popleft()

        # 대기열에 현재 문서보다 중요도 높은 게 있는지 확인
        if queue and max(q[1] for q in queue) > current[1]:
            # 있으면 뒤로 보내기
            queue.append(current)
        else:
            # 없으면 인쇄
            answer += 1
            # 찾는 문서면 반환
            if current[0] == location:
                return answer

    return answer

# 테스트
print(solution([2, 1, 3, 2], 2))  # 1
print(solution([1, 1, 9, 1, 1, 1], 0))  # 5

7.2 문제 2: 큐 2개로 같은 합 만들기

문제 설명

길이가 같은 두 개의 큐를 받습니다.
각 큐의 원소 합을 같게 만들려고 합니다.
한 번의 pop과 한 번의 insert를 하나의 작업이라고 합니다.
최소 몇 번의 작업이 필요한지 return하세요.
불가능하면 -1을 return합니다.

예시:
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
return = 2

정답 코드

from collections import deque

def solution(queue1, queue2):
    """
    두 큐의 합을 같게 만들기

    풀이 전략:
    - 합이 큰 쪽에서 작은 쪽으로 원소 이동
    - 두 포인터 방식으로 최적화
    """
    queue1 = deque(queue1)
    queue2 = deque(queue2)

    sum1 = sum(queue1)
    sum2 = sum(queue2)

    total = sum1 + sum2

    # 전체 합이 홀수면 불가능
    if total % 2 != 0:
        return -1

    target = total // 2
    count = 0
    max_count = len(queue1) * 4  # 최대 연산 횟수

    while count < max_count:
        if sum1 == target:
            return count

        if sum1 > target:
            # queue1이 크면 queue1에서 빼서 queue2로
            val = queue1.popleft()
            queue2.append(val)
            sum1 -= val
            sum2 += val
        else:
            # queue2가 크면 queue2에서 빼서 queue1으로
            val = queue2.popleft()
            queue1.append(val)
            sum1 += val
            sum2 -= val

        count += 1

    return -1

# 테스트
print(solution([3, 2, 7, 2], [4, 6, 5, 1]))  # 2
print(solution([1, 2, 1, 2], [1, 10, 1, 2]))  # 7
print(solution([1, 1], [1, 5]))  # -1

7.3 문제 3: 기능 개발 (프로그래머스)

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다.
각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있지만,
앞에 있는 기능이 배포될 때 함께 배포됩니다.

progresses: 작업의 진도가 담긴 배열
speeds: 작업의 개발 속도가 담긴 배열

예시:
progresses = [93, 30, 55]
speeds = [1, 30, 5]
return = [2, 1]

정답 코드

from collections import deque
import math

def solution(progresses, speeds):
    """
    기능 개발
    """
    # 각 기능이 완료되기까지 필요한 일수 계산
    days = deque()
    for p, s in zip(progresses, speeds):
        remain = 100 - p
        day = math.ceil(remain / s)  # 올림
        days.append(day)

    answer = []

    while days:
        # 첫 번째 기능의 완료일
        first_day = days.popleft()
        count = 1  # 첫 번째 기능

        # 첫 번째 기능보다 빨리 완료되는 기능들 함께 배포
        while days and days[0] <= first_day:
            days.popleft()
            count += 1

        answer.append(count)

    return answer

# 테스트
print(solution([93, 30, 55], [1, 30, 5]))  # [2, 1]
print(solution([95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1]))  # [1, 3, 2]

7.4 문제 4: 다리를 지나는 트럭 (프로그래머스)

문제 설명

트럭 여러 대가 일차선 다리를 정해진 순서대로 건너려 합니다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 구하세요.

다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며,
다리는 weight 이하까지의 무게를 견딜 수 있습니다.

예시:
bridge_length = 2, weight = 10
truck_weights = [7, 4, 5, 6]
return = 8

정답 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    """
    다리를 지나는 트럭
    """
    time = 0
    bridge = deque([0] * bridge_length)  # 다리 위 트럭 (0은 빈 공간)
    bridge_weight = 0  # 다리 위 현재 무게
    trucks = deque(truck_weights)

    while trucks or bridge_weight > 0:
        time += 1

        # 다리에서 트럭 하나 내리기
        leaving = bridge.popleft()
        bridge_weight -= leaving

        # 새 트럭 올리기 시도
        if trucks:
            if bridge_weight + trucks[0] <= weight:
                # 올릴 수 있으면 올리기
                new_truck = trucks.popleft()
                bridge.append(new_truck)
                bridge_weight += new_truck
            else:
                # 못 올리면 빈 공간 추가
                bridge.append(0)

    return time

# 테스트
print(solution(2, 10, [7, 4, 5, 6]))  # 8
print(solution(100, 100, [10]))  # 101
print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]))  # 110

8. 큐 문제 유형 정리

8.1 큐로 풀어야 하는 유형

키워드	확률	설명
"네트워크"	높음	패킷 처리, 요청 대기열
"대기열"	높음	순서대로 처리, 줄 서기
"순서대로"	높음	FIFO 처리가 필요한 경우
"BFS"	100%	너비 우선 탐색 구현
"최단 경로"	높음	BFS 기반 최단 경로
"시뮬레이션"	중간	순서가 중요한 시뮬레이션

8.2 큐 문제 판별법

문제에서 다음 패턴이 보이면 큐를 고려하세요:

1. 순서대로 처리해야 하는 문제
   → 대기열, 프린터, 작업 스케줄링

2. BFS (너비 우선 탐색) 문제
   → 미로 최단 경로, 그래프 탐색

3. 네트워크/시스템 시뮬레이션
   → 패킷 처리, 프로세스 스케줄링

4. 선입선출(FIFO) 동작이 필요한 문제
   → 캐시, 버퍼 관리

8.3 대표적인 큐 문제들

문제 유형	예시
대기열 처리	프린터, 줄 서기
BFS	미로 탈출, 최단 경로
시뮬레이션	다리를 지나는 트럭, 회전 초밥
스케줄링	CPU 스케줄링, 작업 관리
캐시	LRU 캐시, 페이지 교체

9. 시간복잡도

9.1 자료구조별 연산 비교

연산	list	deque
append (오른쪽 추가)	O(1)	O(1)
pop (오른쪽 제거)	O(1)	O(1)
insert(0, x) (왼쪽 추가)	O(n)	O(1)
pop(0) (왼쪽 제거)	O(n)	O(1)
인덱스 접근	O(1)	O(n)

9.2 왜 deque를 사용해야 하는가?

# list.pop(0)의 문제점
# - 맨 앞 요소 제거 후 모든 요소를 한 칸씩 이동
# - 시간복잡도: O(n)

# 10,000개 요소에서 pop(0) 반복
import time

# list 사용 (느림)
lst = list(range(10000))
start = time.time()
while lst:
    lst.pop(0)
print(f"list: {time.time() - start:.4f}초")

# deque 사용 (빠름)
from collections import deque
dq = deque(range(10000))
start = time.time()
while dq:
    dq.popleft()
print(f"deque: {time.time() - start:.4f}초")

# 결과 예시:
# list: 0.1234초
# deque: 0.0012초

9.3 공간복잡도

저장된 요소 수에 비례: O(n)

참고 자료

deque vs list 선택 기준

상황	권장 자료구조
앞에서 자주 삭제	deque
인덱스로 자주 접근	list
양쪽 끝에서 작업	deque
중간에 삽입/삭제	list 또는 LinkedList
BFS 구현	deque
큐/스택 구현	deque

주의사항

from collections import deque

# 빈 deque에서 popleft() 시 에러 발생
dq = deque()
dq.popleft()  # IndexError: pop from an empty deque

# 항상 비어있는지 확인 후 제거
if dq:
    dq.popleft()

# 또는 조건부로 처리
value = dq.popleft() if dq else None

BFS 기본 템플릿 (큐 활용)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)  # 노드 처리

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

FilesExpand file tree

C_02_Queue

Directory actions

More options

Directory actions

More options

Latest commit

History

C_02_Queue

Folders and files

parent directory

README.md

Queue (큐)

목차

1. 개념 및 정의

1.1 큐란?

1.2 일상 속 큐의 예

1.3 스택 vs 큐 비교

2. 큐의 구조

2.1 Position (위치 포인터)

2.2 front와 rear 포인터

2.3 포인터 동작 원리

3. 주요 연산

3.1 연산 개요

3.2 enQueue vs deQueue 동작

3.3 peek vs deQueue 차이

4. 큐의 종류

4.1 종류 비교표

4.2 일반 Queue (Linear Queue)

특징

4.3 Circle Queue (원형 큐)

특징

구현 코드

4.4 Deque (Double-ended Queue, 덱/데크)

특징

5. Python deque 모듈

5.1 deque 소개

5.2 deque import

5.3 deque 주요 함수 정리

5.4 함수별 상세 설명 및 예제

5.4.1 append(x) - 오른쪽에 추가

5.4.2 appendleft(x) - 왼쪽에 추가

5.4.3 pop() - 오른쪽에서 제거

5.4.4 popleft() - 왼쪽에서 제거 (큐의 핵심!)

5.4.5 extendleft(iterable) - 왼쪽에 여러 요소 추가

5.4.6 rotate(n) - 회전

5.4.7 maxlen - 최대 길이 제한

5.5 deque 활용 패턴

큐로 사용 (FIFO)

스택으로 사용 (LIFO)

양방향 큐로 사용

6. 구현 코드

6.1 리스트로 구현 (비효율적)

6.2 deque로 구현 (권장)

6.3 클래스 기반 구현

6.4 코딩테스트용 간단 구현

7. 실전 문제

7.1 문제 1: 프린터 (프로그래머스)

문제 설명

정답 코드

7.2 문제 2: 큐 2개로 같은 합 만들기

문제 설명

정답 코드

7.3 문제 3: 기능 개발 (프로그래머스)

문제 설명

정답 코드

7.4 문제 4: 다리를 지나는 트럭 (프로그래머스)

문제 설명

정답 코드

8. 큐 문제 유형 정리

8.1 큐로 풀어야 하는 유형

8.2 큐 문제 판별법

8.3 대표적인 큐 문제들

9. 시간복잡도

9.1 자료구조별 연산 비교

9.2 왜 deque를 사용해야 하는가?

9.3 공간복잡도

참고 자료

deque vs list 선택 기준

주의사항