반응형
🔗 참고자료
- 백준 문제 큐(10845번) => 링크
✍ 공부하게 된 계기
알고리즘 문제에서 큐에대한 개념이 나왔는데, 조건문을 사용하면 쉽게 해결할 수 있는 문제였습니다.
그런데 단순히 정답을 위해서 풀면 나중에 큐(Queue)관련 문제가 나올 때 제대로 풀 지 못할것 같았습니다.
그래서 좀 더 깊게 파보고 큐(Queue)를 직접 구현해보기로 했습니다.
자료구조를 공부하면서 정말 많은것을 배우고 있습니다.
- 자바의 내부함수 구조를 직접 뜯어보고 어떻게 구현되어있는지 확인하는 계기
- 단순히 자바에서 잘 구현되어있는 List를 계속 사용만 한다면 추상화되어있는 개념만 가질 수 있었을겁니다.
그런데 '한번 구현해보면 어떨까?' 라는 생각으로 인해 자료구조에 더 친해지는 계기가 되었습니다.
❓ 큐(Queue)란
- 큐는 한국어로 "대기줄" 을 뜻합니다.
=> 그래서 큐를 설명하는 강의를 보면 줄서서 기다리는 사람들을 예시로 많이 설명하는 것을 볼 수 있습니다. - 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다.
- 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼너 주을 선 사람이 먼저 나가는 것과 같습니다.
💻 구현한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
customQueue<Integer> customQueue = new customQueue<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String command = st.nextToken();
switch (command) {
case "push":
customQueue.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(customQueue.pop()).append("\n");
break;
case "size":
sb.append(customQueue.size()).append("\n");
break;
case "empty":
sb.append(customQueue.empty()).append("\n");
break;
case "front":
sb.append(customQueue.front()).append("\n");
break;
case "back":
sb.append(customQueue.back()).append("\n");
break;
}
}
System.out.println(sb);
}
}
class customQueue<T> {
transient Node<T> first;
transient Node<T> last;
int size = 0;
public void push(T e) {
final Node<T> l = last;
final Node<T> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
public String pop() {
if (size ==0) return "-1";
final Node<T> f = first;
final T element = f.item;
final Node<T> next = f.next;
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
return element.toString();
}
public int size() {
return size;
}
public int empty() {
if (size == 0) return 1;
else return 0;
}
public T front() {
if (first == null) return (T) "-1";
return first.item;
}
public T back() {
if (last == null) return (T) "-1";
return last.item;
}
private class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
반응형