[자료구조] 큐 Queue [Java]

Queue

큐는 FIFO(First In First Out)형태를 가진 자료구조이다. 후입선출 구조인 stack과 반대라고 생각하면 된다.

 

Enqueue : 큐 뒤에 데이터를 추가

Dequeue : 큐 앞쪽의 데이터를 삭제

 

Java의 Queue interface

stack은 클래스로 구현해서 제공하지만 큐는 Queue 인터페이스만 있고 별도의 클래스가 없다.

따라서 Queue 인터페이스를 구현한 클래스를 사용해야한다.

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

Queue (Java Platform SE 8 )

자바 공식 도큐먼트에 큐를 구현한 클래스들이 나와있다. 이중에서 가장 많이 사용해본건 LinkedList와 ArrayDeque, PriorityQueue

 

Queue의 method

public interface Queue<E> extends Collection<E> {
	boolean add(E e);
	boolean offer(E e);
	E remove();
	E poll();
	E element();
	E peek();
}

 

Queue의 인터페이스를 살펴보면 위와 같다.

• 데이터 입력

• add와 offer는 둘다 데이터를 삽입하는 메서드이다.
• interface의 주석에 따르면 offer는 용량이 제한된 큐에 사용되고 add보다 권장된다고 한다.
• offer()는 큐가 꽉 차 있을때 추가를 시도하면 false가 반환된다.
• add()는 큐가 꽉 차 있을대 IllegalStateException이 발생된다.

• 데이터 삭제

• remove와 poll은 데이터를 삭제하는 메서드이다.
• remove의 경우 큐가 비어있으면 NoSuchElementException이 발생하고 poll은 큐가 비어있다면 null을 반환한다.

• 데이터 열람

• element와 peek은 데이터를 반환하지만 삭제하지는 않는다.
• element의 경우 remove와 같이 큐가 비어있다면 NoSuchElementException 이 발생되고 peek은 큐가 비었다면 null을 반환한다.

 

직접 구현해보기

리스트로 큐를 구현해보았다. 먼저 큐의 인터페이스를 생성해주었다.

public interface GyungminQueue<E> {
	boolean queueIsEmpty();
	boolean queueIsFull();
	int size();
	void enqueue(E value);
	E peek();
	E dequeue();
}

queueIsEmpty() : 큐가 비었는지 확인한다.

queueIsFull() : 큐가 꽉 차있는지 확인한다.

size() 큐의 사이즈를 반환한다.

enqueue(E value) : 큐에 데이터를 넣는다.

peek() : 큐의 맨 앞에 있는 데이터를 반환한다.

dequeue() : 큐의 맨 앞에 있는 데이터를 삭제한다.

 

이제 위의 인터페이스를 구현하는 클래스를 만든다.

import java.util.ArrayList;
import java.util.List;

public class GyungminQueueImpl<E> implements GyungminQueue<E> {

	final static int MAX_SIZE = 10;
	int size;
	List<E> queue;
	
	public GyungminQueueImpl() {
		this.size = 0;
		this.queue = new ArrayList<E>();
	}

	@Override
	public boolean queueIsEmpty() {
		if(size == 0) return true;
		return false;
	}

	@Override
	public boolean queueIsFull() {
		if(size == MAX_SIZE) return true;
		return false;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public void enqueue(E value) {
		if(queueIsFull()) {
			throw new IllegalStateException("Queue is full");
		}
		else {
			queue.add(value);
			size++; 
		}
		
	}

	@Override
	public E peek() {
		if(queueIsEmpty()) {
			throw new IllegalStateException("Queue is empty");
			
		}
		else {
			 return queue.get(0);
		}
	}

	@Override
	public E dequeue() {
		if(queueIsEmpty()) {
			throw new IllegalStateException("Queue is empty");
			
		}
		else {
			E result = queue.get(0);
			queue.remove(0);
			size--;
			return result;
		}
	}

}

테스트를 위해서 MAX_SIZE를 10으로 작게 설정해주었다.

queueIsEmpty() , queueIsFull()를 이용해서 enqueue, dequeue, peek과정에서 IllegalStateException을 던져주었다.

 

이를 테스트 해본 함수다.

public class GyungminQueueTest {

	public static void main(String[] args) {
		GyungminQueue<Integer> queue = new GyungminQueueImpl<>();
		for(int n = 1; n <= 10; n++) {
			queue.enqueue(n);
		}
//		queue.enqueue(11);
		System.out.println("queue peek() test " + queue.peek());
		for(int n = 1; n <= 10; n++) {
			System.out.println("queue dequeue() test " + queue.dequeue());
		}
        System.out.println("now queue size: " + queue.size());
//		queue.dequeue();
//		System.out.println(queue.peek());

	}

}

10까지 데이터를 넣어주고 뒤에 11번째 데이터를 삽입하려고 시도하면?

이렇게 Exception이 발생하는 것을 확인할 수 있다.

 

peek()과 dequeue() 테스트를 해보면 다음과 같이 정상 출력된다.

 

dequeue가 10번 되어 사이즈가 0인상태에서 다시한번 dequeue를 시도하면

Exception이 발생된다.

 

마찬가지로 queue의 사이즈가 0일때 peek을 시도해도 위와같이 Exception이 발생함을 확인할 수 있다.