Queue(큐)의 개념
- 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식
- Stack(스택)과 반대되는 개념
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
Queue(큐)의 종류
- 선형(큐)
- 크기 제한
- 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮김
- 원형(큐)
- 선형 큐의 문제점을 보완
- front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식
Queue(큐)의 메소드
배열을 이용한 큐
- getSize() : 큐의 크기를 반환
- isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
- isFull() : 큐가 가득 차있으면 true, 그렇지 않으면 false 반환
- enqueue() : ((rear+1) % size)번째 인덱스에 데이터 추가
- dequeue() : ((front+1) % size)번째 인덱스의 데이터 반환
- toString() : 큐의 모든 데이터를 반환
- clear() : 큐의 모든 데이터를 삭제
연결리스트를 이용한 큐
- isEmpty() : 큐가 비어있으면 true, 비어있지 않으면 false 반환
- enqueue() : 큐가 비어있으면 새로운 노드를 front와 rear로 선언, 비어있지 않으면 새로운 노드를 rear 노드의 next로 선언한 후 새로운 노드를 rear로 선언
- dequeue() : front 노드의 데이터 반환 후 front 노드의 next를 front 노드로 선언
- toString() : 큐의 모든 데이터를 반환
- clear() : 큐의 모든 데이터를 삭제
배열을 이용한 (원형)큐
ArrayQueue.java
package array.queue;
public class ArrayQueue {
private final int DEFAULT_SIZE = 100000;
private int front = 0;
private int rear = 0;
private Object [] data;
public ArrayQueue() {
data = new Object [DEFAULT_SIZE];
}
public ArrayQueue(int size) {
if(size > 0) {
data = new Object [size+1];
} else {
throw new ArrayIndexOutOfBoundsException();
}
}
public int getSize() {
return this.data.length;
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return rear+1 % getSize() == front;
}
public void enqueue(Object input) {
if(isFull()) {
throw new ArrayIndexOutOfBoundsException();
} else {
data[++rear % getSize()] = input;
}
}
public Object dequeue() {
if(isEmpty()) {
throw new NullPointerException();
} else {
return data[++front % getSize()];
}
}
public String toString() {
String str = new String("[ ");
if(isEmpty()) {
return str + "]";
} else {
for (int i = front+1; i != (rear+1) % getSize(); i = (i+1) % getSize()) {
str += data[i] + " ";
}
return str + "]";
}
}
public void clear() {
for (int i = front+1; i != (rear+1) % getSize(); i = (i+1) % getSize()) {
data[i] = null;
}
front = 0;
rear = 0;
}
}연결리스트를 이용한 큐
LinkedListQueue.java
package linkedlist.queue;
public class LinkedListQueue {
private QueueNode front = null;
private QueueNode rear = null;
private class QueueNode {
private Object data;
private QueueNode next;
public QueueNode(Object input) {
data = input;
next = null;
}
public Object getData() {
return this.data;
}
}
public boolean isEmpty() {
return front == null;
}
public void enqueue(Object input) {
QueueNode newNode = new QueueNode(input);
if(isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
}
public Object dequeue() {
if(isEmpty()) {
throw new NullPointerException();
} else {
Object dequeueData = front.data;
front = front.next;
return dequeueData;
}
}
public String toString() {
String str = new String("[");
if(isEmpty()) {
return str + "]";
} else {
QueueNode tmp = front;
while(tmp.next != null) {
str += tmp.getData() +", ";
tmp = tmp.next;
}
return str + tmp.getData() + "]";
}
}
public void clear() {
front = null;
rear = null;
}
}