📌 서론.

큐를 정의하고 배열으로 직접 구현하였다.

큐(Queue)란?

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. (First In First Out 구조)

큐의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제알 앞/뒤 원소의 확인이 O(1)
4. 제일 앞/뒤 가 아닌 원소들의 확인/ 변경이 불가능.

보통 큐는 blood Fill이나 BFS에서 많이 활용됨.

큐 구현

배열을 통한 구현

1. 원소를 담을 배열 1개
2. 앞쪽, 뒷쪽을 가리킬 변수 2개가 필요.

class ArrayQueue {
  private int[] Queue; // 원소를 담을 배열 1개
  private int head = 0;
  private int tail = 0;

  public ArrayQueue(int capacity) {
    Queue = new int[capacity];
  }

  public void push(int data) {
    Queue[tail++] = data;
  }

  public int pop() {
    return Queue[head++];
  }

  public int front() { // 제일 앞(밑)쪽에 원소를 반환하는 함수.
    return Queue[head];
  }
  public int back() { // 제일 뒷(윗)쪽의 원소를 반환하는 함수
    return Queue[tail-1];
  }

  public static void main(String[] args) {
    ArrayQueue Queue = new (5); // 배열이기에 capacity를 정의해줘야함.
    Queue.push(10);
    Queue.push(20);
    Queue.push(30);
    Queue.push(40);
    Queue.push(50);
//     Queue.push(60); // -> 주어진 capacity 이상 넣을 순 없음.

    System.out.println(Queue.pop()); // 10
    System.out.println(Queue.front()); // 20
    System.out.println(Queue.pop()); // 20
    System.out.println(Queue.back()); // 50
  }
}

정적 배열이기에 처음에 Queue의 용량을 선언해줘야한다.

📝 연습 문제 큐_2

링크 : https://www.acmicpc.net/problem/18258

1. 문제 설명

   정수를 저장하는 큐를 구현하고, 입력으로 주어지는 명령에 따라 결과를 출력하는 문제이다.

2. 문제 풀이

명령의 수가 2,000,000 개 이기 때문에 ArrayList를 사용하여 풀면 시간 초과가 난다.

큐를 직접 구현하여 풀었다.

// 큐_2 18258

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    //input
    int numberOfCount = Integer.parseInt(br.readLine());
    ArrQueue queue = new ArrQueue(numberOfCount);

    for (int i = 0; i < numberOfCount; i++) {
      String[] cmd = br.readLine().split(" ");
      switch (cmd[0]) {
        case "push": // push X: 정수 X를 큐에 넣는 연산이다.
          queue.push(Integer.parseInt(cmd[1]));
          break;
        case "pop": // pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
          sb.append(queue.pop()).append('\n');
          break;
        case "size": // size: 큐에 들어있는 정수의 개수를 출력한다.
          sb.append(queue.size()).append('\n');
          break;
        case "empty": // empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
          sb.append(queue.empty()).append('\n');
          break;
        case "front": // front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
          sb.append(queue.front()).append('\n');
          break;
        case "back": // back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
          sb.append(queue.back()).append('\n');
          break;
      }
    }

    // Output
    System.out.println(sb.toString());
    br.close();
  }
}

class ArrQueue {

  private int[] Queue; // 원소를 담을 배열 1개
  private int head = 0;
  private int tail = 0;

  public ArrQueue(int capacity) {
    Queue = new int[capacity];
  }

  public void push(int data) {
    Queue[tail++] = data;
  }

  public int pop() {
    if (!isEmpty()) {
      return Queue[head++];
    }
    return -1;
  }

  public int front() { // 제일 앞(밑)쪽에 원소를 반환하는 함수.
    if (!isEmpty()) {
      return Queue[head];
    }
    return -1;
  }

  public int back() { // 제일 뒷(윗)쪽의 원소를 반환하는 함수
    if (!isEmpty()) {
      return Queue[tail - 1];
    }
    return -1;
  }

  public int size() {
    return tail - head;
  }

  public int empty() {
    if (isEmpty()) {
      return 1;
    }
    return 0;
  }

  public boolean isEmpty() {
    return tail - head <= 0;
  }
}