public interface Queue<E> {
/**
* 큐가 비어있는지 확인합니다
*/
boolean isEmpty();
/**
* 큐가 가득 찼는지 확인합니다
*/
boolean isFull();
/**
* 큐에 저장된 현재 원소의 수를 반환합니다.
*/
int size();
/**
* 큐의 삭제(dequeue)가 발생하는 지점인 front에 존재하는 원소를 반환합니다.
*/
E front();
/**
* 큐의 삽입(enqueue)가 발생하는 지점인 front에 존재하는 원소를 반환합니다.
*/
E rear();
/**
* offer를 수행합니다.
* 큐에 요소를 삽입합니다.
* (== EnQueue)
*/
boolean offer(E item);
/**
* poll을 수행합니다.
* 큐에 가장 마지막에 들어간 원소를 큐에서 제거한 뒤 반환합니다.
* 원소가 없다면 null을 반환합니다.
* (== DeQueue)
*/
E poll();
/**
* peek를 수행합니다.
* 큐에 가장 마지막에 들어간 원소를 큐에서 제거하지 않고 반환합니다.
* 원소가 없다면 null을 반환합니다.
*/
E peek();
/**
* 큐을 비웁니다.
*/
void clear();
}
LinkedNode 구현
내부적으로 사용할 Node를 다음과 같이 구현하겠습니다.
public class LinkedNode <E> {
private E element;
private LinkedNode<E> next;
public LinkedNode(E item) {
this.element = item;
}
public E element() {
return this.element;
}
public void setNext(LinkedNode<E> next) {
this.next = next;
}
public LinkedNode<E> next() {
return this.next;
}
}
LinkedQueue의 front와 rear를 설정하는 방식
LinkedNode를 사용하여 Queue를 구현할 때, front와 rear를 어떻게 설정하느냐에 따라 효율이 달라집니다.
front를 Node의 가장 마지막으로 설정한 경우
삽입 시에는 빠르게 동작합니다. 삭제 시에는 front 노드의 이전 노드를 찾기 위해 선형 탐색을 해야 하므로 오랜 시간이 걸립니다.
front를 Node의 가장 처음으로 설정한 경우
삽입 시에는 기존 rear 노드의 next에 새로운 노드를 지정한 후, rear을 새로운 노드로 변경하여주면 되므로 빠른 연산이 가능합니다. 삭제 시에는 기존 front의 next를 새로운 front로 변경해주면 되므로 빠른 연산이 가능합니다.
즉 결론적으로 front를 LinkedNode의 가장 처음 노드로,
rear를 가장 마지막 노드로 설정해 주면 효율적입니다.
LinkedQueue<E> 전체 구현 코드
public class LinkedQueue <E> implements Queue<E>{
private int size;
private LinkedNode<E> front;
private LinkedNode<E> rear;
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return false;
}
@Override
public int size() {
return this.size;
}
@Override
public E front() {
if (front == null) return null;
return front.element();
}
@Override
public E rear() {
if (rear == null) return null;
return rear.element();
}
@Override
public boolean offer(E item) {
LinkedNode<E> newRearNode = new LinkedNode<>(item);
if(isEmpty()) {
this.front = newRearNode;
}
else {
rear.setNext(newRearNode);//현재 rear 다음에 새로운 노드 추가
}
this.rear = newRearNode;//새로운 노드를 rear로 set
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) return null;
E remove = this.front.element();//front가 null일 수도 있으나, 이는 isEmpty로 처리
this.front = this.front.next();
if(this.front == null) {
this.rear = null;
}
size--;
return remove;
}
@Override
public E peek() {
if (isEmpty()) return null;
return front.element();
}
@Override
public void clear() {
this.size = 0;
this.front = null;
this.rear = null;
}
}
세부 구현
LinkedQueue<E>의 필드
public class LinkedQueue <E> implements Queue<E>{
private int size;
private LinkedNode<E> front;
private LinkedNode<E> rear;
rear와 front를 null로 바꾸어주면 참조를 잃은 기존의 노드들은 GC가 알아서 수거합니다.
ArrayQueue<E>의 삽입과 삭제
@Override
public boolean offer(E item) {
LinkedNode<E> newRearNode = new LinkedNode<>(item);
if(isEmpty()) {
this.front = newRearNode;
}
else {
rear.setNext(newRearNode);//현재 rear 다음에 새로운 노드 추가
}
this.rear = newRearNode;//새로운 노드를 rear로 set
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) return null;
E remove = this.front.element();//front가 null일 수도 있으나, 이는 isEmpty로 처리
this.front = this.front.next();
if(this.front == null) {
this.rear = null;
}
size--;
return remove;
}
@Override
public E peek() {
if (isEmpty()) return null;
return front.element();
}
큐가 비어있지 않다면 기존 rear의 위치에 있는 노드의 다음 노드를 새로운 노드로 설정해줍니다. 이후 rear을 새로운 노드로 설정합니다.
poll(): 큐에 가장 먼저 들어온 원소를 제거하여 반환합니다.
제거할 때에는 front를 기존 front의 next로 설정하여줍니다.
이후 새롭게 설정된 front가 비어있다는 것은 Queue가 비어있다는 것이므로 현재 설정되어있는 rear도 지워줍니다.
테스트코드
public class Test {
public static void main(String[] args) {
LinkedQueue<Integer> queue = new LinkedQueue<>();
IntStream.rangeClosed(0, 9).forEach(queue::offer);
IntStream.rangeClosed(0, 9).forEach( i -> System.out.println(queue.poll()));
}
}
