[Data Structure] 큐(1) 선형 큐 구현과 단점

 

 

큐의 개념

 

선형자료구조인 큐는 FIFO(선입선출) 구조의 자료구조이다. 스택은 데이터가 들어가는 입구와 출구가 공유된 자료구조라면 큐는 입구와 출구가 서로 다른 곳에 존재한다.

 

 

 

 

---

 

큐의 주요 메서드와 front, rear

 

큐는 기본적으로 front와 rear 가장 처음 큐에 들어온 데이터를 front로 마지막에 들어온 데이터를 rear로 추적 관리한다.

(위 그림에서는 A가 front C가 rear라고 볼 수 있다.)

 

 

큐에다가 데이터를 넣는 과정을 enqueue,  데이터를 꺼내는 과정을 dequeue라고 부른다.

 

enqueue, dequeue 기능 말고도 스택처럼 peek, size 등 상황에 맞게 기능을 추가해도 된다.

 

 

overflow (큐가 꽉 찬 상태)

  정적 할당 큐인 경우 count 변수를 두어 큐 사이즈와 count를 비교해 overflow 체크한다.

  

underflow (큐가 비어 있는 상태)

  front 변수와 rear 변수가 같은 곳을 가리키고 있다면 큐는 비어있는 상태라고 볼 수 있다. 

 

 

---

 

큐와 스택의 차이

특징	큐	스택
처리 방식	선입선출(FIFO)	후입선출(LIFO)
데이터 추가	rear에서 enqueue	top에서 push
데이터 삭제	front에서 dequeue	top에서 pop
데이터 확인	rear에서 peek	top에서 peek
사용되는 곳	작업 대기열 관리, BFS	JVM 메서드 호출 및 관리, DFS
구현 방법	연결 리스트, 배열	연결 리스트, 배열

 

 

---

 

우선 이번 글에서는 배열을 사용해 선형 구조로 큐를 구현해 보겠다.

정적 할당 큐이다.

 

선형 큐(linear queue)

 

[큐 인터페이스]

package arrqueue;

public interface QueueInterface {
    void enqueue(int value);
    void dequeue();
}

 

우선 간단하게 enqueue, dequeue만 만들기로 하자.

 

 

 

[큐 구현 클래스]

 

1. enqueue 오버라이딩

    @Override
    public void enqueue(int value) {
        if (count >= size) {
            System.out.println("큐가 가득차있는 상태");
            return;
        }
        arr[rear++] = value;
        count++;
        System.out.println(Arrays.toString(arr) + "  count=" + count);
    }

 

enqueue 과정은 큐에서 rear를 이용해 배열에 넣는다. 

rear를 통해 삽입하는 이유는 Queue는 FIFO 구조이므로 뒤쪽으로 데이터를 넣어 front 쪽으로 데이터를 꺼내는 구조인 것이다.

 

데이터를 추가할수록 rear는 증가한다.

 

 

2. dequeue 오버라이딩

    //dequeue시 값을 삭제하지 않은 이유는 어차피 선형 큐에서는 삭제된 공간을 재사용하지 못하기 때문
    @Override
    public void dequeue() {
        if (rear == front) {
            System.out.println("큐");
            return;
        }
        System.out.println("꺼낸값: " + arr[front++]);
        count--;
        System.out.println(Arrays.toString(arr) + "  count=" + count);

    }

 

 

 

전체 코드

package arrqueue;
/*
    해당 큐는 선형 큐 구현할 시 단점을 보여주기 위한 코드이다.
    반복되는 enqueue, dequeue 작업에서 단점을 보여주기 위한 코드이므로 peek를 구현안했다.
    딱 enqueue, dequeue만 구현하였으며

    선형 큐의 단점
    1. 배열 공간이 남아있어도 enqueue 불가능  "공간 낭비"
    2. rear가 배열의 맨 끝에 도달하는 순간 큐에 데이터 저장 더 이상 못함.
    3. 이러한 이유로 원형 큐가 필요하다.
 */

import java.util.Arrays;

public class QueueImplement implements QueueInterface {
    int[] arr;
    private int rear;
    private int front;
    private int size;
    private int count;

    QueueImplement() {
        arr = new int[10];
        size = 10;
        rear = front = 0;
    }

    @Override
    public void enqueue(int value) {
        if (count >= size) {
            System.out.println("큐가 가득차있는 상태");
            return;
        }
        arr[rear++] = value;
        count++;
        System.out.println(Arrays.toString(arr) + "  count=" + count);
    }

    //dequeue시 값을 삭제하지 않은 이유는 어차피 선형 큐에서는 삭제된 공간을 재사용하지 못하기 때문
    @Override
    public void dequeue() {
        if (rear == front) {
            System.out.println("큐");
            return;
        }
        System.out.println("꺼낸값: " + arr[front++]);
        count--;
        System.out.println(Arrays.toString(arr) + "  count=" + count);

    }
}

 

 

 

실행

 

package arrqueue;

public class Main {
    public static void main(String[] args) {
        QueueImplement queueImplement = new QueueImplement();
        for (int i = 0; i < 5; i++) {
            queueImplement.enqueue((i + 1) * 10);
        }
        queueImplement.dequeue();

        for (int i = 0; i < 6; i++) {
            queueImplement.enqueue((i + 1) * 10);
        }
    }
}

 에러를 발생시킨 Main문

 

 

 

 

---

 

선형 큐의 문제점

 

로직상 enqueue를 하면 rear는 증가하고 dequeue를 하면 front 역시 증가한다.

하지만 해당 코드는 정적 할당 선형 큐이다. 한번 정해진 배열 크기는 변할 수 없다.

 

만약 enqueue를 배열 사이즈만큼 호출해서 값을 넣으면 rear 변수는 배열의 끝 index값까지 증가할 것이다.

꽉 찬 상태에서 dequeue를 하면 front는 1 증가하여 1자리를 남게 한다. 하지만 선형 큐는 남은 자리에 접근하지 못한다. 

 

 

 

 

문제점을 정리하면

 

- 배열 공간이 남아있어도 enqueue 불가능 (공간 낭비)

- 배열 공간 활용하기 위해서는 큐 안에 있는 요소를 다시  배열의 시작점 쪽으로 하나씩 다 옮겨야 함 (비효율적)

- rear가 배열의 맨 끝에 도달하는 순간 큐에 데이터 저장 더 이상 못함.

- 이러한 이유로 원형 큐가 필요하다.

 

---

 

 

선형 큐는 매우 비효율적이라 보통 원형 큐로 큐를 만든다.