자바 큐란? - 큐 자바 구현 (QUEUE)

큐(QUEUE)란?

📌 큐의 개념

Queue 의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것을 의미한다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이

선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.

📌 큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때 삭제연산만 수행되는 곳을 프론트(front), **삽입연산만 이루어지는 곳을 리어(rear)**로 정하여

각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)

프론트에서 이루어지는 삭제연산을 **디큐(dnQueue)**라고 부른다.

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며,

리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

📌 큐의 활용 예시

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

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

---

방법1 . 큐 LinkedList 사용

Queue<Integer> queue = new LinkedList<>(); 사용

Queue 선언

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

자바에서 큐는 LinkedList를 활용하여 생성해야 합니다. 그렇기에 Queue와 LinkedList가 다 import되어 있어야 사용이 가능합니다. Queue<Element> queue = new LinkedList<>()와 같이 선언해주면 됩니다.

Queue 값 추가

Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가

1. add()

• 해당 큐 맨 뒤에 값 삽입
• 값 추가 성공 시 true 반환
• 큐가 꽉 찬 경우 IllegalStateException 에러 발생

2. offer()

• 해당 큐 맨 뒤에 값 삽입
• 값 추가 성공 시 true 반환
• 값 추가 실패 시 false 반환

큐에 데이터를 추가하는 동작으로 offer 와 add 메소드가 있다.

두 메소드의 차이점은 공간의 제약이 있는 큐(Queue) 구현체에서 발생한다.

// 큐가 꽉차있는 경우
offer(value) : false 반환
add(value) : IllegalStateException 발생

사이즈 제약이 있는 큐를 사용하는 경우는 offer 메소드의 사용을 더 권장한다.

Queue 값 삭제

queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

1. remove()

• 큐 맨 앞에 있는 값 반환 후 삭제
• 큐가 비어 있는 경우 NoSuchElementException 에러 발생

2. poll()

• 큐 맨 앞에 있는 값 반환 후 삭제
• 큐가 비어있을 경우 null 반환

3. clear

• 큐 비우기

Queue 에서 가장 먼저 들어간 값 출력

q.element();
q.peek();

1. element()

• 큐의 맨 앞에 있는 값 반환
• 큐가 비어 있는 경우 NoSuchElementException 에러 발생

2. peek()

• 큐의 맨 앞에 있는 값 반환
• 비어있을 경우 null 반환

방법2. 큐 배열로 만들기

생성자 만들기

package chap05;

public class IntQueue {
	private int max; // 큐의 용량
	private int front; // 첫 번째 요소 커서
	private int rear; // 마지막 요소 커서
	private int num; // 현재 데이터 수
	private int[] que; // 큐본체

	// 생성자
	public IntQueue(int capacity) {
		num = front = rear = 0;
		max = capacity;
		try {
			que = new int[max];
		} catch (OutOfMemoryError e) {
			max = 0;
		}
	}

	public static void main(String[] args) {

	}

}

인큐메서드 enque (데이터 삽입)

// 인큐에 성공하면 인큐한 값 그대로 반환
	// 큐가 가득차서 인큐할 수 없으면 -1 반환
	public int enque(int x) {
		if (num >= max)
			return -1;
		que[rear++] = x;
		num++;
		//rear값을 1만큼 증가했을 때 큐의 최대 용량인 max와 같아지면
		//rear의 배열의 처음인 0으로 변경
		if (rear == max)
			rear = 0;
		return x; //인큐한 값 반환
	}

디큐 메서드 deque (데이터 삭제)

// 큐에서 데이터 디큐
	// 큐가 비어있어 디큐할 수 없으면 -1 반환
	public int deque() {
		if (num <= 0)
			return -1;
		int x = que[front++]; //저장된 값 꺼내고 커서 위치 1증가
		num--; //하나 꺼냈으니 총 용량인 num 하나 감소
		
		// 디큐하기 전의 front가 배열의 끝이면 과정 거치고 배열 마지막 요소 초과함
		// front의 배열의 처음인 0으로 변경
		if (front == max)
			rear = 0;
		return x; // 인큐한 값 반환
	}

검색메서드 indexOf

// 찾고자 하는 x 데이터의 인덱스 반환
	public int indexOf(int x) {
		for (int i = 0; i < num; i++) {
			int idx = (i + front) % max;

			if (que[idx] == x) {
				return idx;
			}
		}
		return -1; // 검색 실패
	}

int idx = (i + front) % max;

→ 스캔의 시작이 배열의 첫 요소가 아니라 큐의 첫 요소, 즉 프런트이다.

큐 비우기 clear

// 큐 비우기
	public void clear() {
		num = front = rear = 0;
	}

큐 용량 반환 capacity

// 큐 용량 반환
	public int capacity() {
		return max;
	}

큐에 쌓여있는 데이터 수 반환 size

// 큐에 쌓여있는 데이터 수 반환
	public int size() {
		return num;
	}

큐가 비었는지 확인 isEmpty

// 큐가 비어있나요?
public boolean isEmpty() {
		return num <= 0;
	}

큐가 가득 찼는지 확인 isFull

// 큐가 가득 찼나요>
	public boolean isFull() {
		return num >= max;
	}

큐 모든 데이터 출력 - 덤프(선입선출) dump

// 큐 안의 모든 데이터 출력(선입선출
	public void dump() {
		if (num <= 0)
			System.out.println("큐가 비어있습니다.");
		else {
			for (int i = 0; i < num; i++) {
				System.out.print(que[(i + front) % max] + " ");
				System.out.println();
			}
		}

📌 백준 10845 자바

큐 클래스 사용

package Day1109;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B10845 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		Queue<Integer> queue = new LinkedList<>();
		int rear = 0;

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			String order = st.nextToken();

			switch (order) {
			case "push":
				rear = Integer.parseInt(st.nextToken());
				queue.offer(rear);
				break;

			case "pop":
				sb.append(queue.isEmpty() ? -1 : queue.poll()).append("\\n");
				break;

			case "size":
				sb.append(queue.size()).append("\\n");
				break;

			case "empty":
				sb.append(queue.isEmpty() ? 1 : 0).append("\\n");
				break;

			case "front":
				sb.append(queue.isEmpty() ? -1 : queue.peek()).append("\\n");
				break;

			case "back":
				sb.append(queue.isEmpty() ? -1 : rear).append("\\n");
				break;
			}
		}
		System.out.println(sb);

	}

}