Queue (큐)

Queue

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

• FIFO(First In First Out, 선입선출) 구조를 가지고 있는 자료구조다.
  • 매표소에서 표를 예매하는 것과 같다.
  • 매표소에 줄을 섰을 때, 먼저 온 사람이 앞에 서서 먼저 표를 구매하고 빠져나간다.
  • 나중에 온 사람은 앞에 사람들이 빠질 때 까지 기다렸다가 자기 차례가 오면 구매하고 빠져나간다.
• 큐에 데이터를 넣는 행위를 enqueue라고 한다.
• 큐에서 데이터를 꺼내는 행위를 dequeue라고 한다.

두가지 자료구조를 활용해서 큐를 구현했다.

• 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다.
• 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다.
• ListNode로 구현했을 땐 큐 크기 제한이 없다.
• 테스트코드 포함 전체 코드

구현1 (int배열 사용)

package com.example.week4;

public class QueueWithArray {
    static final int EMPTY = -1;
    int[] datas;
    int tail = EMPTY;

    public QueueWithArray(int size) {
        datas = new int[size];
    }

    public void enqueue(int data) {
        tail++;
        datas[tail] = data;
    }

    public int dequeue() {
        if (tail == EMPTY) {
            throw new IndexOutOfBoundsException("큐에 데이터가 없습니다.");
        }
        int data = datas[0];
        for(int i=1; i<=tail; i++) {
            datas[i-1] = datas[i];
        }
        return data;
    }
}

구현2 (ListNode 사용)

package com.example.week4;

public class QueueWithListNode {
    static final int EMPTY = -1;
    ListNode head = new ListNode();
    int tail = EMPTY;


    public void enqueue(int data) {
        tail++;
        ListNode.add(head, new ListNode(data), tail);
    }

    public int dequeue() {
        ListNode removed = ListNode.remove(head, 0);
        return removed.data;
    }
}