[자료구조] 큐(Queue) 설명 및 구현

1. 큐(Queue)

일상생활에서 은행에 들어온 순서대로 번호표를 뽑고 번호표 순서대로 먼저 온 고객부터 처리해 주는 것과 같이 선입선출 형태의 구조를 큐(Queue)라고 부릅니다.

 

큐는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 자료구조이지만 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어지는 자료구조입니다.

2. 큐의 특징

1) 데이터가 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out)  구조입니다.

 

2) 한쪽 끝을 front로 정하여 삭제 연산만 수행하도록 하고 다른 쪽 끝은 rear로 정하여 삽입 연산만 수행하도록 제한하여 만든 자료구조입니다.

 

front 원소는 가장 먼저 큐에 들어온 첫 번째 원소이고, 리어 원소는 가장 늦게 들어온 마지막 원소입니다.

큐의 선입선출 구조

3. 큐 알고리즘

· 큐 생성

createQueue()
    Q[n];
    front ← -1;
    rear ← -1;
end createQueue()

새로 생성하여 저장된 원소가 없는 공백 큐이므로 front와 rear는 -1로 초기화합니다.

· 공백 상태 검사

isEmpty(Q)
    if(front = rear) then return true;
    else return false;
end isEmpty()

큐가 공백인 경우는 처음 공백 큐를 생성하여 front와 rear 값이 -1인 경우와 마지막에 삽입한 rear의 원소를 삭제하여 front가 rear의 위치에 있는 경우입니다. 따라서 front와 rear의 값이 같을 때 큐는 공백 상태입니다.

· 포화 상태 검사

isFull(Q)
    if(rear = n-1) then return true;
    else return false;
end isFull()

큐가 포화 상태인 경우는 배열의 마지막 인덱스까지 원소가 저장된 경우이므로 rear의 값이 배열의 마지막 인덱스 n - 1과 값이 같을 때 큐는 포화 상태입니다.

· 삽입 연산(enQueue)

enQueue(Q, data)
    if(isFull(Q))    then Queue_Full();
    else{
        rear ← rear + 1;
        Q[rear] ← data;
    }
end enQueue()

포화 상태가 아닌 큐에 원소를 삽입하려면 배열에 저장되어 있는 마지막 원소의 다음 자리에 삽입해야 하므로 rear의 값을 하나 증가시키고 삽입합니다.

· 삭제 연산(deQueue)

dnQueue(Q)
    if(isEmpty(Q)) then Queue_Empty();
    else{
        front ← front + 1;
        return Q[front];
    }
end enQueue()

공백 상태가 아닌 큐에서 원소의 삭제는 큐에 저장된 원소 중에서 가장 먼저 삽입된 원소를 가장 먼저 삭제해야 합니다. 따라서 front의 값을 하나 증가시키고 원소를 삭제하여 반환합니다.

4. 큐 구현

· Queue

public interface Queue {
	boolean isEmpty();
	void enQueue(char data);
	char deQueue();
	char peek();
	void delete();
}

 

· ArrayQueue

public class ArrayQueue implements Queue {
	private int front;
	private int rear;
	private int queueSize;
	private char queue[];

	// 큐 초기화
	public ArrayQueue(int queueSize) {
		this.front = -1;
		this.rear = -1;
		this.queueSize = queueSize;
		this.queue = new char[this.queueSize];
	}

	@Override
	public boolean isEmpty() {
		return (rear == front); // front와 rear가 -1인 경우와 front와 rear가 같은 위치에 있을 경우 공백상태
	}

	public boolean isFull() {
		return (rear == this.queueSize - 1); // rear가 배열의 크기와 같을 경우 포화상태
	}

	@Override
	public void enQueue(char data) {
		if (isFull()) {
			System.out.println("큐가 포화상태입니다.\n");
		} else {
			queue[++rear] = data; // rear 위치를 1 증가시킨 뒤 삽입
		}
	}

	@Override
	public char deQueue() {
		if (isEmpty()) {
			System.out.println("큐가 공백상태입니다.\n");
			return 0;
		} else {
			return queue[++front]; // front 위치를 1 증가시킨 뒤 값을 반환
		}
	}

	@Override
	public char peek() {
		if (isEmpty()) {
			System.out.println("큐가 공백상태입니다.\n");
			return 0;
		} else {
			return queue[front + 1]; // 가장 먼저 들어온 값 반환
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			System.out.println("큐가 공백상태입니다.\n");
		} else {
			++front; // front 위치를 1 증가
		}
	}

	// 큐 출력
	public void printQueue() {
		if (isEmpty()) {
			System.out.println("큐가 공백상태입니다.\n");
		} else {
			System.out.printf("Q = ");
			for (int i = front + 1; i <= rear; i++) {
				System.out.printf("%c ", queue[i]);
			}
			System.out.println("\n");
		}
	}
}

 

· MainForQueue

public class MainForQueue {
	public static void main(String[] args) {
		ArrayQueue q = new ArrayQueue(5);
		char data = 0;

		System.out.println("1. 큐에 원소 5개 삽입하기");
		for (char c = 'A'; c <= 'E'; c++) {
			q.enQueue(c);
		}
		q.printQueue();

		System.out.println("2. 가장 먼저 들어온 값 반환하기");
		data = q.peek();
		System.out.printf("%c\n\n", data);

		System.out.println("3. 큐의 원소 3개 디큐");
		for (int i = 0; i < 3; i++) {
			data = q.deQueue();
			System.out.printf("삭제된 원소: %c\n", data);
			q.printQueue();
		}

		System.out.println("4. 큐의 원소 1개 삭제하기");
		q.delete();
		q.printQueue();
	}
}

 

· 실행 결과