4회 테코테코

 

---

≣ 목차

---

요약

Queue

내부 동작 방식 (배열 기반) - 선형 Queue

Integer.MAX_VALUE 에서 -8 을 빼서 default 사용한다. (메모리 안정성 때문인가??) 

 

선형 Queue 문제점: 메모리 낭비 -> 원형 큐 사용

초기 front, rear 값은 모두 -1이다.

 

1. isFull 을 통해 data[max_size] 와 크기를 비교한다. 꽉찬 경우, false 를 반환한다.

2. offer 를 해서 data 에 값을 넣는다. + rear 값을 1 증가 시킨다.

3. poll 할 경우 front 값을 1 증가 시킨다. (데이터가 삭제되지 않는다.)

4. offer == poll 인 경우 isEmpty 가 true 이다.

---

Queue

문제

10845번: 큐

https://www.acmicpc.net/problem/10845

접근 방법

- 라이브러리를 사용하지 않고 배열을 선형 큐로 만들어서 직접 구현해보자

고민 포인트

- 배열의 크기를 얼마나 잡아야 하지?

최종 코드 및 회고

- 처음에 rear + 1 로 size 를 계산해서 정확한 값이 출력되지 않았었다.

- size 를 변수로 따로 관리해서 문제를 해결할 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static final int MAX_SIZE = 10000;
    static int front = -1, rear = -1;
    static int length = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[] data = new int[MAX_SIZE];

        for (int i = 0; i < size; i++) {
            String[] command = br.readLine().split(" ");
            switch (command[0]) {
                case "push":
                    if (!isFull()) {
                        rear++;
                        length++;
                        data[rear] = Integer.parseInt(command[1]);
                    }
                    break;
                case "pop":
                    if (!isEmpty()) {
                        front++;
                        length--;
                        System.out.println(data[front]);
                    } else System.out.println(-1);
                    break;
                case "front":
                    System.out.println(isEmpty() ? -1 : data[front + 1]);
                    break;
                case "back":
                    System.out.println(isEmpty() ? -1 : data[rear]);
                    break;
                case "size":
                    System.out.println(isEmpty() ? 0 : length);
                    break;
                case "empty":
                    System.out.println(isEmpty() ? 1 : 0);
                    break;
            }
        }
    }

    private static boolean isFull() {
        return rear == MAX_SIZE;
    }

    private static boolean isEmpty() {
        return front == rear;
    }
}