8장 큐

큐는 극장에 줄을 서는 사람들처럼 삽입된 순서대로 삭제되는 선입설출(FIFO, First In First Out)의 구조로 운영된다. 큐는 한쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하도록 하고, 다른 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다.

스택 vs 큐 차이

	삽입 연산		삭제 연산
	연산자	삽입 위치	연산자	삭제 위치
스택	push	top	pop	top
큐	enQueue	rear	deQueue	front

 

 

큐를 프로그램으로 구현하는 방법은 배열을 사용하는 순차 자료구조방식과 참조변수를 사용하는 연결자료구조가 있다.

 

선형 큐

배열의 크기는 큐의 크기, 즉 큐에 저장할 수 있는 최대 원소의 개수가 된다. 초기 공백 큐의 상태는 front변수와 rear 변수 값이 -1 이다.

원형 큐

- 큐의 포화 상태를 확인하기 위해서 큐의 rear가 배열의 마지막 인덱스 (n-1)인지 검사한다. 문제는 rear이 배열의 마지막 인덱스를 가르키게 되면 앞에 남아있는 (삽입 중간에 Dequeue 되어 비어있는 공간) 공간을 활용 할 수 없게 된다.  이런 경우 원소를 배열의 앞부분으로 이동시켜 위치를 조정해줘야 한다. 그러나 이 작업은 연산도 복잡해지고 큐의 효율성을 떨어트린다. 이를 해결하기 위해 원형 큐를 사용한다.

- 원형 큐의 front, rear 초기 상태는 0 이다.

 

삽입 Enqueue

rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다. 

배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arraysize == front 라면 배열이 포화상태인걸로 판단하여 데이터 삽입이 이루어지지 않게 됩니다.

 

삭제 Dequeue

front의 포인터를 1증가 시키고 그 위치의 데이터를 배열에서 가지고 옵니다. rear==front 조건이라면 배열이 공백상태인걸로 판단하여 Dequeue가 실행되지 않습니다.

 

연결 큐

- 순차 자료구조 방식을 이용한 큐에는 몇 가지 문제가 있다. 사용 크기가 제한되어 있어서 큐의 길이를 마음대로 변경 할 수 없고, 원소가 없을 때에도 항상 처음 크기를 유지해야하므로 메모리 낭비가 심하다. 이를 해결한 것이 연결 큐이다.

- 연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째 노드를 가리키는 참조변수 front와 마지막 노드를 가리키는 참조변수 rear을 사용한다.

 

덱

- 덱은 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 스택의 성질과 큐의 성질을 모두 가지고 있는 자료구조다.

마무리, 큐는 작업 버퍼 큐, 프로세스 스케줄링, 대기 행렬을 모델링하는 시뮬레이션 등에서 사용한다.

 

 

package queue;

interface Queue {
	boolean isEmpty();
	boolean isFull();
	void enqueue(char item);
	char dequeue();
	char peek();
	void clear();
}

class Main implements Queue{
	private int front;
	private int rear;
	private int queueSize;
	private char queueArr[];
	
	public Main(int queueSize) {
		front = -1; // front 초기화
		rear = -1;
		this.queueSize = queueSize; // queue사이즈 설정
		queueArr = new char[this.queueSize]; // 큐 배열 설정
	}
	
	@Override
	public boolean isEmpty() {
		// front, rear가 같으면 데이터가 없는 상태이므로 모두 -1로 초기화
		if(front == rear) {
			front = -1;
			rear = -1;
		} // front, rear가 같은 경우 데이터가 없는 상태이므로 true, 아닌 경우 false
		return (front == rear);
	}
	
	@Override 
	public boolean isFull() {
		// rear 포인터가 큐의 마지막 원소와 동일한 경우 true 아닌 경우 false
		return (rear == this.queueSize-1);
	}
	
	// 큐에 데이터 삽입
	@Override
	public void enqueue(char item) {
		if(isFull()) {
			System.out.println("큐가 꽉 찼습니다.");
		} else {
			queueArr[++rear] = item; // 다음 rear 포인터가 가리키는 위치에 데이터를 추가
			System.out.println("삽입된 데이터 : " + item);
		}
	}
	@Override
	public char dequeue() {
		if(isEmpty()) {
			System.out.println("큐가 비었습니다.");
			return 0;
		} else {
			System.out.println("삭제된 아이템 : " + queueArr[front+1]);
			front = (front+1) % this.queueSize;
			return queueArr[front];
		}
	}
	@Override
	public char peek() {
		if(isEmpty()) {
			System.out.println("큐가 비었습니다.");
			return 0;
		} else {
			System.out.println("peek에 있는 아이템 : " + queueArr[front+1]);
			return queueArr[front+1];
		}
	}
	@Override
	public void clear() {
		if(isEmpty()) {
			System.out.println("큐가 비었습니다.");
		} else {
			front = -1;
			rear = -1;
			queueArr = new char[this.queueSize]; //새로운 큐 배열 생성
			System.out.println("큐 초기화 완료");
		}
	}
	
	// 큐에 저장된 모든 데이터 출력
	public void printQueue() {
		if(isEmpty()) {
			System.out.println("큐가 비었습니다.");
		} else {
			for(int i=front+1; i<=rear; i++) {
				System.out.println(queueArr[i] + " ");
			}
			System.out.println();
		}
	}
	public static void main(String args[]) {
		int queueSize = 5;
		Main arrQueue = new Main(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();
	}		
}