02 선형 큐 (Linear Queue) 자료구조

선형 큐 (Linear Queue)

---

큐는 가장 먼저 들어온 데이터가 가장 먼저 내보내지는 (FIFO : First In First Out) 구조를 가집니다.

선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공합니다.

 

■Enqueue 기능

Enqueue는 큐 자료구조에 데이터를 집어 넣는 기능을 수행합니다. 영화 매표소에 사람들이 줄을 선다고 생각해봅니다. 이때 매표소 가장 앞사람을 가르키는 것을 front라 하고 마지막에 서있는 사람을 가르키는 것을 rear이라고 부릅니다.

 

1번이 Enqueue 되어진 상태입니다. 첫 번째로 줄을 선 사람이므로 front와 rear이 둘다 1번을 가르키고 있습니다.

 

다음으로 2번이 Enqueue 기능을 수행 한 상태입니다. Front는 고정되어 있고 rear만 가장 나중에 들어오면 2번을 가르키고 있는 상태입니다.

 

다음으로 3번이 Enqueue 기능을 수행 한 상태입니다. front는 여전히 고정되어 있고 rear은 3번을 가르킵니다.

 

다음으로 4번이 Enqueue 기능을 수행 한 상태입니다.

 

 

■ Dequeue

 

다음으로 Dequeue 기능입니다.  Dequeue는 반대로 큐에서 데이터를 내보내는 기능을 수행합니다.

Dequeue 기능을 수행하고 front의 인덱스를 증가시키게 보통이지만 여기서는 front를 고정시키고 rear 인덱스만 줄인 채로 뒤에 데이터를 앞으로 이동시키는 방식을 사용합니다.

 

 Dequeue를 한번 수행하고 나면 1번이 큐에서 내보내지고 front는 고정된채로 뒤에 데이터가 앞으로 한칸씩 이동하게 됩니다. 이 방식은 나중에 rear이 큐의 마지막 인덱스를 가르키고 있을 때 앞의 공간을 활용하기 위해서입니다.

한번 더 Dequeue를 실행 한 결과입니다. 2번이 내보내지고 rear은 여전히 마지막 데이터를 가르킵니다.

 

■ 선형 큐의 문제점

 

일반적인 선형 큐는 rear이 마지막 index를 가르키면서 데이터의 삽입이 이루어집니다. 문제는 rear이 배열의 마지막 인덱스를 가르키게 되면 앞에 남아있는 (삽입 중간에 Dequeue 되어 비어있는 공간) 공간을 활용 할 수 없게 됩니다. 이 방식을 해결하기 위해서는 Dequeue를 할때 front를 고정 시킨 채 뒤에 남아있는 데이터를 앞으로 한 칸씩 당기는 수밖에 없습니다. 또다른 방안으로는 원형큐를 사용하는 방법인데 그것은 다음 포스팅에서 다루도록 하겠습니다.

 

 

■ 선형 큐 구현

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

public class Linear_Queue {          int rear = -1;     int front = 0;     int maxsize = 0;     int[] Linear_Queue;          public Linear_Queue(int maxsize)     {         this.maxsize = maxsize;         Linear_Queue = new int[maxsize];     }          public void EnQueue(int num)     {         if(rear != maxsize-1)         {             Linear_Queue[++rear] = num;         }         else         {             System.out.println("데이터 다참");         }     }          public int DeQueue()     {         if(rear!=front || (rear==0 && front==0))         {             int tmp =Linear_Queue[front];             for(int i=1;i<=rear;i++)             {                 Linear_Queue[i-1] = Linear_Queue[i];             }             rear--;             return tmp;         }         else         {             return -1;         }         } }