[자료구조][Java] 큐 (Queue)

1. 큐 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 같음
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택(Stack)과 꺼내는 순서가 반대이다.

2. 큐에서 사용하는 용어

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능 (먼저 들어간게 먼저 나온다.)

 

3. Java에서 큐(Queue) 사용하기

• Java에서는 기본적으로  java.util 패키지에 Queue 클래스를 제공하고 있다.
  • Enqueue에 해당하는 기능으로 Queue 클래스에서는 add(value) 또는 offer(value) 메서드를 제공
  • Dequeue에 해당하는 기능으로 Queue 클래스에서는 poll()또는 remove()메서드를 제공
• 큐(Queue) 클래스 사용해보기

// Queue 사용을 위해 , LinkedList 클래스를 사용하므로, 두 클래스 모두 import 해야 한다.
import java.util.LinkedList;
import java.util.Queue;

// 자료형 매개변수를 넣어서, 큐에 들어갈 데이터의 타입을 지정해야 함
Queue<Integer> queue_int = new LinkedList<Integer>(); // Integer형 Queue 선언
Queue<String> queue_str = new LinkedList<String>(); // String형 Queue 선언

 

• 큐에 데이터 추가하기 (Enqueue)

// 데이터 추가는 add(value) 또는 offer(value) 를 사용함
queue_int.add(1);
queue_int.offer(2);

 

• 큐의 데이터 삭제하기 (Dequeue)

// poll()과 remove()는 큐의 첫 번째 값을 반환한뒤 해당 값을 삭제한다.
queue_int.poll();
queue_int.remove();

 

4. ArrayList로 Queue 구현하기

import java.util.ArrayList;

public class MyQueue<T> {

	private ArrayList<T> queue = new ArrayList<T>();
	
	public void enqueue(T item) {
		queue.add(item);
	}
	
	public T dequeue() {
		if (queue.isEmpty()) {
			return null;
		} else
		return queue.remove(0);
	}
	
	public static void main(String[] args) {
    // 테스트 코드
		MyQueue<Integer> mq = new MyQueue<Integer>();
		mq.enqueue(1);
		mq.enqueue(2);
		mq.enqueue(3);
		System.out.println(mq.dequeue());
		System.out.println(mq.dequeue());
		System.out.println(mq.dequeue());
		
	}

}