Archive

04 Queue

8 min read

자료구조탐색삽입/삭제
Priority Queue
  • 확인 및 추가 필요

1. 큐(Queue)

1.1. 추상 자료형

  • 데이터

    • 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음

  • 연산

    • init(): 초기화
    • enqueue(e): 요소 e를 큐의 맨 뒤(Rear)에 삽입
    • dequeue(): 큐의 맨 앞(Front) 요소를 삭제하고 반환
    • peek(): 맨 앞 요소를 삭제하지 않고 반환
    • is_empty(), is_full(): 공백/포화 상태 확인

1.2. Time Complexity

  • Search: (FIFO 특성상 비효율적)
  • Insert/Delete:

1.3. Features

  • 구조

    • 전단(Front): 데이터가 삭제되는 쪽 (맨 앞)
    • 후단(Rear): 데이터가 삽입되는 쪽 (맨 뒤)

  • 선입선출(FIFO; First-In First-Out)

    • 삽입: rear
    • 삭제: front

1.4. Applications

컴퓨터 시뮬레이션, 너비 우선 탐색(BFS) 등 다양한 알고리즘에 활용

  • 프로세스/스레드 스케줄링 (CPU 작업 큐)
  • 버퍼 관리 (프린터 스풀링, 네트워크 패킷 처리)
    • 처리 속도가 다른 두 장치(예: 빠른 CPU와 느린 프린터) 사이에서 속도 차이를 극복하기 위해 임시로 데이터를 저장하는 버퍼(Buffer)로 사용
  • BFS 그래프 탐색
  • 이벤트 처리 시스템 (이벤트 큐)
  • 데이터 스트림 처리 (스트림 버퍼)
  • 순서 보장 캐시 시스템 (FIFO 캐시)

2. 배열을 이용한 큐의 구현

  • 배열 구조의 큐
    • front, rear에 대한 인덱스를 별도로 저장 (+ 구조체로 사용하여 여러 개의 큐 사용 가능)
    • dequeue가 반복되면 front가 증가, enqueue가 반복되면 rear가 증가
    • 선형 큐(Linear Queue): front, rear가 MAX_SIZE에 도달하면 요소들을 모두 앞으로 옮긴다.
    • 원형 큐(Circular Queue): front, rear가 MAX_SIZE에 도달하면 다시 0으로 만든다.

2.1. 선형 큐(Linear Queue)

  • 구조: 1차원 배열 사용

    • front: 첫 번째 요소 바로 앞의 인덱스
    • rear: 마지막 요소의 인덱스

  • 문제점

    • 데이터의 삽입과 삭제가 반복되면 앞부분에 빈 공간이 있어도 rear가 배열 끝에 도달하여 더 이상 삽입할 수 없는 상태가 발생
    • 해결책으로 요소들을 앞으로 이동시켜야 하는데, 이는 효율성이 떨어진다.

2.2. 원형 큐(Circular Queue)

  • 개념

    • 선형 큐의 문제점을 해결하기 위해 배열의 처음과 끝을 연결하여 원형으로 사용하는 방식

  • 인덱스 회전: 나머지 연산자(%)를 사용

    • front = (front + 1) % MAX_SIZE
    • rear = (rear + 1) % MAX_SIZE

  • 상태 판별

    • 공백 상태: front == rear
    • 포화 상태: front == (rear + 1) % MAX_SIZE (공백과 구분을 위해 한 칸을 비워둠)

  • 구현 코드

    • enqueue: rear를 1 증가시키고(% MAX_SIZE) 해당 위치에 값 저장
    • dequeue: front를 1 증가시키고(% MAX_SIZE) 해당 위치의 값 반환

3. 덱(Deque)

  • 덱(Deque; Double-Ended Queue)
    • 전단(Front)과 후단(Rear) 양쪽 모두에서 삽입과 삭제가 가능한 큐
    • 스택과 큐의 성질을 모두 가질 수 있다.

3.1. 추상 자료형

  • 데이터

    • front와 rear를 통한 접근을 허용하는 요소들의 모음

  • 연산

    • init(): deque 초기화

    • is_empty(): 공백 상태이면 true 반환

    • is_full(): 포화 상태이면 true 반환

    • add_front(e): front에 e 추가

      • front에 추가할 때 → 반 시계 방향 회전

    • delete_front(): front 꺼내서 반환(dequeue)

      • front를 삭제할 때 → 시계 방향 회전

    • get_front(): front 꺼내지 않고 반환(peek)

    • add_rear(e): rear에 e 추가(enqueue)

      • rear에 추가할 때 → 시계 방향 회전

    • delete_rear(): rear 꺼내서 반환

      • rear를 삭제할 때 → 반 시계 방향 회전

    • get_rear(): rear 꺼내지 않고 반환

3.2. 배열을 이용한 원형 덱 구현

  • 원형 큐를 기반으로 하되, 반시계 방향 회전이 필요한 연산이 추가
    • delete_rear() 및 add_front() 구현 시 필요
    • 인덱스 계산: (index - 1 + MAX_SIZE) % MAX_SIZE (음수 방지)

4. 덱의 활용(시행착오법)

  • 시행착오법
    • 하나의 경로를 선택해 시도하고 막히면 다시 다른 경로 찾기 시도
    • 저장된 경로를 모두 선택할 수 있다면 어떤 자료구조에 저장하든지 출구를 찾을 수 있음
    • 가장 대표적인 방법 : DFS, BFS

4.1. 깊이 우선 탐색

  • 깊이 우선 탐색(DFS; Depth First Search)

    • 가장 최근에 저장한 경로를 선택하여 다시 시도
    • 특징: 한 경로로 최대한 깊게 들어갔다가 막히면 가장 최근 갈림길로 돌아옴
    • 구현: 스택(Stack) 원리 사용

  • 덱 활용

    • 입구 삽입: add_rear
    • 현재 위치 꺼내기: delete_rear (후단에서 꺼냄 → 스택처럼 동작 LIFO)
    • 이웃 위치 저장: add_rear

4.2. 너비 우선 탐색

  • 너비 우선 탐색(BFS; Breadth First Search)

    • 가장 먼저 저장된 경로를 선택하여 다시 시도
    • 특징: 시작점부터 가까운 모든 경로를 차례대로 방문하며 넓게 탐색
    • 구현: 큐(Queue) 원리 사용

  • 덱 활용

    • 현재 위치 꺼내기: delete_front (전단에서 꺼냄 → 큐처럼 동작 FIFO)
    • 이웃 위치 저장: add_rear

4.3. 활용

(1) 미로 탐색 알고리즘

  • 덱에는 경로(칸의 위치)를 저장한다.
    • 삽입을 후단으로 고정하고 후단에서 삭제하면 스택으로 동작한다. (DFS)
    • 삽입을 후단으로 고정하고 전단에서 삭제하면 큐로 동작한다. (BFS)
  • 경로를 저장하는 함수에서는 방문하지 않았고 갈 수 있는 칸이면 후단에 삽입한다.
  • 경로를 꺼내는 함수에서는 후단(DFS) 또는 전단(BFS)에서 삭제한다.

(2) 그래프의 순회

  • cf. 그래프
    • 그래프 = 노드 + 링크
    • 그래프의 순회(troversal)
      • stack → DFS
      • queue → BFS

그래프 뷰