알고리즘
-
큐 라이브러리를 사용할 경우 Java에서는 가장 맨 뒤에 있는 요소를 반환하는 메소드가 없음
-
LinkedList 방식을 이용하여 구현할 것임
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Queue_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Deque<Integer> Dq = new LinkedList<>();
int N = Integer.parseInt(br.readLine());
StringTokenizer command;
while(N--> 0){
command = new StringTokenizer(br.readLine()," "); //문자열 분리
switch (command.nextToken()){
case "push":
Dq.offer(Integer.parseInt(command.nextToken()));
break;
case "pop":
Integer item = Dq.poll();
if (item == null){
sb.append(-1).append('\n');
}
else {
sb.append(item).append('\n');
}
break;
case "size":
sb.append(Dq.size()).append('\n');
break;
case "empty":
if(Dq.isEmpty()) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
break;
case "front":
// peek()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
Integer ite = Dq.peek();
if(ite == null) {
sb.append(-1).append('\n');
}
else {
sb.append(ite).append('\n');
}
break;
case "back":
// peekLast()은 큐에 꺼낼 요소가 없을 경우 null을 반환한다.
Integer it = Dq.peekLast();
if(it == null) {
sb.append(-1).append('\n');
}
else {
sb.append(it).append('\n');
}
break;
}
}
System.out.println(sb);
}
}
-
StringTokenizer는 엔터를 입력할 경우 종료되기 때문에 while 루프를 반복할 때 마다 새로운 입력을 받아줘야 한다.
-
이 코드에서는 큐를 구현하기 위헤 Java에서 제공하는 'Deque' 인터페이스를 사용하고 있다. 여기서 Deque는 Double Ended Queue의 줄임말이다. 큐의 양 끝에서 요소의 추가 및 제거가 가능한 자료구조를 의미한다.
-
Deque 를 구현한 클래스로 LinkedList를 선택하여 큐를 구현하고 있는 것이다. 큐라는 형태는 여러가지 클래스로 구현될 수 있다. LinkedList , ArrayDeque , Priority 등등..
-
LinkedList 는 요소의 삽입 및 삭제가 양쪽 끝에서 모두 상수 시간O(1)에 이루어진다는 장점이 있지만 인덱스를 기반으로 접근하는 것이 아니기 때문에 임의의 위치에 있는 요소에 접근하는데 선형 시간이 소요된다 O(n) 그리고 포인터를 사용하여 각 요소를 연결하기 때문에 추가적인 메모리 오버헤드가 발생할 수 있음
-
ArrayDeque는 배열을 기반으로 하여 인덱스를 통한 빠른 요소의 접근이 가능하다. 뿐만 아니라 요소의 삽입 및 삭제가 양쪽 끝에서 모두 상수 시간 O(1) 에 이루어지고 배열을 사용하기 떄문에 메모리 할당과 복사에 대한 오버헤드가 적다
하지만, 크기가 동적으로 조절되기 때문에 크기를 동적으로 조절할 때 배열을 복사하는 오버헤드가 발생할 수 있음
- 즉 여기서 Queue 인터페이스를 사용하지 않은 이유는 case "back" 명령어를 처리할 수 없기 때문임
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Queue_2_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Deque<Integer> Dq = new LinkedList<>();
int N = Integer.parseInt(br.readLine());
StringTokenizer command;
while (N-- > 0) {
command = new StringTokenizer(br.readLine(), " "); // 문자열 분리
switch (command.nextToken()) {
case "push":
Dq.offer(Integer.parseInt(command.nextToken()));
break;
case "pop":
sb.append(Dq.isEmpty() ? -1 : Dq.pop()).append('\n');
break;
case "size":
sb.append(Dq.size()).append('\n');
break;
case "empty":
sb.append(Dq.isEmpty() ? 1 : 0).append('\n');
break;
case "front":
sb.append(Dq.isEmpty() ? -1 : Dq.peek()).append('\n');
break;
case "back":
sb.append(Dq.isEmpty() ? -1 : Dq.peekLast()).append('\n');
break;
}
}
System.out.println(sb);
}
}
- 코드를 수정하여 가독성을 높임
