큐(Queue) : FIFO

큐(Queue)는 선입 선출(FIFO : First-In First-Out)의 형식으로 입출력이 일어나는 자료구조이다.

앞서 설명한 스택(Stack)은 동일한 위치에서 삽입, 삭제 연산이 수행되는 반면, 큐(Queue)는 삽입, 삭제 연산이 서로 다른 위치에서 수행된다.

삽입이 일어나는 곳을 후단(Rear)이라고 하고, 삭제가 일어나는 곳을 전단(Front)이라고 한다.

스택(Stack)처럼 삽입(Enqueue), 삭제(Dequeue) 2가지 기본 연산을 가지고 있다.

JAVA에선 간단하게 라이브러리를 추가하여 별다른 구현 없이 사용할 수 있으나 일반적으로 LinkedList로 생성한다.

import java.util.Queue;
import java.util.LinkedList;
Queue<"자료형"> "큐 이름" = new LinkedList<>();

 

큐(Queue) 또한 선형자료구조로써 배열(선형, 원형), 연결 리스트를 이용하여 구현할 수 있다.

배열로 구현하는 방법은 큐의 크기가 고정되는 단점이 있지만 구현이 쉽고, 데이터 접근이 빠르다. 반면, 연결 리스트로 구현하는 방법은 구현이 약간 복잡한 반면, 큐의 크기를 필요에 따라 가변적으로 변경할 수 있다.

다음은 배열로 간단하게 구현한 선형 큐(Queue)이다.

class MyQueue<T> {
	private int front, rear;
	private int queueSize;
	private T[] arr;
	
	public MyQueue(int queueSize){
		front = rear = -1;
		this.queueSize = queueSize;
		arr = (T[])new Object[queueSize];
	}
	
	public void enqueue(T data) {
		if (is_Full()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		arr[++rear] = data;
	}
	
	public T peek() {
		if (is_Empty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		return arr[front + 1];
	}
	
	public T dequeue() {
		if (is_Empty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		T ret = arr[++front];
		arr[front] = null;
		return ret;
	}
	
	public boolean is_Full() {
		if (rear + 1 == queueSize) return true;
		return false;
	}
	
	public boolean is_Empty() {
		if (rear == front) return true;
		return false;
	}
	
	public int getSize() {
		return rear - front;
	}
	
	public int getFrontElement() {
		return (int) arr[front + 1];
	}
	
	public int getBackElement() {
		return (int) arr[rear];
	}
}

구현한 큐(Queue)로 간단한 예제를 테스트한 결과는 다음과 같다.

MyQueue<Integer> q = new MyQueue<>(3);
System.out.println(q.is_Empty());
System.out.println(q.is_Full());
q.enqueue(3);
System.out.println(q.getSize());
q.enqueue(4);
q.enqueue(5);
System.out.println(q.is_Full());
System.out.println(q.getSize());
System.out.println(q.dequeue());
System.out.println(q.peek());
System.out.println(q.dequeue());
System.out.println(q.dequeue());
System.out.println(q.is_Empty());