[윤성우의 열혈 자료구조]큐(Queue) - 자바(Java) 구현

큐(Queue)

• 먼저 들어간 것이 먼저 나오는 자료구조
  • FIFO(First-in, First-out) 구조

• 운영체제 관점에서 보면 프로세스나 쓰레드의 관리에 활용이 되는 자료구조

• 배열 또는 연결리스트를 이용하여 구현할 수 있다. 다만 큐의 논의 주체는 배열 기반에 초점이 맞추어져 있다.(배열에서 논의할 내용이 많다.)
  • 배열기반으로 큐를 구현한다고 하면 일반적으로 원형 큐를 구현한다.
    • 단순 배열 큐(선형 큐)는 front(출구), rear(입구) 위치의 앞쪽 배열 공간을 활용하지 못한다.
    • 배열의 끝에 도달하면 다시 배열의 처음 위치로 설정하여 공간을 활용하도록 고안된 것이 원형 큐이다.
    • 배열의 마지막에 도착했을 때 배열의 처음으로 이동하는 논리적인 움직임이 원형으로 보여서 원형 큐라고 한다. 실질적으로 연결되어있는 것은 아니다.
  • 원형 큐를 구현할 때 배열의 Empty, Full 상태를 구분하기 위해 메모리 공간 1개를 상태 구분 용도로 사용한다.
    • 상태를 구분하지 못한다면 기존 데이터를 덮어 씌우거나 삭제할 데이터의 위치가 틀어질 수도 있다. 따라서 아래의 코드 구현에서는 front와 rear가 같은 위치를 가리키는 경우 Empty rear+1이 front의 위치와 같아지는 경우를 Full로 생각하여 구현하였다.

큐 자료구조의 추상 자료형(ADT)

	boolean QIsEmpty(); //큐가 비어있는지 확인하는 메소드

	void Enqueue(T data); //큐에 데이터를 저장하는 메소드

	T Dequeue(); //큐에 처음으로 저장된 요소를 삭제하는 메소드

	T QPeek(); //큐의 처음에 저장된 요소를 조회하는 메소드

배열기반 큐(원형 큐)

public class ArrayQueue<T> {

	private static final int DEFAULT_ARRAY_SIZE = 8; 
	private T[] queueArr;
	private int front;	//출구
	private int rear;	//입구
	
	public ArrayQueue(Class<T> type) {
		queueArr = (T[]) Array.newInstance(type, DEFAULT_ARRAY_SIZE);
		front = 0;
		rear = 0;
	}

	/**
	 * front, rear 위치 계산하는 메소드
	 * @param pos
	 * @return
	 */
	private int NextPosIdx(int pos) {
		if(pos == DEFAULT_ARRAY_SIZE-1) {
			return 0;
		}else {
			return pos+1;	
		}
	}
	
	/**
	 * 큐가 비어있는지 확인하는 메소드
	 */
	private boolean QIsEmpty() {
		if(front == rear)
			return true;
		
		return false;
	}

	/**
	 * 큐에 데이터를 저장하는 메소드
	 * @param data
	 */
	private void Enqueue(T data) {
		rear = NextPosIdx(rear);
		if(rear == front)
			new ArrayIndexOutOfBoundsException("Queue Memory Full!");
		
		queueArr[rear] = data;	
	}

	/**
	 * 큐에 처음으로 저장된 요소를 삭제하는 메소드
	 * @return
	 */
	private T Dequeue() {
		if(QIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Empty!");
		
		front = NextPosIdx(front); //front의 위치는 이미 삭제된 데이터로 간주한다. 따로 초기화 하지 않음 
		return queueArr[front];
	}

	/**
	 * 큐의 마지막에 저장된 요소를 조회하는 메소드
	 * @return
	 */
	private T QPeek() {
		if(QIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Error!");
		
		int rIdx = NextPosIdx(front);
		return queueArr[rIdx];
	}
	
	public static void main(String[] args) {
		// Queue의 생성 및 초기화 ///////
		ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(Integer.class);
		
		// 데이터 넣기 ///////
		arrayQueue.Enqueue(1);
		arrayQueue.Enqueue(2);
		arrayQueue.Enqueue(3);  
		arrayQueue.Enqueue(4);
		arrayQueue.Enqueue(5);

		// 큐의 처음 데이터 조회 ///////
		System.out.println(arrayQueue.QPeek());
		
		// 데이터 꺼내기 ///////
		while(!arrayQueue.QIsEmpty())
			System.out.printf("%d ", arrayQueue.Dequeue()); 
	}
}

 

배열기반 큐(선형 큐, 원형 큐) 비교

• 둘 다 배열의 특징을 가진다.
• 선형 큐
  • 배열의 공간이 남아있음에도 공간을 활용하지 못하는 단점이 있다.
• 원형 큐
  • 선형 큐의 문제를 보완하여 메모리의 모든 공간을 활용할 수 있지만, 그럼에도 메모리 공간 1개를 상태 구분 용도로 사용하여 메모리 손실이 있다.

---

연결리스트기반 큐

public class LinkedListQueue<T> {

	private Node front;	//출구(머리, 삭제)
	private Node rear;	//입구(꼬리, 삽입)
	
	//노드를 표현한 클래스
	private class Node{
		private T data;
		private Node nextLink;
		
		private Node(T data) {
			this.data = data;
			this.nextLink = null;
		}
	}
		
	public LinkedListQueue() {
		front = null;
		rear = null;
	}

	/**
	 * 큐가 비어있는지 확인하는 메소드
	 */
	private boolean QIsEmpty() {
		if(front == null)
			return true;
		
		return false;
	}

	/**
	 * 큐에 데이터를 저장하는 메소드
	 * @param data
	 */
	private void Enqueue(T data) {
		Node newNode = new Node(data);
		
		if(QIsEmpty()) {
			front = newNode;
			rear = newNode;
		}else {
			rear.nextLink = newNode;
			rear = newNode;
		}
	}

	/**
	 * 큐에 처음으로 저장된 요소를 삭제하는 메소드
	 * @return
	 */
	private T Dequeue() {
		if(QIsEmpty()) {
			new ArrayIndexOutOfBoundsException("Queue Memory Empty!");
		}
		Node rNode = front;
		front = front.nextLink;
		
		return rNode.data;
	}

	/**
	 * 큐의 마지막에 저장된 요소를 조회하는 메소드
	 * @return
	 */
	private T QPeek() {
		if(QIsEmpty()) {
			new ArrayIndexOutOfBoundsException("Queue Memory Empty!");
		}
		Node rNode = front;
		
		return rNode.data;
	}
	
	public static void main(String[] args) {
		// Queue의 생성 및 초기화 ///////
		LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
		
		// 데이터 넣기 ///////
		linkedListQueue.Enqueue(1);
		linkedListQueue.Enqueue(2);
		linkedListQueue.Enqueue(3);  
		linkedListQueue.Enqueue(4);
		linkedListQueue.Enqueue(5);

		// 큐의 처음 데이터 조회 ///////
		System.out.printf("%d ", linkedListQueue.QPeek());
		System.out.printf("%d \n", linkedListQueue.QPeek());
		
		// 큐의 데이터 삭제(꺼내기) ///////
		System.out.printf("%d ", linkedListQueue.Dequeue());
		System.out.printf("%d \n", linkedListQueue.Dequeue());
		
		// 남은 데이터 삭제(꺼내기) ///////
		while(!linkedListQueue.QIsEmpty())
			System.out.printf("%d ", linkedListQueue.Dequeue()); 
	}
}

---

[참고자료]

윤성우의 열혈 자료구조