큐(Queue)

큐란?

데이터가 입력되면 입력되는 순서대로 쌓고, 먼저 들어온 것부터 사용하는 구조.

FIFO(First In First Out)형, 선입선출형이라고도 한다.

큐에 데이터를 넣는 것을 인큐(enqueue)라고 하고, 데이터를 꺼내는 것을 디큐(dequeue)라고 한다.

데이터를 꺼내는 쪽을 프런트(front)라고 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.

 

구현 방법

배열(순환 큐) 또는 연결 리스트(링크드 큐)를 이용한다.

 

용도

운영체제는 현재 수행 중인 프로세스를 큐의 형태로 관리한다.

예를 들어 컴퓨터 안에 여러 개의 프로세스가 수행 중인데 새로운 프로세스가 수행되어야 하는 경우,

기존에 수행되던 프로세스 중 가장 먼저 메모리에 올라온 프로세스가 아웃되고 새로운 프로세스를 메모리에 올리게 된다.

또 운영체제는 수행 중인 프로그램의 이벤트도 큐의 형태로 관리한다.

예를 들어 창 닫기, 버튼 클릭, 윈도우 크기 조정의 이벤트가 발생하면 큐에 저장시키고 차례대로 처리한다.

 

자바로 구현하기

package StackAndQueue;

import StackAndQueue.IntAryQueue.EmptyIntQueueException;
import StackAndQueue.IntAryQueue.OverflowIntQueueException;

public class IntQueue {

	private int max;	//큐 용량
	private int front;	//첫 번째 요소 커서
	private int rear;	//마지막 요소 커서
	private int num;	//현재 데이터 수
	private int[] que;	//큐 본체를 참조하는 배열 변수
	
	//실행시 예외 : 큐가 비어있음.
	public class EmptyIntQueueException extends RuntimeException {
		public EmptyIntQueueException() {}
	}
	
	//실행시 예외 : 큐가 가득 차있음.
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() {}
	}
	
	//생성자
	public IntQueue(int capacity) {
		front = rear = num = 0;
		max = capacity;
		try {
			que = new int[max];
		} catch(OutOfMemoryError e) {
			max = 0;
		}
	}
	
	//enque 메소드
	public int enque(int data) throws OverflowIntQueueException {
		if(num>=max) {
			throw new OverflowIntQueueException();
		}
		que[rear++] = data;
		num++;
		if(rear == max) {
			rear = 0;
		}
		return data;
	}
	
	//deque 메소드
	public int dnque() throws EmptyIntQueueException {
		if(num<=0) {
			throw new EmptyIntQueueException();
		}
		int result = que[front++];
		num--;
		if(front == max) {
			front = 0;
		}
		return result;
	}
	
}

(indexOf, peek, clear, capacity, size, isEmpty, isFull, dump 미구현)

 

큐 자료구조는 많이 사용되기 때문에 자바에서 기본적으로 제공한다.

import java.util.*;
public class Queue {
	public static void main(String[] args) {
		LinkedList<String> ls = new LinkedList<String>();
		ls.offer("홍길동"); // 큐에 저장
		ls.offer("김동자");
		ls.offer("유명한");
		ls.offer("천세원");
		System.out.println("Size = " + ls.size());
		while(ls.peek() != null) // 읽을 값이 있는가?
		System.out.println(ls.poll()); // 값을 읽어서 출력
		System.out.println("Size = " + ls.size());
	}
}