Java 배열로 큐(Queue) 구현하기

Java 배열로 큐(Queue) 구현하기

 

Java의 배열을 이용하여 큐(Queue)를 구현하는 방법에 대해 알아보겠습니다.

 

1. 큐(Queue)

 

 

큐는 먼저 들어간 데이터가 먼저 나오는선입선출(FIFO: First In First Out)의 자료구조이며, 대기열 이라고도 합니다. (Queue라는 단어 자체가 표를 구매하기 위해 일렬로 늘어선 줄을 의미합니다.) 데이터가 삽입되는 위치는 Rear 또는 Back 이라고 하며 가장 뒤에 있고, 데이터가 추출되는 위치는 Front라고 하며 가장 앞에 있습니다. 큐는 일반적으로 데이터가 입력된 순서대로 처리되어야 할 경우에 사용합니다.

 

큐의 variation 으로는 우선순위 큐, 원형 큐, 데크(deque) 등이 존재하며 일반적으로 입력은 enqueue, 출력은 dequeue, 첫 번째 요소의 데이터 확인은 peek 메서드를 사용합니다.

 

다음은 큐가 실제로 사용되는 경우입니다.

 

• 운영체제(OS: Operating System)
  시스템 스케줄링, Input Buffer, 프린터 작업 관리 등에 사용됩니다.

 

1.1. 큐의 구현

 

다음은 일반적으로 큐에 사용되는 필수적인 메서드들입니다.

 

• enqueue
  큐의 가장 마지막에 데이터를 삽입합니다.
• dequeue
  큐의 첫 번째 위치에 있는 데이터를 반환하고 큐에서 삭제합니다.
• isEmpty
  큐가 empty 상태인지 확인합니다.
• clear
  큐에 저장된 모든 데이터를 삭제하고 큐를 초기화합니다.
• peek
  큐의 첫 번째 위치에 있는 데이터를 추출합니다.
  dequeue 메서드와는 달리 큐에서 데이터를 삭제하지 않습니다.

 

다음은 Java로 구현한 큐의 소스코드입니다.

 

/*
 * @ TITLE Queue (배열로 구현한 큐)
 */
interface Queue {
    boolean isEmpty();
    boolean isFull();
    void enqueue(char item);
    char dequeue();
    char peek();
    void clear();
}
 
public class ArrayQueue implements Queue {
    
    private int front;
    private int rear;
    private int queueSize;
    private char queueArr[];
 
    // 큐를 생성하는 생성자
    public ArrayQueue(int queueSize) {
        front = -1;    // front 포인터 초기화
        rear = -1;    // rear 포인터 초기화
        this.queueSize = queueSize;    // queue 사이즈 설정
        queueArr = new char[this.queueSize];    // 큐 배열 생성
    }
    
    // 큐가 비어있는 상태인지 확인
    public boolean isEmpty() {
        // front, rear 포인터가 같은 경우 데이터가 없는 상태이므로 포인터를 모두 -1로 초기화
        if(front == rear) {
            front = -1;
                rear = -1;
        }
        
        // front, rear 포인터가 같은 경우 데이터가 없는 상태이므로 true 아닌 경우 false return
        return (front == rear);
    }
    
    // 큐가 가득찬 상태인지 확인
    public boolean isFull() {
        // rear 포인터가 큐의 마지막 인덱스와 동일한 경우 true 아닌 경우 false return
        return (rear == this.queueSize-1);
    }
    
    // 큐에 데이터 삽입
    public void enqueue(char item) {
        if(isFull()) {
            System.out.println("Queue is full!");
        } else {             
            queueArr[++rear] = item;    // 다음 rear 포인터가 가리키는 위치에 데이터 추가
            System.out.println("Inserted Item : " + item);
        }
    }
    
    // 큐에서 데이터 추출 후 삭제
    public char dequeue() {
        if(isEmpty()) {
            System.out.println("Deleting fail! Queue is empty!");
            return 0;
        } else {
            // 큐에서 삭제할 데이터 반환
            System.out.println("Deleted Item : " + queueArr[front+1]);
 
            // front 포인터는 삭제할 위치에 있는 상태이므로 다음과 같이 (front + 1) % size 로 설정.
            // front + 1 로 설정하면 front 포인터가 마지막 요소에 위치했을 경우,
            // ArrayOutOfBoundException이 발생하기 때문에 (front + 1) % size 로 설정해줌.
            // ex) 큐의 size가 5일 때 (index 범위는 0 ~ 4)
            // index of front 3: (3 + 1) % 5 = 4
            // index of front 4: (4 + 1) % 5 = 0
            front = (front + 1) % this.queueSize;
 
            return queueArr[front];
        }
                
    }
    
    // 큐의 첫번째 데이터 추출
    public char peek() {
        if(isEmpty()) {
            System.out.println("Peeking fail! Queue is empty!");
            return 0;
        } else { 
            // front 포인터가 첫번째 요소를 추출하도록 설정.            front = (front + 1) % this.queueSize;
            System.out.println("Peeked Item : " + queueArr[front]);
            return queueArr[front];
        }
    }
    
    // 큐 초기화
    public void clear() {
        if(isEmpty()) {
            System.out.println("Queue is already empty!");
        } else {
            front = -1;    // front 포인터 초기화
            rear = -1;    // rear 포인터 초기화
            queueArr = new char[this.queueSize];    // 새로운 큐 배열 생성
            System.out.println("Queue is clear!");
        }
    }
    
    // 큐에 저장된 모든 데이터를 출력
    public void printQueue() {
        if(isEmpty()) {
            System.out.println("Queue is empty!");
        } else {
            System.out.print("Queue elements : ");
            // front 포인터는 -1 또는 삭제된 요소의 위치에 있기 때문에,
            // +1 위치를 시작점으로 지정.
            for(int i=front+1; i<=rear; i++) {
                System.out.print(queueArr[i] + " ");
            }
            System.out.println();
        }
    }
 
    public static void main(String args[]) {
        int queueSize = 5;
        ArrayQueue arrQueue = new ArrayQueue(queueSize);
        
        arrQueue.enqueue('A');
        arrQueue.printQueue();
        
        arrQueue.enqueue('B');
        arrQueue.printQueue();
        
        arrQueue.enqueue('C');
        arrQueue.printQueue();
        
        arrQueue.enqueue('D');
        arrQueue.printQueue();
        
        arrQueue.enqueue('E');
        arrQueue.printQueue();
        
        arrQueue.dequeue();
        arrQueue.printQueue();
        
        arrQueue.dequeue();
        arrQueue.printQueue();
        
        arrQueue.dequeue();
        arrQueue.printQueue();
        
        arrQueue.dequeue();
        arrQueue.printQueue();
        
        arrQueue.peek();
        arrQueue.printQueue();
        
        arrQueue.clear();
        arrQueue.printQueue();
    }
    
}

 

위의 코드를 실행하면 다음과 같은 결과가 출력됩니다.

 

 

이상으로 Java의 배열로 구현한 큐에 대해서 알아봤습니다.

 

※ 참고 문헌

• ko.wikipedia.org, 큐 (자료 구조), https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
• donghoson.tistory.com, 자바로 큐(Queue)를 구현하기, https://donghoson.tistory.com/m/162?category=799812
• muckycode.blogspot.com, [자료 구조] 큐(Queue), https://muckycode.blogspot.com/2015/01/queue.html
• thrillfighter.tistory.com, 자료구조 큐(Queue) C언어 , https://thrillfighter.tistory.com/153