[백준] 10845 : 큐 (JAVA)

백준 10845 자바

큐를 잘 모른다면??

https://songsunkite.tistory.com/entry/자바-큐란-큐-자바-구현-QUEUE

큐 LinkedList 사용

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

Queue 선언

import java.util.LinkedList;//importimport 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 반환

---

큐 성공

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

0.5 초 (추가 시간 없음)

256 MB

87919

39668

31031

48.936%

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

---

방법1. 큐 크래스 사용

package Day1109;

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

class Stack {

	private int max; // 스택 용량
	private int ptr;// 스택 포인터
	private int[] stk; // 스택본체

	// 생성자
	public Stack(int capacity) {
		ptr = 0;// 생성 시 스택은 비어있으므로
		max = capacity;
		try {
			stk = new int[max]; // 스택 본체용 배열 생성
		} catch (OutOfMemoryError e) { // 생성할 수 없음
			max = 0;
		}
	}

	// push X: 정수 X를 스택에 넣는 연산이다.
	public int push(int x) {
		// 전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
		return stk[ptr++] = x;
	}

	// pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
	// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
	public int pop() {
		if (ptr <= 0)
			return -1;
		return stk[--ptr];
	}

	// size: 스택에 들어있는 정수의 개수를 출력한다.
	public int size() {
		return ptr;
	}

	// empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
	public int empty() {
		if (ptr <= 0)
			return 1;
		return 0;
	}

	// top: 스택의 가장 위에 있는 정수를 출력한다.
	// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
	public int top() {
		if (ptr <= 0)
			return -1;
		return stk[ptr - 1];
	}
}

public class B10828_1 {
	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());
		Stack s = new Stack(N);

		StringTokenizer st;

		// 명령어 수만큼 반복.
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			// 출력해야하는 명령
			String order = st.nextToken();

			switch (order) {
			case "push":
				s.push(Integer.parseInt(st.nextToken()));
				break;

			case "pop":
				sb.append(s.pop()).append("\\n");
				break;

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

			case "empty":
				sb.append(s.empty()).append("\\n");
				break;

			case "top":
				sb.append(s.top()).append("\\n");
				break;

			}
		}
		System.out.println(sb);
	}
}