[알고리즘] Queue 개념 + java.util.Queue

 

 

 큐 (Queue) 

개념

큐 란?
: First In First Out 의 특징을 가지고 있는 선형적 자료구조

맛집에 가서 줄을 설 때를 생각하시면 됩니다.

먼저 들어온 사람이 제일 먼저 처리가 되고, 그 이후로 줄줄이 처리가 됩니다.

이러한 데이터 처리의 구조를 가진 자료구조를 큐 라고 합니다.

 

특징

큐는 선입선출(FIFO: First In First Out) 의 특징을 가지고 있습니다.

보통 BFS 를 구현할 때 많이들 사용됩니다.

또한, 제일 첫 요소를 나타내는 front 와 제일 마지막 요소를 나타내는 rear 라는 인덱스 키워드를 가지고 있습니다.

스택과 마찬가지로 연결 리스트로 구현될 수 있습니다.

 

 

 

 Java Queue API - LinkedList 클래스 사용 

Stack 과는 다르게도 Queue 는 인터페이스 입니다. Collection 을 extends 합니다.

인터페이스이기 때문에 직접적인 구현부가 없어 Queue의 구현체로 LinkedList 를 사용해야 합니다.

add: 큐에 요소를 넣음 (boolean 값 반환: 성공하면 true 아니면 false)
element: front 요소를 확인
offer: 큐에 요소를 넣음
peek: front 요소를 확인
poll: 큐에 front 요소를 삭제함
remove: 큐에 front 요소를 삭제함 (boolean 값 반환: 성공하면 true 아니면 false)

Collection 의 연산을 사용할 수 있습니다.

 

enqueue

package day220804.practice;


import java.util.LinkedList;
import java.util.Queue;


public class QueueTest {
	static Queue<Integer> queue = new LinkedList<>();


	public static void main(String[] args) {
		// 삽입 연산 
		queue.add(3);
		queue.add(1);
		queue.offer(2);

		System.out.println(queue);
	}

}

add() 와 offer() 메서드를 이용하여 삽입 연산을 수행할 수 있습니다.

Collection 연산을 사용할 수 있기 때문에 add 연산을 쓰는 것을 권장합니다. (왜냐면 기억하기 쉬우니까)

 

dequeue

package day220804.practice;


import java.util.LinkedList;
import java.util.Queue;


public class QueueTest {
	static Queue<Integer> queue = new LinkedList<>();


	public static void main(String[] args) {
		// 삽입 연산
		queue.add(3);
		queue.add(1);
		queue.offer(2);

		System.out.println(queue);

		// 삭제 연산
		queue.remove(2);
		System.out.println(queue);

		queue.poll();
		System.out.println(queue);
	}

}

remove() 메서드를 이용하면 특정 요소를 삭제할 수 있습니다. Collection 에서 사용하는 것 처럼요.

하지만 poll() 메서드를 이용하면 제일 위에 있는 요소가 삭제됩니다.

 

peek

package day220804.practice;


import java.util.LinkedList;
import java.util.Queue;


public class QueueTest {
	static Queue<Integer> queue = new LinkedList<>();


	public static void main(String[] args) {
		// 삽입 연산
		queue.add(3);
		queue.add(1);
		queue.offer(2);

		System.out.println(queue);

		// top 확 연산
		System.out.println(queue.element());
		System.out.println(queue.peek());
	}

}

front 에 있는 요소를 반환합니다. 제일 위에 있는 요소를 element() 와 peek() 메서드를 이용하여 확인할 수 있습니다.

 

isEmpty

package day220804.practice;


import java.util.LinkedList;
import java.util.Queue;


public class QueueTest {
	static Queue<Integer> queue = new LinkedList<>();


	public static void main(String[] args) {
		// 삽입 연산
		queue.add(3);
		queue.add(1);
		queue.offer(2);

		System.out.println(queue);

		// 비었는지 아닌지 확인
		System.out.println(queue.isEmpty());

		// 모두 삭제
		queue.clear();

		System.out.println(queue);

		// 비었는지 아닌지 확인
		System.out.println(queue.isEmpty());

	}

}

Collection 의 isEmpty() 연산을 통해 큐가 비었는지 아닌지 확인할 수 있습니다.

 

 

 

 Java Queue API - ArrayDeque 클래스 사용 

package day220804.practice;


import java.util.ArrayDeque;
import java.util.Queue;


public class QueueTest {
	// static Queue<Integer> queue = new LinkedList<>();
	static Queue<Integer> queue = new ArrayDeque<>();


	public static void main(String[] args) {
		// 삽입 연산
		queue.add(3);
		queue.add(1);
		queue.offer(2);

		System.out.println(queue);

		// 비었는지 아닌지 확인
		System.out.println(queue.isEmpty());

		// 모두 삭제
		queue.clear();

		System.out.println(queue);

		// 비었는지 아닌지 확인
		System.out.println(queue.isEmpty());

	}

}

ArrayDeque 도 Queue 의 구현부로 사용할 수 있습니다.

LinkedList 보다 성능이 좋다고 하니 이를 사용하는 것을 권장드립니다.

 

 

 

 

 

 

 

 

# java queue # 알고리즘 큐

---