[알고리즘-PS] Java 에서 큐를 구현하는 방법

Queue란

Stack 자료구조와 다르게 FIFO(First In First Out) 방식의 선입 선출 구조를 가지고 있는 자료 구조이다.

큐는 최근 사용 문서, 인쇄작업 대기 목록, 버퍼 등의 분야에서 사용되며 스택은 위에만 뚤려 있어 자료가 한 방양으로만 흐른다면 큐는 양 방향으로 뚤려 파이프 같은 모양으로 자료가 흐른다.

큐의 원리

큐는 다음과 같이 front와 rear로 데이터의 추가 및 삭제의 경계를 알린다.

큐에 데이터 추가하기

만약 큐가 비어있다면 front 와 rear은 같은 곳을 향하게 될 것이고 20 과 30 이란 데이터를 추가한다면 어떻게 변하는지 봐보자.

front와 rear의 포인터가 달라졌는데 이런 식으로 추가를 한다면 rear += 1으로 rear의 위치가 변경되며 rear에 에 해당되는 인덱스에 값이 추가될 것이다.

큐에 데이터 추출하기

그럼 현재와 같은 상태에서 데이터를 추출할 때는 front의 포인터가 한 칸 뒤로 이동하게 되며 해당 인덱스의 값을 추출한다.

---

값의 추가 및 삭제가 이루어진다면 가변적인 front와 rear로 인한 배열의 고정적 길이를 벗어나는 결과가 발생하므로 ArrayList로 구현을 해야 한다면 데이터를 꺼낼 때 생기는 Front의 공백을 매우기 위해 Front 이후의 데이터를 모두 앞으로 한 칸씩 앞당기는 과정을 거쳐야 한다.

ArrayList의 구현

class IntQueue{

    private int front;
    private int rear;
    private int max;
    private int[] queue;

    public IntQueue(int capacity){
        max = capacity;
        rear = -1;
        front = 0;
        queue = new int[max];
    }
    boolean empty(){
        return (front == (rear+1));
    }

    boolean full(){
        return (rear >= max-1);
    }

    // rear로 데이터를 추가
    void add(int x){
        if(full()) throw new ArrayIndexOutOfBoundsException();
        queue[++rear] = x;
    }
    // front는 데이터를 뺼 때만 사용
    int remove(){
        if (empty()) throw new ArrayIndexOutOfBoundsException();
        return queue[front++];
    }

    int peek(){
        return queue[front];
    }

}

LinkedList의 구현

수정중..