자료구조-큐 문제

문제풀이

자료구조 중 FIFO구조인 큐의 기본적인 동작들을 구현하는 문제로 Queue 클래스를 사용하면 쉽게 풀 수 있는 문제였다.

큐(Queue)란?

큐(Queue)는 기본 자료구조 중 하나로, 줄을 지어 순서대로 처리하는 자료구조이다. 큐는 LIFO(Last-in First-out)구조를 가진 스택(Stack)과는 다르게 FIFO(First-in First-out)구조를 가진다. 즉, 먼저 들어온 데이터가 먼제 나가는 구조이다.

큐(Queue)의 특징

• 먼저 들어간 데이터가 먼저 나간다. FIFO구조
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능하다.
• 프로세스 관리, 우선순위가 같은 작업 예약에 활용된다.
• 그래프의 너비 우선 탐색(BFS)에서 사용된다.

큐(Queue)클래스의 사용법

Queue<Integer> que = new LinkedList<>();

큐(Queue)의 연산

큐(Queue)는 오버플로우(Overflow)나 언더플로우(Underflow)가 발생하면 예외를 던지거나 null 또는 false를 반환하는 메소드들이 있다.

1. 예외를 던지는 메소드

• add(A) : A를 큐(Queue)에 넣는다.
• remove() : 맨 처음에 들어간 데이터를 제거한다.
• element() : 큐(Queue)에서 가장 앞에 있는 것을 반환한다.

2. null 또는 false를 반환하는 메소드

• offer(A) : A를 큐(Queue)에 넣는다.
• poll() : 맨 처음에 들어간 데이터를 제거한다.
• peek() : 큐(Queue)에서 가장 앞에 있는 것을 반환한다.

소스 코드

package data_structure;

import java.util.;
import java.io.;

public class queue {

public static void main(String[] args) throws IOException{
	// TODO Auto-generated method stub
	Queue<Integer> que = new LinkedList<>();
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	
	int n = Integer.parseInt(br.readLine());
	int input = 0;
	for(int i=0; i<n; i++) {
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		String str = st.nextToken();
		
		switch(str) {
		
		case "push":
			input = Integer.parseInt(st.nextToken());
			que.offer(input);
			break;
		case "pop":
			sb.append(que.isEmpty() ?  -1 : que.poll()).append("\n");
			break;
		case "size":
			sb.append(que.size()).append("\n");
			break;
		case "empty":
			sb.append(que.isEmpty() ?  1 : 0).append("\n");
			break;
		case "front":
			sb.append(que.isEmpty() ?  -1 : que.peek()).append("\n");
			break;
		case "back":
			sb.append(que.isEmpty() ?  -1 : input).append("\n");
			break;
		}
		
	}
	System.out.print(sb);
}

}

문제를 풀고 느낀점

• 스택과 다르게 FIFO구조를 가진 큐에 대해 공부하는 시간을 가지게 되었고, 큐 클래스를 이용하여 문제를 풀 수 있는 기본 구조를 배워 잘 활용할 수 있을 것 같다.