백준 18258번 | 큐 2 문제 풀이 (Java)

문제

 

제출 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        Deque<String> queue = new ArrayDeque<>();

        for(int i = 0; i < N; i++) {
            String[] command = br.readLine().split(" ");

            switch(command[0]) {
                case "push":
                    queue.addLast(command[1]);
                    break;
                case "pop":
                    bw.append(queue.isEmpty() ? "-1\n" : queue.pollFirst()+"\n");
                    break;
                case "size":
                    bw.append(queue.size()+"\n");
                    break;
                case "empty":
                    bw.append(queue.isEmpty() ? "1\n" : "0\n");
                    break;
                case "front":
                    bw.append(queue.isEmpty() ? "-1\n" : queue.peekFirst() + "\n");
                    break;
                case "back":
                    bw.append(queue.isEmpty() ? "-1\n" : queue.peekLast() + "\n");
                    break;
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

 

자바 ArrayDeque 내부로직

 

ArrayDeque는 원형배열 기반

 

초기 생성자

1. 내부 배열 크기 17로 초기화

Object[] elements;
int head;
int tail;

public CustomArrayDeque() {
    this.elements = new Object[[17];
}

 

 

push 로직

 

addLast(tail을 증가 시키면서 뒤쪽에 추가)

1. e == null이면 NPE 발생

2. tail 위치에 요소 추가

3. inc 의해 tail 증가

4. 배열이 가득 찼을 경우(this.head = inc()) grow 의해 크기 확장

public void addLast(E e) {
    if (e == null) {
        throw new NullPointerException();
    } else {
        Object[] es = this.elements;
        es[this.tail] = e;
        if (this.head == (this.tail = inc(this.tail, es.length))) {
            this.grow(1);
        }

    }
}

static final int inc(int i, int modulus) {
    ++i;
    if (i >= modulus) {
        i = 0;
    }

    return i;
}

 

 

addFirst(head를 감소 시키면서 값을 앞쪽을 추가)

1. e == null이면 NPE 발생

2. dec 의해 head 감소 후 요소 삽입

3. 배열이 가득 찼을 경우(this.head = this.tail) grow 의해 크기 확장

public void addFirst(E e) {
    if (e == null) {
        throw new NullPointerException();
    } else {
        Object[] es = this.elements;
        es[this.head = dec(this.head, es.length)] = e;
        if (this.head == this.tail) {
            this.grow(1);
        }

    }
}

static final int dec(int i, int modulus) {
    --i;
    if (i < 0) {
        i = modulus - 1;
    }

    return i;
}

 

 

pop

 

pollFirst(head값 출력 후 head값 증가)

1. head값 e에 저장

2. 값이 있을 경우 head 위치 값 null(GC) head값 증가

public E pollFirst() {
    Object[] es;
    int h;
    E e = (E)elementAt(es = this.elements, h = this.head);
    if (e != null) {
        es[h] = null;
        this.head = inc(h, es.length);
    }

    return e;
}

static final <E> E elementAt(Object[] es, int i) {
    return (E)es[i];
}

 

 

pollLast(tail값 감소 후 tail값 출력)

1. tail 값 감소(dec(this.tail, es.length)

2. tail값 e에 저장

3. e값이 있을 경우 tail 위치 null(GC)

public E pollLast() {
    Object[] es;
    int t;
    E e = (E)elementAt(es = this.elements, t = dec(this.tail, es.length));
    if (e != null) {
        es[this.tail = t] = null;
    }

    return e;
}

 

size

1. this.tail: 데이터 삽입될 위치(마지막 원소의 다음 인덱스)

2. this.head: 데이터가 제거될 위치(첫 번째 원소의 인덱스)

3. this.elements.length: 버퍼 배열의 크기

4. i-j 음수 일 경우 버퍼 크기 더함

public int size() {
    return sub(this.tail, this.head, this.elements.length);
}
    
static final int sub(int i, int j, int modulus) {
    if ((i = i - j) < 0) {
        i += modulus;
    }

    return i;
}

 

isEmpty

public boolean isEmpty() {
    return this.head == this.tail;
}

 

문제 의도

- 큐의 기본 동작 이해

 

문제 출처