[자료구조] 10. 큐

1. 큐의 개념

1) 큐 (Queue)

• 큐는 일상생활에서 흔히 볼 수 있는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 구조를 가진다.

 

큐의 특징

• 스택과 유사하지만, 삽입과 삭제가 서로 다른 위치에서 수행됨

• 삽입은 rear에서, 삭제는 front에서 이루어짐

• front와 rear라는 두 개의 포인터를 사용

 

큐의 예시

• 신호등 앞에서 줄 서 있는 자동차

• 키보드 입력 시 버퍼 메모리에 저장되는 문자들

• 프린터 인쇄 대기열

 

 

2) 큐의 주요 동작

삽입 연산 (Enqueue)

• rear 포인터가 가리키는 위치에 원소 삽입

• 삽입 후 rear 증가

 

삭제 연산 (Dequeue)

• front 포인터가 가리키는 위치의 원소 삭제

• 삭제 후 front 증가

 

 

3) 큐의 추상 자료형 (ADT)

큐의 연산

• enqueue(x): 큐의 rear 위치에 데이터 x 삽입

• dequeue(): 큐의 front 위치에서 데이터 삭제 후 반환

• isEmpty(): 큐가 비어있는지 확인

• isFull(): 큐가 가득 찼는지 확인

 

 

4) 스택과 큐의 연산 비교

• 스택: 삽입(push)과 삭제(pop)이 top에서 이루어짐

• 큐: 삽입(enqueue)은 rear에서, 삭제(dequeue)는 front에서 이루어짐

 

 

5) 큐의 삽입과 삭제 과정

연산 과정 예시

(1) 공백 큐 생성: createQueue();

(2) A 삽입: enqueue(Q, A);

(3) B 삽입: enqueue(Q, B);

(4) 삭제 (A 제거): dequeue(Q);

(5) C 삽입: enqueue(Q, C);

(6) 삭제 (B 제거): dequeue(Q);

(7) 삭제 (C 제거): dequeue(Q);

---

6) 큐의 알고리즘

(1) 공백 상태 검사

isEmpty(Q) {
  if (front == rear) return true;
  else return false;
}

 

(2) 포화 상태 검사

isFull(Q) {
  if (rear == n-1) return true;
  else return false;
}

 

(3) 삽입 연산 (Enqueue)

enqueue(Q, x) {
  if (isFull(Q)) queue_full();
  else {
    rear = rear + 1;
    Q[rear] = x;
  }
}

 

(4) 삭제 연산 (Dequeue)

dequeue(Q) {
  if (isEmpty(Q)) queue_empty();
  else {
    front = front + 1;
    return Q[front];
  }
}

 

 

 

7) 순환 큐 (Circular Queue)와 포화 상태 문제

순차 큐의 문제점

• 큐의 삽입과 삭제가 반복되면 front와 rear가 증가하여, 배열이 비어 있어도 큐가 꽉 찬 것처럼 인식되는 문제 발생

 

해결 방법

• 기존 원소를 배열의 앞부분으로 이동시키는 방법이 있지만, 비효율적

• 원형 큐 (Circular Queue) 사용하여 해결

- rear가 끝까지 가면 다시 처음으로 순환

- 공간 낭비 없이 효율적인 큐 관리 가능

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.