큐(Queue)는 (연결 리스트와 스택과 유사하게) 데이터를 저장하는 데이터 구조이다. 큐에서는 데이터가 도착하는 순서가 중요하다. 일반적으로 큐는 사람들이나 물건들이 한 줄로 서서 차례를 기다리는 것과 비슷하다.
정의: 큐는 데이터의 삽입이 한쪽 끝(뒤, rear)에서 이루어지고 삭제는 다른 쪽 끝(앞, front)에서 이루어지는 정렬된 리스트이다. 가장 처음 삽입된 항목이 맨 먼저 삭제된다(FIFO)
스택에서처럼 큐는 두 가지 동작의 종류가 있다. 항목이 큐에 삽입될 때, 인큐(EnQueue)라고 하고, 항목이 큐로부터 제거될 때, 디큐(DeQueue)라고 한다. 빈 큐로부터 디큐하려고 하는 것을 언더플로우(underflow)라고 부르고, 꽉 찬 큐에 항목을 인큐하려고 하는 것을 오버플로우(overflow)라고 하는데, 일반적으로 예외로 처리된다.
- 큐는 어떻게 사용되는가?
큐는 데이터의 순서를 유지해야 할 필요가 있는 경우에 매우 유용하다.
- 큐 ADT
큐의 주된 연산들
EnQueue(int data): 큐의 가장 끝에 항목을 삽입한다.
int DeQueue(): 큐의 가장 앞의 항목을 제거하고 리턴한다.
큐의 보조 연산들
int Front(): 큐의 가장 앞에 있는 항목을 제거하지 않고 리턴한다.
int QueueSize(): 저장된 항목의 개수를 리턴한다.
int IsEmptyQueue(): 저장된 항목이 없는지를 나타낸다.
- 예외들
다른 ADT들과 유사하게 빈 큐에 대하여 디큐하려고 시도하면 '빈 큐 예외(Empty Queue Exception)'가 발생하고, 꽉 찬 큐에 인큐하려고 하면 '꽉찬 큐 예외(Full Queue Exception)' 가 발생한다.
- 큐의 구현
간단한 원형 배열에 기초한 구현
동적 원형 배열에 기초한 구현
연결 리스트 구현
왜 원형 배열인가?
먼저, 스택에서 사용했던 것처럼 단순한 배열을 사용할 수 있는지 살펴보자. 큐의 삽입은 한쪽 끝에서, 삭제는 다른 쪽 끝에서 이루어진다는 것을 알고 있다. 그런데 몇 번의 삽입과 삭제 연산 뒤에 다음 그림과 같은 상황에 처하는 경우가 많다.
 |
| (배열의 앞쪽 공간이 낭비되는 현상) |
이 문제는 원형 배열로 해결할 수 있는데, 원형 배열은 마지막 항목과 첫 번째 항목이 연결되는 형태이다. 이를 이용하여 앞쪽에 빈 공간이 있으면 뒤(rear)포인터가 다음 빈 공간으로 쉽게 이동할 수 있다.
간단한 원형 배열 구현
public class ArrayQueue {
private int front;
private int rear;
private int capacity;
private [] array;
private ArrayQueue(int size) {
capacity = size;
front = -1;
rear = -1;
array = new int [size];
}
public static ArrayQueue createQueue(int size) {
return new ArrayQueue(size);
}
public boolean isEmpty() {
return (front == -1);
}
public boolean isFull() {
return ((rear + 1) % capacity == front);
}
public int getQueueSize() {
return ((capacity - front + rear + 1)%capacity);
}
public void enQueue(int data) {
if(isFull()) {
throw new QueueOverflowException("Queue Overflow");
}else{
rear = (rear + 1) % capacity;
array[rear] = data;
if(front == -1) {
front = rear;
}
}
}
public int deQueue() {
int data = null;
if(isEmpty()) {
throw new EmptyQueueException("Queue Empty");
}else{
data = array[front];
if(front == rear) {
front =rear - 1;
}else{
front = (front+1)%capacity;
}
}
return data;
}
}
- 성능과 한계
동적 원형 배열 구현
public class DynArrayQueue extends Queue {
private int front;
private int rear;
private int capacity;
private int[] array;
private DynarrayQueue() {
capacity = 1;
front = -1;
rear = -1;
array =new int[1];
}
public static DynArrayQueue createDynArrayQueue() {
return new DynArrayQueue();
}
public boolean isEmpty() {
return (front == -1);
}
private boolean isFull() {
return ((rear + 1) % capacity == front);
}
public int getQueueSize() {
if(front == -1) return 0;
int size = (capacity - front + rear + 1) % capacity;
if(size == 0) {
return capacity;
}else return size;
}
private void resizeQueue() {
int initCapacity = capacity;
capacity *= 2;
int[] oldArray = array;
array = new int[this.capacity];
for(int i=0; i<oldArray.length;i++) {
array[i] = oldArray[i];
}
if(rear < front) {
for(int i=0; i<front; i++) {
array[i+initCapacity] = this.array[i];
array[i] = null;
}
rear = rear + initCapacity;
}
}
public void enQueue(int data) {
public void enQueue(int data) {
if(isFull()) resizeQueue();
rear = (rear + 1) % capacity;
array[rear] = data;
if(front == -1) front = rear;
}
public int deQueue() {
int data = null;
if(isEmpty()) throw new EmptyQueueException("Queue Empty");
else { data = array[front];
if(front == rear) front = rear = -1;
else front = (front + 1) % capacity;
}
return data;
}
}
성능
연결 리스트 구현
public class LLQueue extends Queue {
private LLNode frontNode;
private LLNode rearNode;
private LLQueue() {
this.frontNode = null;
this.rearNode = null;
}
public static LLQueue createQueue(){
return new LLQueue();
}
public boolean isEmpty() {
return (frontNode == null);
}
public void enQueue(int data) {
LLNode newNode = new LLNode(data);
if(rearNode != null) {
rearNode.setNext(newNode);
}
rearNode = newNode;
if(frontNode == null) {
frontNode = rearNode;
}
}
public int deQueue() {
int data = null;
if(isEmpty()) {
throw new EmptyQueueException("Queue Empty");
}else{
data = frontNode.getData();
frontNode = frontNode.getNext();
}
return data;
}
}
성능
댓글 없음:
댓글 쓰기