[Java] Queue 직접 구현해보기

🔗 참고자료

• 백준 문제 큐(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;
        }
    }
}