큐(Queue)

- 입출력이 서로 반대쪽으로 이루어지는 제한구조이다. 즉, 자료는 입력된 순서대로 출력되는 선입선출(FIFO) 방식이다.

- 한쪽 끝에서 삽입이 일어나고 반대쪽으로 끝에서 삭제가 일어나는 선형 리스트이다.

- 큐의 각 항목들을 동일한 데이터 형태이다.

 

특징

- 임의의 우선순위를 가진 원소를 우선순위 큐에 언제든지 삽입할 수 있고, 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 이러한 두 연산을 지원하는 자료 구조를 최대(최소) 우선순위 큐라고 하며 구현 방법으로는 최대(최소) heap을 사용한다.

- 큐는 스택과 마찬가지로 배열이나 연결리스트로 구현이 가능하다.

 

응용

- 작업스케줄링, 전철역에서 개찰구를 통과

- 버퍼, 스풀, Radix 정렬시 버킷으로 이용

- 그래프 너비 우선 탐색(BFS)

 

JAVA 코드 구현

package com.cs0210;

public class QueueArr {
	private int front;
	private int rear;
	private int size;
	private char[] arr;

	public QueueArr(int size) {
		front = -1;
		rear = -1;
		this.size = size;
		arr = new char[size];
	}

	public boolean isEmpty() {
		if (front == rear) {
			front = -1;
			rear = -1;
		}
		return front == rear;
	}

	public boolean isFull() {
		return (rear == this.size - 1);
	}

	public void enqueue(char data) {
		if (isFull()) {
			System.out.println("포화 상태입니다.");
		} else {
			arr[++rear] = data;
		}
	}

	public char dequeue() {
		if (isEmpty()) {
			System.out.println("비어있습니다.");
			return 0;
		} else {
			char result = arr[++front];
			if (front >= this.size)
				front -= this.size;
			return result;
		}
	}

	public char peek() {
		if (isEmpty()) {
			System.out.println("비어있습니다.");
			return 0;
		} else {
			return arr[front + 1];
		}
	}

	public static void main(String[] args) {
		int size = 3;
		QueueArr queue = new QueueArr(size);
		
		queue.enqueue('A');
		System.out.println(queue.peek());		
		
		queue.enqueue('B');
		System.out.println(queue.peek());		
		
		queue.enqueue('C');
		System.out.println(queue.peek());
		
		System.out.println("dequeue : " + queue.dequeue());
		System.out.println(queue.peek());
		
		System.out.println("dequeue : " + queue.dequeue());
		System.out.println(queue.peek());
		
		System.out.println("dequeue : " + queue.dequeue());
		System.out.println(queue.peek());
		
		System.out.println("dequeue : " + queue.dequeue());
		
	}
}

원형 큐

- 큐의 처음과 끝을 연결하여 원형으로 표현하는 방법

- 선형 큐에서 queue-full 신호가 발생하면 큐에서 많은 데이터 이동이 일어날 수 있는 이동 큐의 과부하 문제를 해결함

 

특징

- 삽입, 삭제 시 포인터 값을 증가시킨 후 자료의 입출력이 이루어지며, 큐가 full인 상태에서도 하나의 빈 공간을 갖게 된다. 이 때, 하나의 빈공간은 아무 위치나 상관이 없다. 즉, 0번지는 사용하지 않는다는 표현은 틀리다.

- 하지만 원형 큐에서는 큐가 비어있는 경우와 큐가 가득 찬 경우 둘다 front = rear인 관계가 된다.

- 때문에 Overflow와 Underflow의 구별이 불가능하다. 예로 front = rear = 0일 때 큐에 n개의 자료를 연속해서 입력시키면 rear = 0이 된다. 이때 큐는 가득찬 상태이다.

 

Deque(데크, Double Ended Queue)

- 데크는 리스트의 양쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형 리스트로서, left와 right 두 개의 포인터를 갖는 데이터 구조이다.

- 큐의 개념을 확장한 구조라고 볼 수 있으며, 스택과 큐를 복합한 운영방식이다.

- 입력이 한쪽에서만 가능한 입력제한 데크를 Scroll이라 하고, 출력이 한쪽에서만 가능한 출력제한 데크를 Shelf라고 한다.