큐 - 큐의 개념, 큐의 추상 자료형, 큐의 응용, 배열 큐, 원형 큐

1. 큐의 개념

큐의 의미

큐(Queue)는 일상생활에서 흔히 볼 수 있는 줄 서기와 유사하다. 사람들이 버스 정류장에 줄을 서서 버스를 기다리는 것처럼, 큐는 데이터들이 들어오고 나가는 순서가 중요한 자료 구조다.

큐의 정의

큐는 선입선출(First In First Out, FIFO)의 원칙을 따르는 자료 구조다. 큐에 가장 먼저 들어온 데이터가 가장 먼저 나간다.

• 추상적 특성: 큐는 추상적인 개념으로, 데이터의 처리 순서를 제어하는 데 초점을 맞춘다. 큐에 데이터를 추가하는 것을 'Enqueue', 데이터를 꺼내는 것을 'Dequeue'라고 함.
• 구현 방식: 큐는 배열이나 연결 리스트 등으로 구현될 수 있다. 각각의 구현 방식에 따라 성능이나 사용 방법에 차이가 있을 수 있음.

2. 큐의 추상 자료형

큐의 연산

큐의 기본적인 연산에는 삽입(Enqueue), 삭제(Dequeue), 비어있는지 확인(isEmpty), 가득 찼는지 확인(isFull) 등이 있다. 각 연산은 큐의 선입선출 특성을 유지하면서 데이터를 관리한다.

1. 삽입 연산 (Enqueue)

• 새로운 데이터를 큐의 끝에 추가한다.
• 큐가 가득 차 있지 않을 때만 수행할 수 있다.
• 예시 슈도코드:

  void enqueue(int data) {
      if (!isFull()) {
          queue[rear] = data;
          rear = (rear + 1) % queueSize;
      }
  }

2. 삭제 연산 (Dequeue)

• 큐의 맨 앞에 있는 데이터를 제거하고 반환한다.
• 큐가 비어있지 않을 때만 수행할 수 있다.
• 예시 슈도코드:

  int dequeue() {
      if (!isEmpty()) {
          int data = queue[front];
          front = (front + 1) % queueSize;
          return data;
      }
      return -1; // 큐가 비어있는 경우
  }

3. 비어있는지 확인 (isEmpty)

• 큐가 비어있는지 여부를 반환한다.
• front와 rear의 위치를 비교하여 판단한다.

4. 가득 찼는지 확인 (isFull)

• 큐가 가득 차 있는지 여부를 반환한다.
• rear의 다음 위치가 front와 같으면 가득 찬 것으로 판단한다.

3. 큐의 응용

CPU의 관리 방법과 큐의 활용

컴퓨터 시스템에서 CPU의 관리는 큐의 개념을 활용하여 효율적으로 이루어진다. CPU 작업 스케줄링, 특히 'First-Come, First-Served(FCFS)' 방식은 큐의 기본적인 원리인 선입선출(FIFO) 방식과 매우 흡사하다. 이 방식에서는 먼저 요청된 작업이 먼저 CPU 자원을 할당받게 된다.

라운드 로빈 스케줄링

• 라운드 로빈(Round Robin) 방식은 각 작업에 동일한 시간을 할당하여 CPU가 순차적으로 작업을 처리.
• 이 방법은 공정성을 기반으로 하며, 작업들이 일정 시간 동안 CPU를 사용한 후 대기열의 끝으로 이동.
• 라운드 로빈은 큐를 사용하여 각 작업의 순서를 관리하며, 각 작업이 CPU를 공평하게 사용할 수 있도록 함.

원형 큐의 활용

• CPU 작업 스케줄링에서 원형 큐는 효율적인 자원 관리에 핵심적인 역할을 한다.
• 원형 큐는 배열 기반의 큐가 가진 공간 낭비 문제를 해결한다. 배열의 끝에 도달한 후에도 공간을 재활용하여 작업을 계속 추가할 수 있다.
• 이 방식은 메모리를 효율적으로 활용하며, 작업의 순환적인 관리를 가능하게 한다.

CPU 관리는 큐의 개념을 실제 시스템에 적용하는 대표적인 예시 중 하나이다. 라운드 로빈 방식과 같은 다양한 스케줄링 기법들이 큐의 이론을 바탕으로 개발되었다.

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

큐의 생성

배열을 사용해 큐를 구현하려면 배열의 크기와 큐의 시작점(프론트) 및 끝점(리어)을 관리하는 것이 중요하다.

큐의 초기 상태

• 프론트(Front): 삭제 연산이 일어나는 지점.
• 리어(Rear): 삽입 연산이 일어나는 지점.

예시: 크기가 5인 배열 int[] queue = new int[5];를 선언하고, 프론트와 리어는 -1로 초기화한다.

큐의 삽입 연산

• 조건: 배열이 가득 차지 않았을 때
• 연산: 리어의 위치를 증가시키고 그 위치에 데이터를 삽입

예시: 큐에 1, 2, 3을 차례로 삽입하면 배열은 [1, 2, 3, 0, 0]이 되고, 리어는 2가 된다.

큐의 삭제 연산

• 조건: 큐가 비어있지 않을 때
• 연산: 프론트 위치의 데이터를 삭제하고 프론트를 증가시킨다

예시: 위 상태에서 하나의 요소를 삭제하면, 프론트가 0에서 1로 이동하고, 배열은 [1, 2, 3, 0, 0] 상태를 유지한다. (실제 삭제된 요소는 프로그램에서 사용하지 않는 것으로 간주)

문제점과 해결 방안

• 문제점: 삭제 연산으로 인해 배열 앞 부분에 공간이 생겨도, 리어 포인터가 배열 끝에 도달하면 삽입이 불가능해진다.
• 해결 방안: 원형 큐를 도입하여 리어 포인터가 배열 끝에 도달하면 배열의 처음으로 돌아가 빈 공간을 활용한다.

자바 코드 예시

public class Queue {
    int size;
    int front, rear;
    int[] queue;

    public Queue(int size) {
        this.size = size;
        this.queue = new int[size];
        this.front = this.rear = -1;
    }

    public void enqueue(int data) {
        if ((rear + 1) % size == front) {
            System.out.println("Queue is full");
        } else {
            rear = (rear + 1) % size;
            queue[rear] = data;
        }
    }

    public int dequeue() {
        if (front == rear) {
            System.out.println("Queue is empty");
            return -1;
        } else {
            front = (front + 1) % size;
            return queue[front];
        }
    }
}

이 코드는 크기가 고정된 배열을 사용해 원형 큐를 구현한다. enqueue 메소드는 새 요소를 삽입하고, dequeue 메소드는 요소를 삭제한다. 여기서 원형 큐의 핵심은 인덱스 계산에 모듈로 연산을 사용하는 것이다.

5. 원형 큐

원형 큐의 개념과 특징

원형 큐(Circular Queue)는 기존 선형 큐의 한계점을 개선한 자료구조이다. 선형 큐의 경우, 큐의 앞 부분에 공간이 비어 있어도 데이터를 삽입할 수 없는 '공간 낭비' 문제가 있었다. 반면 원형 큐는 물리적 형태는 선형이지만, 논리적으로 원형 구조를 가진다. 즉, 큐의 끝과 시작이 연결되어 있어 공간 활용도가 높다는 장점이 있다.

특징 요약:

• 선형 큐의 공간 낭비 문제 해결
• 물리적으로는 선형, 논리적으로는 원형 구조
• 공간 활용도 상승
• 인덱스 관리에 나머지 연산(%) 사용

원형 큐의 구현 방법

원형 큐의 구현은 '프론트(Front)'와 '리어(Rear)' 두 개의 포인터를 사용한다. 큐에 데이터를 삽입하거나 삭제할 때, 이 포인터들을 원형으로 움직이게 하여 큐를 관리한다. 구체적으로, 삽입 연산(enqueue)시 리어 포인터를 증가시키고, 삭제 연산(dequeue)시 프론트 포인터를 증가시킨다. 인덱스 관리에는 나머지 연산자를 활용해 원형 구조를 유지한다.

구현 요소:

• 프론트와 리어 포인터 사용
• 삽입 연산: 리어 포인터 이동 후 데이터 삽입
• 삭제 연산: 프론트 포인터 이동 후 데이터 제거
• 포인터 이동은 나머지 연산으로 제한

원형 큐에서의 삽입과 삭제 연산

원형 큐에서 삽입 연산은 리어 포인터를 이동시키며 데이터를 추가한다. 삭제 연산은 프론트 포인터를 이동시키며 데이터를 제거한다. 이 때, 포인터의 이동은 나머지 연산을 통해 큐의 크기를 넘지 않도록 제어한다. 이러한 구조 덕분에 원형 큐는 빈 공간을 효율적으로 재활용할 수 있다.

연산 과정:

• 삽입(enqueue): 리어 포인터 이동 → 데이터 추가
• 삭제(dequeue): 프론트 포인터 이동 → 데이터 제거
• 포인터 이동은 큐의 크기를 고려하여 제한

큐의 빈 상태와 삽입 상태

원형 큐에서 빈 상태는 프론트와 리어 포인터가 동일한 위치에 있을 때를 말한다. 예를 들어, 모든 요소가 삭제되어 프론트와 리어가 같은 지점을 가리킬 때 큐는 빈 상태이다. 반면에, 삽입 상태는 새 요소가 큐에 추가될 때 발생한다. 이때 리어 포인터는 새로운 요소의 위치로 이동하고, 큐에 공간이 있는 한 계속해서 삽입이 가능하다.

큐의 삭제로 인한 빈 상태

원형 큐에서 요소를 삭제하면 프론트 포인터가 이동한다. 만약 모든 요소가 삭제되어 프론트 포인터가 리어 포인터와 같은 위치에 오게 되면, 큐는 다시 빈 상태가 된다.

큐의 만원 상태

원형 큐에서 만원 상태는 큐가 꽉 차 있는 상태를 의미한다. 이는 리어 포인터가 큐의 마지막 요소 뒤에 위치할 때 발생한다. 하지만 원형 큐의 특성상 실제로는 물리적인 배열의 처음으로 포인터가 이동하는 순환 구조를 가진다.

원형 큐의 초기 상태

원형 큐를 처음 생성했을 때, 프론트와 리어 포인터는 동일한 위치, 보통 배열의 시작점을 가리킨다. 이 상태에서 큐는 비어 있는 상태이며, 삽입과 삭제 연산이 수행될 준비가 되어 있다.

원형 큐의 상태 변화와 예시

원형 큐는 삽입과 삭제 연산을 통해 상태가 변화한다. 예를 들어, 크기가 5인 원형 큐가 있고 현재 리어와 프론트 포인터가 인덱스 0을 가리킨다고 가정해보자. 데이터 A를 삽입하면 리어 포인터는 인덱스 1로 이동하고, A가 저장된다. 이후 데이터 B와 C를 삽입하면 리어 포인터는 각각 인덱스 2와 3으로 이동한다. 만약 이 상태에서 데이터 A를 삭제하면, 프론트 포인터는 인덱스 1로 이동하고, A는 큐에서 제거된다. 이러한 방식으로 원형 큐는 연속적인 데이터 삽입 및 삭제를 효율적으로 처리한다.

상태 변화 예시:

1. 초기 상태: 프론트, 리어 포인터 모두 인덱스 0
2. A 삽입: 리어 포인터 인덱스 1로 이동, A 저장
3. B, C 삽입: 리어 포인터 순차적으로 이동, 각 데이터 저장
4. A 삭제: 프론트 포인터 인덱스 1로 이동, A 제거
5. 결과 상태: 프론트 포인터 인덱스 1, 리어 포인터 인덱스 3

원형 큐의 삽입 연산 결과

원형 큐에서 삽입 연산을 수행하면, 큐에 새로운 요소가 추가되고 리어 포인터가 새 요소의 위치로 업데이트된다. 만약 리어 포인터가 배열의 끝에 도달하면, 순환 구조에 따라 다시 배열의 시작점으로 이동한다.

 

 

---

 

 

참고 자료: 자료구조 (강태원, 정광식 공저, KNOU press 출판)