자료구조 선형 큐 (Linear Queue) 자바로 구현
1. 개요
큐는 대표적인 자료구조중 하나로, 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출, FIFO
(First In First Out) 형태의 자료구조다.
활용방법으로는
- 프린터 출력 (가장 먼저 대기열에 오른 프린트를 먼저 실행)
- 대기열, 대기표 (먼저 신청한 사람이 먼저 업무를 봄)
- 순서가 보장된 처리를 제공
- 사용자가 몰린 서버에 유
기능으로는
- offer() : 데이터 삽입
- poll() : 데이터 빼기
- peek() : 데이터를 뽑지 않고, 큐 안에서 가장 먼저 들어온 데이터 확인
2. 구현
package queue;
public interface IQueue<T> {
void offer(T data);
T poll();
T peek();
int size();
void clear();
boolean isEmpty();
}
package queue;
public class MyLinkedQueue<T> implements IQueue<T> {
// 노드 기반 큐
private Node head;
private Node tail;
private int size;
public MyLinkedQueue() {
this.size = 0;
this.head = new Node(null);
this.tail = this.head; // head의 레퍼런스를 집어넣었으니 tail에서
// 다른 레퍼런스를 집어넣기 전까진, head를 조작하는 것과 같다.
}
@Override
public void offer(T data) {
Node node = new Node(data);
this.tail.next = node;
this.tail = this.tail.next;
this.size++;
}
@Override
public T poll() {
if (this.isEmpty()) {
throw new IllegalStateException();
}
Node node = this.head.next;
this.head.next = node.next;
node.next = null;
this.size--;
if (this.head.next == null) {
this.tail = this.head;
}
return node.data;
}
@Override
public T peek() {
if (this.isEmpty()) {
throw new IllegalStateException();
}
return this.head.next.data;
}
@Override
public int size() {
return this.size;
}
@Override
public void clear() {
this.head.next = null;
this.tail = head;
this.size = 0;
}
@Override
public boolean isEmpty() {
return this.head.next == null;
}
private class Node {
T data;
Node next;
Node(T data) { this.data = data; }
Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
}
3. 설명
3-1. 노드 구성
data (데이터를 가지는 변수), next (다음 노드, 포인터의 역할)
인수로 data만 넣으면 노드에 데이터만 대입, data와 노드를 넣으면 노드에 데이터와 다음 노드를 대입한다.
3-2. 멤버 변수(Member Variable), 생성자(constructor)
선형 큐를 편하게 구현하려면, 데이터가 들어가지 않는 head와 tail이라는 노드가 필요하다.
그리고 큐의 크기를 나타내는 size가 있다.
인스턴스 생성 시, 생성자에서 size는 0, head에 빈 노드를 집어넣고, tail에 head를 집어넣는다.
자바에선 인스턴스 생성 시, 변수에 그 레퍼런스 주소가 들어가니, head와 tail은 같은 메모리 주소를
보고 있다.
3-3. offer()
데이터를 삽입하는 메소드다.
데이터를 집어넣기 위해, 인수로 들어온 데이터를 대입한 노드를 생성한다.
데이터가 없는 상태에선, tail은 head와 같으므로, this.tail.next = node 로 대입하면, head와 tail의 next는
데이터가 들어간 새로운 노드가 된다.
tail에 tail.next를 대입하게 되면, tail의 next는 새로운 노드이니, head는 그대로, tail은 새로운 노드가 된다.
정리하면
head(null, newNode1), tail(newNode1.data, null), newNode1(data, null);
한번 더 데이터가 들어오게 되면, 데이터가 들어간 2번째 노드가 생성되고, tail은 지금 newNode1이니, newNode1
의 next는 2번째 노드가 된다.
tail에 tail.next를 대입하면, tail은 2번째 노드가 되고, 정리하면
head(null, newNode1), tail(newNode2.data, null), newNode1(data, newNode2), newNode2(data,
null) 의 상태가 된다.
3-4. isEmpty()
큐에 데이터가 들어가 있나 확인하는 메소드다.
생성자에서 head의 next를 설정하지 않았으니, 데이터가 들어오지 않았으면 head.next는 null이고, true를
반환한다. 데이터가 있으면 head.next가 null이 아니므로, false를 반환한다.
3-5. poll()
큐에서 가장 먼저 들어온 데이터를 가져오고, 그 데이터를 큐에서 삭제하는 메소드다.
우선 큐가 비어있으면, 꺼낼 데이터가 없으니, isEmpty() 메소드로 확인하고, 없으면 에러를 발생시킨다.
데이터가 있으면, 데이터를 꺼내기 위해 새로운 노드를 생성하고, 가장 먼저 들어온 데이터가 있는, head.next
의 레퍼런스 주소를 대입한다.
가장 먼저 들어온 데이터 외에 데이터가 있다면, 가장 먼저 들어온 노드의 next에 저장되어 있으니, head.next
를 그걸로 바꿔준다.
그리고, 데이터를 꺼낼 노드의 next를 null로 바꿔주면, 이 메소드가 끝나게 되면, 이 노드를 참조하는 변수는 아무것도
없으니, 자바의 GC(Garbage Collector)에 의해 없어지게 된다.
데이터를 가진 노드가 하나 사라졌으니 사이즈를 1 줄여주고, 만약 데이터를 가진 노드가 없다면, offer() 메소드의
작업을 하기 위해, 생성자와 같이, this.tail = this.head의 형태로 레퍼런스를 대입한다.
그리고, 가장 먼저 들어온 노드의 데이터를 반환하고, 메소드가 끝나게 된다.
3-6. peek()
poll() 메소드와 다르게, 가장 먼저 들어온 노드를 삭제하지 않고, 노드의 데이터만 반환받는 메소드다.
만약, 큐가 비었으면 에러를 일으킨다. 그게 아니라면 head.next는 가장 먼저 들어온 데이터가 들어간 노드이니,
그 데이터를 반환하고 메소드가 종료된다.
3-7. size()
큐의 사이즈를 반환하는 메소드다.
3-8. clear()
큐 안에 데이터가 있는 노드를 모두 삭제하는 메소드다.
head.next에 가장 먼저 들어온 데이터를 가진 노드가 있고, 그 노드부터 다른 노드로 이어져 있는 큐인데,
가장 먼저 들어온 노드의 참조를 null로 끊고, 마지막 데이터가 있는 tail을, 데이터와 포인터가 모두 비어있는
head로 초기화하면서, 데이터가 있는 노드들은 GC에 의해 삭제되고, 큐에는 빈 노드인 head와 tail만 남는다.
데이터가 들어간 노드가 없으니 사이즈에 0을 대입하고 메소드가 종료된다.