Queue의 특징
큐는 선입선출(First in First out: FIFO)의 특징을 갖는 자료구조이다.
선입선출이란 '먼저 들어온 것이 먼저 나간다'라는 의미이다.
놀이기구를 타기 위해 여러 명이 줄을 서 있다고 가정해보자.
첫 번째로 줄에서 벗어나 놀이기구를 탈 사람은 첫 번째로 줄을 선 사람일 것이다.
줄에 먼저 들어온 사람이 먼저 줄을 나가는 것이다. 이것이 선입선출이다.
큐는 이러한 선입선출의 원칙으로 데이터를 관리한다.
큐는 주로 대기열을 구현하기 위해 사용된다.
Queue의 구현 방법
큐는 배열 또는 연결리스트를 통해 구현할 수 있으며, 주로 연결리스트를 통해 구현한다.
그 이유는 연결리스트를 통해 구현하는 것이 더 쉽고 편하기 때문이다.
배열로 큐를 구현하는 경우 아래와 같은 불편함이 있다.
- 저장될 요소의 개수에 따라 배열의 크기를 동적으로 조정해주는 작업이 필요하다.
- 요소의 추가/삭제가 반복되면 요소들의 위치가 배열의 뒤로 쏠리는 현상이 발생한다. 따라서 요소들의 위치를 조정해주기 위한 작업이 필요하다.
Queue 구현
인터페이스를 통해 큐의 메소드를 정의하고, 배열과 연결리스트를 통해 구현해보도록 하겠다.
실제 사용 코드에서는 연결리스트로 구현한 큐를 사용할 것이며, 배열로 구현한 큐 또한 사용 방법은 동일하다.
Queue 인터페이스
public interface QueueInterface<T> {
/**
* 큐의 맨 끝에 요소를 추가한다.
* @param element: 추가할 요소
* @return 추가 성공: true, 추가 실패: false
*/
boolean offer(T element);
/**
* 큐의 맨 앞 요소를 제거하고 반환한다.
* @return 큐의 맨 앞 요소
*/
T poll();
/**
* 큐의 맨 앞 요소를 반환한다.
* @return 큐의 맨 앞 요소
*/
T peek();
/**
* 큐의 맨 앞 요소를 제거하고 반환한다.
* 요소가 없을 경우 예외 발생 <- poll()과 차이점
* @return 큐의 맨 앞 요소
*/
T remove();
/**
* 큐의 맨 앞 요소를 반환한다.
* 요소가 없을 경우 예외 발생 <- peek()와 차이점
* @return 큐의 맨 앞 요소
*/
T element();
}
ArrayQueue 구현부
public class ArrayQueue<T> implements QueueInterface<T> {
private static final int DEFAULT_CAPACITY = 64; // 기본 용적 크기
private T[] array; // 저장 공간
private int size; // 요소 개수
private int front; // 시작 인덱스(항상 빈 공간 <- 큐가 비어있는지를 확인하기 위함)
private int rear; // 마지막 요소의 인덱스
// 용적 크기 0
@SuppressWarnings("unchecked")
public ArrayQueue() {
this.array = (T[]) new Object[0];
this.size = 0;
this.front = 0;
this.rear = 0;
}
// 용적 크기: capacity
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) {
this.array = (T[]) new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
@SuppressWarnings("unchecked")
private void resize() {
int arrayCapacity = array.length;
// 저장 공간 0
if (arrayCapacity == 0) {
array = (T[]) new Object[DEFAULT_CAPACITY];
return;
}
// 저장 공간이 가득 찬 경우
if ((rear + 1) % arrayCapacity == front) {
T[] newArray = (T[]) new Object[arrayCapacity * 2];
copyArray(arrayCapacity, newArray);
}
// 저장 공간/2 > 요소 개수
if (size < (arrayCapacity/2)) {
T[] newArray = (T[]) new Object[Math.max(arrayCapacity / 2, DEFAULT_CAPACITY)];
copyArray(arrayCapacity, newArray);
}
}
// 큐 맨 끝에 데이터 추가
@Override
public boolean offer(T element) {
resize();
rear = (rear + 1) % array.length;
array[rear] = element;
size++;
return true;
}
// 맨 앞 요소를 제거하고 반환
@Override
public T poll() {
if (size == 0) {
return null;
}
front = (front + 1) % array.length;
T element = array[front];
array[front] = null;
size--;
resize();
return element;
}
// 맨 앞 요소를 반환
@Override
public T peek() {
if (size == 0) {
return null;
}
return array[(front + 1) % array.length];
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- poll()과 차이
public T remove() {
if (size == 0) {
throw new NoSuchElementException();
}
return poll();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peak()와 차이
public T element() {
if (size == 0) {
throw new NoSuchElementException();
}
return peek();
}
private void copyArray(int arrayCapacity, T[] newArray) {
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = newArray;
front = 0;
rear = size;
}
// 요소 개수 반환
public int size() {
return size;
}
// 큐가 비어있는 지 여부 반환
public boolean isEmpty() {
return size == 0;
}
// 목표 요소의 저장 여부 반환
public boolean contains(T element) {
int start = (front + 1) % array.length;
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if(array[idx].equals(element)) {
return true;
}
}
return false;
}
// 큐의 모든 요소 제거
@SuppressWarnings("unchecked")
public void clear() {
this.array = (T[]) new Object[array.length];
size = 0;
front = 0;
rear = 0;
resize();
}
@Override
public String toString() {
int start = (front + 1) % array.length;
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
stringBuilder.append(" ").append(array[idx]);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
LinkedListQueue 구현부
public class LinkedListQueue<T> implements QueueInterface<T> {
private Node<T> head; // 첫 번째 노드에 대한 참조
private Node<T> tail; // 마지막 노드에 대한 참조
private int size; // 요소 개수(= head~tail의 노드 개수)
public LinkedListQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 큐 맨 끝에 요소 추가
@Override
public boolean offer(T element) {
// 추가할 새로운 노드 생성
Node<T> newNode = new Node<>(element);
// 새로운 노드가 첫 번째 노드인 경우, head가 새로운 노드를 참조
// 아닌 경우, tail.next가 새로운 노드를 참조
if (size == 0) {
head = newNode;
} else {
tail.next = newNode;
}
// tail이 새로운 노드를 참조
tail = newNode;
size++;
return true;
}
// 맨 앞 요소를 제거하고 반환
@Override
public T poll() {
// 삭제할 요소가 없는 경우, null
if (size == 0) {
return null;
}
T element = head.element; // 삭제하고 반환하려는 요소
Node<T> nextNode = head.next; // 삭제할 노드의 다음 노드
// head가 삭제할 노드의 다음 노드를 참조
head = null;
head = nextNode;
size--;
return element;
}
// 맨 앞 요소를 반환
@Override
public T peek() {
// 삭제할 요소가 없는 경우, null
if (size == 0) {
return null;
}
return head.element;
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- poll()과 차이
@Override
public T remove() {
// 요소가 없을 경우 예외 발생
if (size == 0) {
throw new NoSuchElementException();
}
return poll();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peak()와 차이
@Override
public T element() {
// 요소가 없을 경우 예외 발생
if (size == 0) {
throw new NoSuchElementException();
}
return peek();
}
// 요소 개수를 반환
public int size() {
return size;
}
// 큐가 비어있는 지 여부를 반환
public boolean isEmpty() {
return size == 0;
}
// 목표 요소가 저장되어있는 지 여부 반환
public boolean contains(T element) {
// head부터 순회하면서 요소를 가진 노드가 있는지 확인
for (Node<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
return true;
}
}
return false;
}
// 큐의 모든 요소를 제거한다.
public void clear() {
for (Node<T> x = head; x != null;) {
Node<T> next = x.next;
x.element = null;
x.next = null;
x = next;
}
size = 0;
head = null;
tail = null;
}
// toString() 오버라이딩
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (Node<T> x = head; x != null; x = x.next) {
stringBuilder.append(" ").append(x.element);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
실제 사용
public class Main {
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for (int i = 0; i < 25; i++) {
queue.offer(i + 1);
}
System.out.println("queue = " + queue);
// queue = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ]
///////////////////////////////////////////////////////////////////////
int peek = queue.peek();
System.out.println("peek = " + peek); // peek = 1
System.out.println("queue = " + queue); // queue = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ]
///////////////////////////////////////////////////////////////////////
int pop = queue.poll();
System.out.println("poll = " + pop); // poll = 1
System.out.println("queue = " + queue); // queue = [ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ]
///////////////////////////////////////////////////////////////////////
System.out.println("queue.empty() = " + queue.isEmpty()); // queue.empty() = false
queue.clear();
System.out.println("queue.empty() = " + queue.isEmpty()); // queue.empty() = true
}
}