큐(Queue)

 

 

 

큐의 구조

 

📌 큐(Queue)

컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In, First Out)구조로 저장하는 형식을 말한다.

 

큐는 프로그래밍에서 가장 많이 쓰는 자료구조 중 하나이다. FIFO(First-in, First-Out) 구조 혹은 LILO(Last In, Last Out) 구조라고 부르기도 한다. 예를 들면 음식점에서 가장 먼저 줄을 선 사람이 가장 먼저 음식점에 입장하는 것과 동일하다고 보면 된다. 가장 먼저 넣은 데이터를 가장 먼저 뺀다.

 

✔️ 큐의 용어

용어	뜻	비유	자바
Enqueue	큐에 데이터를 넣는 기능	손님에게 번호표를 발부	add(value), offer(value)
Dequeue	큐에서 데이터를 꺼내는 기능	창구에서 서비스를 받은 손님의 번호표를 삭제	poll(), remove(), clear()
Front	큐의 맨 앞의 위치(인덱스)	다음 서비스를 받을 손님의 번호	0번 인덱스
Rear	큐의 맨 뒤의 위치(인덱스)	마지막에 온 손님의 번호	Quque.size() - 1
Peek	front에 위치한 데이터를 읽음	다음 서비스를 받을 손님이 누구인지 확인	peek(), element()

✔️ 큐의 활용 

큐는 주로 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용된다.

• 서로 다른 쓰레드 사이 또는 프로세스 사이에서 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용
• 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 프로세스를 대기시킬 때 사용

 

✔️ 특수한 형태의 큐

• 원형 큐 (Circular Queue)
• 우선순위 큐(Priority Queue)
• DEQ (Deque, Double Ended Queue)

 

✔️ 큐의 간단한 구현

public class ImplQueue<T> {
	// LinkedList로도 변경가능
	private ArrayList<T> queue = new ArrayList<T>();
    
    public void enqueue(T item) {
    	queue.add(item);
    }
    
    public T dequeue() {
    	if(queue.isEmpty()) {
        	return null
        }
        return queue.remove(0);
    }
    
    public T peek() {
    	if(queue.isEmpty()) {
        	return null;
        }
        return queue.get(0);
    }
    
    public boolean isEmpty() {
    	return queue.isEmpty();
    }
    
    public static void main(String[] args) {
    	ImplQueue<Integer> implQue = new ImplQueue<>();
        
        implQue.enqueue(1);
        implQue.enqueue(2);
        implQue.enqueue(3);
        System.out.println(implQue.dequeue());
        System.out.println(implQue.dequeue());
        System.out.println(implQue.dequeue());
    }
}