[자료구조] Queue 개념과 Java 구현

Queue란?

스택과 마찬가지로 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식으로 스택과는 반대로 가장 먼저 들어온 데이터가 먼저 나가는 구조(FIFO, First In First Out)를 가진 자료구조이다. 버스 정류장에서 버스를 타기 위해 줄을 서면 먼저 온 사람이 먼저 버스를 타는 과정을 생각하면 된다. 

 

큐의 예로는 이메일 전달 혹은 푸쉬 알림 기능 그리고 전화 온 순서대로 상담을 처리하는 콜센터를 생각할 수 있다. 

 

Java에서 제공하고 있는 Queue는 인터페이스이고 Queue interface를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다. 보통은 자바에서 다음과 같이 사용한다.

Queue<Integer> q = new LinkedList<>();

 

주요 기능

1. offer(e), add(e) : 맨 끝에다가 큐에 값을 집어넣는다.

2. poll(), remove() : 맨 앞의 데이터를 삭제하고 삭제한 값을 반환한다.

3. peek(), element() : 맨 앞의 데이터를 반환한다.

4. isEmpty() : 큐가 비어있는지 확인한다.

 

Java로 구현하기

LinkedList로 구현하기

1. 같은 타입을 받는 Node를 선언한다. Node는 자기 자신의 데이터 값과 다음 노드의 주소 값인 next을 가진다. 생성자에서 data를 받아서 내부 변수에 저장한다.

class Queue<T> {
	class Node<T> {
    	private T data;
        private Node<T> next;
        
        public Node(T input) {
        	this.data = input;
            this.next = null;
        }
    }
}

 

 

2.  Queue는 앞뒤로 주소를 알고 있어야 하니까 front와 rear라는 멤버 변수를 선언한다.

class Queue<T> {
	...
    private Node<T> front;
    private Node<T> rear;
}

 

 

3. 추가하는 add(T item) 함수를 추가한다. 추가하려는 노드를 새로 생성해주고 만약 마지막 노드가 있다면 마지막 노드 뒤에 새로 생성한 노드를 붙이고 데이터가 없으면 첫 번째 노드가 null이기 첫 번째 노드 자리에 추가하려는 노드를 할당한다.

class Queue<T> {
	...
	public void add(T item) {
    	Node<T> toAddNode = new Node<T>(item);
        if (rear != null) {
        	rear.next = toAddNode;
        }
        rear = toAddNode;
        if (front == null) {
        	front = rear;
        }
    }
    
}

 

 

4. remove()를 구현해 보자. front가 null일 때 예외 처리를 해주고 가장 첫 데이터를 삭제 하기 위에 삭제할 데이터를 백업해주고 그 후에 front 노드에 다음 노드를 할당해준다. 만약 유일한 데이터였다면 rear 노드도 null 처리를 해주고 삭제한 데이터를 반환한다.

class Queue<T> {
	...
    public T poll() {
    	if (front == null) {
        	throw new NoSuchElementException();
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
        	rear = null;
        }
        return data;
    }
}

 

5. peek()을 구현해 보자. 만약 front가 null이라면 예외 처리를 해주고 만약 데이터가 있다면 간단하게 front.data를 반환한다.

class Queue<T> {
	...
    public T peek() {
    	if (front == null) {
        	throw new NoSuchElementException();
        }
    	return front.data;
    }
}

 

6. isEmpty()를 구현해 보자. 간단히 첫 번째 노드가 null 인지를 반환한다.

class Queue<T> {
	...
   	public boolean isEmpty() {
    	return front == null;
    }
}

 

 

Array로 구현하기

문제점

Array로 큐를 구현하면 위의 그림과 같이 쏠림 현상이 발생하는데 인덱스를 계속 해서 앞으로 당기거나 뒤로 밀면 비효율적이고 이 상태에서 배열 크기를 늘리면 빈 공간을 그대로 두고 계속해서 배열 크기만 커지기 때문에 메모리를 낭비하게 된다. 그렇다면 어떻게 이 문제를 어떻게 해결해야 할까?

 

그건 바로 앞의 빈 메모리 공간을 채워주는 것이다. 배열을 선형이 아닌 원형(환형)이라고 가정해보자!

이러한 구조를 보통 Circular Queue, 원형 큐라고 한다. rear를 따라서 데이터가 추가되고 front를 따라서 데이터가 삭제된다. 더 이상 빈 자리가 없을 경우에만 배열의 크기를 늘려주면 되니까 메모리의 낭비가 없다. front가 가장 먼저 추가된 데이터의 인덱스 자리가 아닌 그 앞 자리에 위치한 이유는 한 자리를 비워둬야 아무런 데이터가 없을 때 front == rear의 상태가 되고 이를 통해서 큐가 비어있는 상태라는 걸 알 수 있기 때문이다.

 

아직은 혼자 구현하기에 너무 헷갈려서 내가 좋아하는 블로거님의 블로그에서 구현한 코드를 따라해보기로 했다. 

전체 코드는 이 곳에서 확인 가능합니다.

자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기

 

구현 예제

1. 클래스 및 생성자 구성하기

public class ArrayQueue<E> implements Queue<E> {
	
    private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기
    
    private Object[] arry; 
    private int size;
    
    private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
    private int rear; // 마지막 요소의 인덱스를 가리키는 변수
    
    // 생성자1 (초기 용적 할당을 안 할 경우)
    public ArrayQueue() {
    	this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.front = 0;
        this.rear = 0;
    }
    
    // 생성자2 (초기 용적 할당을 할 경우)
    public ArrayQueue(int capacity) {
    	this.array = new Object[capacity];
        this.size = 0;
        this.front = 0;
        this.rear = 0;
    }
}

 

 

2. 동적 할당을 위한 resize 메소드 구현

size가 capacity에 얼마만큼 차있는지를 확인하고 적절한 크기에 맞게 용적을 변경할 때 사용하는 메소드이다. 용적은 외부에서 접근하면 데이터의 손상이 생길 수 있기 때문에 private 접근제어자를 사용한다.

private void resize(int newCapacity) {
	
    int arrayCapacity = array.length; // 현재 용적 크기
    
    Objectp[] newArray = new Object[newCapacity]; // 용적을 변경한 배열
    
    for (int i = 1; j = front + 1; i <= size; i++, j++) {
    	newArray[i] = array[j % arrayCapacity];
    }
    this.array = null;
    this.array = newArray; 
    
    front = 0;
    rear = size;
}

- 용적이 가득 차면 rear의 다음 인덱스(rear + 1)는 front와 같다.

- front + 1번 째의 인덱스부터 데이터가 저장되니까 j는 front + 1이 되고 계속해서 증감연산식을 사용하면 배열 크기보다 더 인덱스가 진행되니까 나머지 연산자를 사용해서 다시 인덱스가 0으로 돌아가게 해준다.

- 그래야 새로운 배열의 첫 번째 인덱스에 front + 1 인덱스 값을 넣을 수 있다.

 

 

3. offer 메소드 구현

public boolean offer(E item) {
	// 용적이 가득 찼을 경우
    if ((rear + 1) % array.length == front) {
    	resize(array.length * 2); 
    }
    
    rear = (rear + 1) % array.length; // rear를 rear의 다음 위치로 갱신
    array[rear] = item;
    size++;
    
    return true;
}

 

4. poll 메소드 구현

public E poll() {
	if (size == 0) {
    	return null;
    }
    
    front = (front + 1) % array.length; // front를 한 칸 옮긴다.
    
    @SuppressWarnings("unchecked")
    E item = (E) array[front]; // 반환 데이터 임시 저장
    
    array[front] = null;
    size--;
    
    // 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
	if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
			
		// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다. 
		resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
	}
		
	return item;
}

- Object -> E 타입으로 변환 할 때 변환할 수 없는 타입일 수 있다는 경고로 메소드 옆에 경고 표시가 뜨는데 지금은 E 타입만 존재하기 때문에 형 안정성이 보장되어 이 경고들을 무시하겠다는 의미로 @SuppressWarnings("unchecked")를 사용했다.

 

 

4. peek() 메소드 구현

public E peek() {
	if (size == 0) { return null; }
    
    @SuppressWarnings("unchecked")
    E item = (E) array[(front + 1) % array.length];
    return item;
}

 

 

 

- 개발자라면 무조건 알아야하는 자료구조!

- [자료구조 알고리즘] Queue 구현하기 in Java

- 자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기