[알고리즘] 2.2.자료구조 : 배열을 이용한 큐(Queue) 구현

  큐 이해하기

2017/01/30 - [Programming/Algorithm] - [알고리즘] 2.2.자료구조 : 큐(Queue)

  배열을 이용한 큐 구현

public class ArrQueue {

private int front;

private int rear;

private int size;

private Object[] arrQueue;

public ArrQueue(int size){

this.front = 0;

this.rear = -1;

this.size = size;

this.arrQueue = new Object[this.size];

}

//Queue 배열이 꽉 차있는지 확인

public boolean isFull(){

if(rear >= size-1) return true;

else return false;

}

//Queue 배열이 비어있는지 확인

public boolean isEmpty(){

if(rear < front) return true;

else return false;

}

//원하는 데이터를 추가하는 메쏘드

public void enQueue(Object item){

if(isFull()) throw new ArrayIndexOutOfBoundsException();

this.rear++;

arrQueue[rear] = item;

}

//front에 위치한 데이터가 무엇인지 확인하는 메쏘드

public Object peek(){

return arrQueue[front];

}

//Queue의 front에 위치한 데이터 삭제

public Object deQueue(){

if(isEmpty()) throw new ArrayIndexOutOfBoundsException();

Object backUpItem = peek();

this.front++;

return backUpItem;

}

}

public class main {

public static void main(String[] args) {

ArrQueue arrQueue = new ArrQueue(4);

arrQueue.enQueue("Hello");

arrQueue.enQueue(5);

arrQueue.enQueue("queue");

while(!arrQueue.isEmpty()){

System.out.println(arrQueue.deQueue());

}

}

}

결과값 

먼저 생성자부터 살펴봅시다.

public ArrQueue(int size){

this.front = 0;

this.rear = -1;

this.size = size;

this.arrQueue = new Object[this.size];

}

생성자에서 주의할 점은 front와 rear의 인덱스입니다. 다시 은행의 번호표를 생각해보면, 은행을 처음 열었을 때 번호표는 1번으로 초기화가 되어있을 것입니다. front는 다음에 호출받을 번호이고, rear는 마지막의 번호표의 위치입니다. front부터 생각해보면 아직 손님이 한명도 없어도 다음에 호출할 번호는 맨 처음입니다. 따라서 배열의 맨처음인 0으로 초기화하였습니다. 다음으로 rear는 마지막의 번호표의 위치인데, 아직 손님이 한 명도 없어 번호표를 발부한 적이 없습니다. 따라서 -1로 초기화하였습니다. rear를 0으로 초기화하면 안되는지 의문을 가질수 있는데, 배열에서 0은 첫번째 요소를 의미합니다. 즉, rear = 0; 의 의미는 마지막에 받은 번호가 1번 이라는 것입니다. 그럼 첫 손님은 번호표 1번이 아니라 2번을 받게 되는 것이지요. 배열의 인덱스가 1부터 시작하면 어려울 이유가 없지만 0부터 시작하고, 번호표는 1번부터 시작하여 조금 헷갈릴 수도 있습니다.

다음으로 isEmpty(), isFull(), peek()은 스택과 똑같이 구현하였고 기능도 같습니다.

enQueue()는 마지막에 온 손님에게 번호표를 주는 함수입니다. 마지막에 온 손님의 번호는 마지막에 발부한 번호(rear)에 1을 더하면 되겠지요? 1을 더한 rear의 위치에 번호표를 추가합니다.

deQueue()는 창구 업무를 본 손님의 번호표를 대기목록에서 삭제하는 함수입니다. 이는 단순히 front의 위치를 다음으로 옮겨주기만 하면 됩니다. 

  선형 큐(Linear Queue)의 문제점

enqueue()와 dequeue()를 여러번 하였다고 가정해봅시다. 배열로 큐를 구현하였으니 최대 크기를 미리 정해야 합니다. 예제에서는 4로 정하였습니다.

enqueue를 4번하고 dequeue를 3번한 상태입니다. 여기서 문제점은 앞부분 배열 [0],[1],[2]는 비어있지만 Queue는 꽉 찼다고 인식을 합니다. (isFull()함수 참조) 이를 해결하기 위해 큐를 선형으로 만들지 않고 원형으로 만든 circularQueue가 나옵니다. 원형큐는 다음시간에 정리하도록 하겠습니다.