[펌_JAVA를 이용한 자료구조] 큐(Queue)

참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며

안녕하세요. 이번 강좌는 자료구조의 또 다른 하나인 Queue에 대해서 배워보겠습니다. 지난번의 Stack과는 어떤점이 다를까요? 어디로 자료를 넣고 어디서 자료를 빼는지, 어디에 쓰일지 등을 생각해 가시면서 읽어주시면 더욱 좋으리라고 필자는 생각합니다. 이번 강좌는 5회 강좌인 Stack의 형식과 매우 비슷할 것입니다. Stack와 같이 알아두신다면 더할나위 없이 좋겠죠.

Queue 란

지난번의 Stack과 구조 자체는 매우 흡사합니다. 하지만 한가지가 다릅니다. 자료가 입력되고 출력되는 곳이 따로 존재 한다는 것이죠. Stack에서는 맨 위에서만 입력, 출력을 할 수 가 있었죠. 하지만 Queue는 한쪽에서 자료가 입력되면, 자료가 출력되는 곳은 입력된 곳이 아닌 다른 곳 이라는 겁니다. 물이 지나가는 파이프 정도라고 생각하면 간단하겠네요.

[그림 1]

위 그림처럼 파이프가 Queue라고 할 수 있구요, 파이프로 들어가고 나오는 물이 자료(Data)라고 할 수 있습니다. Queue에서는 처음 들어간 자료가 가장 먼저 나오게 됩니다. FIFO(First In First Out) 라고도 하죠.

============================================================================================

 

Array로 Queue 구현

지난 Stack강좌에서도 Array로 구현을 했었죠. 이번에도 Array로 Queue를 구현해 보도록 하겠습니다.

Queue구현에 필요한 함수에는 Enque(), Deque(), Is_empty(), Is_full(), Shift_index_to_right(), Print_queue() 들이 있습니다. 하나하나 차례대로 살펴 보도록 하죠.

일단 필요한 멤버 변수들부터 살펴 보도록 하겠습니다.

private int[] data; private int front; private int rear; private int many_items; private int queue_size;

data배열은 실제로 자료들이 들어갈 배열을 가리키게 되며, front와 rear는 자료가 입력되고 출력되는 인덱스를 가리키게 됩니다. many_items는 현재 Queue안에 자료가 몇 개나 존재 하는지 그 크기를 가지게 되구요, queue_size는 만들어진 Queue의 크기를 가지고 있게 됩니다.

이 프로그램에서는 front를 배열의 맨 앞에 두고 자료가 입력이 될 때마다 rear가
증가하고, 자료가 빠져나갈때에 rear가 감소하는 형식으로 작성이 되었습니다. 들어가는 자료는 0과 양수만이 해당이 됩니다.

생성자 함수도 살펴보도록 하겠습니다.

Queue(int size) {    queue_size = size;    data = new int[size];    front = 0;    rear = 0;    many_items = 0; }

생성자 함수는 size라는 정수형 인자 하나를 받게 되죠. Queue클래스를 생성할 때 넣어주는 숫자가 Queue의 전체 크기가 되는 것입니다. 이 프로그램에서는 배열의 0번 인덱스에 자료를 넣는 방식으로 작성을 했는데요, 이건 프로그래머가 정할 수 있는 것으로써 배열의 맨 마지막 인덱스에서 자료의 입력이 이루어 지도록 할 수 도 있습니다.

[그림 2]크기 5의 Queue의 초기 상태

자료는 언제나 front로만 입력되며, 자료가 입력될 때마다 rear가 하나씩 증가하게 됩니다. 밑의 Enque함수를 보시면 아실 수 있을 겁니다.

public void Enque(int want_number) {     if(Is_empty() == true)     {        data[front] = want_number;        many_items++;     }     else if(Is_full() == false)     {        Shift_index_to_right();        data[front] = want_number;        rear++;        many_items++;     }     else        System.out.println("Queue가 가득 차서 " + want_number + "을(를) 집어 넣을 수 없습니다"); }

Enque함수도 역시 정수형 인자 하나를 받게 되며 그 인자를 Queue에 입력하는 작업을 수행하게 됩니다. Queue가 비어 있는 경우와 비어있지 않은 경우를 판단하여 Shift_index_to_right함수를 호출하기도 하고 호출하지 않기도 하는 차이점만 있습니다. Queue에 자료가 가득 차 있다면 적절한 메시지를 호출하고 입력은 하지 않게 됩니다.

밑의 그림 몇 개는 Enque과정을 차례차례 나타냅니다.


[그림 3] Queue에 처음으로 숫자 1을 입력한 경우

[그림 4] Queue에 6을 입력한 첫 번째 단계(Shift_idex_to_right(); )

[그림 5] Queue에 6을 입력한 두 번째 단계(data[front] = want_number;)

[그림 6] Queue에 6을 입력한 세 번째 단계(rear++;)

Shift_index_to_right()라는 함수가 보이시죠. 이 함수가 하는 일은 Queue안에 있는 자료들을 한칸씩 오른쪽으로 이동해 주는 역할을 합니다. front에 자료를 넣어줘야 하는데 그냥 넣었다가는 front에 이미 들어있는 자료를 잃어 버리는 경우가 발생하겠죠.

Shift_index_to_right()함수를 살펴보도록 하겠습니다.

private void Shift_index_to_right() {     int i;     for( i = rear ; i >= front ; i-- )     {        data[i + 1] = data[i];     } }

이제는 Deque함수를 살펴보도록 할까요? rear가 가리키는 인덱스에서 자료를 빼기만 하면 되므로 많은 함수는 필요가 없겠죠?

public int Deque() {     if(Is_empty() == false)     {        many_items--;        return data[rear--];     }     return -1; }

Deque함수는 Queue가 비어있나를 체크 하여 Queue가 비어있으면 -1을 리턴해주고 아니라면 Queue에서 rear가 가리키는 배열의 인덱스에 있는 값을 리턴해 주겠죠. 이 Queue는 양수와 0만을 가지는 구조이기 때문에 즉 -1을 리턴한다는 것은 Error를 나타낸다고 할 수 있겠습니다.

Is_empty() 함수와 Is_full() 함수는 many_items와 queue_size를 비교하는 것만으로도 체크가 되기 때문에 자세한 설명은 생략하도록 하겠습니다. 직접한번 작성해 보시기 바랍니다.

그 다음으로 Printf_Queue함수만 작성하면 프로그램이 완성됩니다.

public void Print_queue() {     int i;     System.out.println("----------------------------------");     System.out.println("Number of Items = " + many_items);     System.out.println("----------------------------------");     System.out.println("Print");     for( i = front ; i <= rear ; i++ )        System.out.println(data[i]);     System.out.println("=================================="); }

front에서 rear에 있는 값까지만 찍어주면 되는 간단한 함수입니다.

강좌를 마치며...

이번 강좌는 Queue에 대해서 알아보았습니다. 지난 강좌의 마지막 부분에서도 말씀드렸듯이 Queue역시 Linked List로 작성하는 것이 더 효율적인 면이 분명히 있습니다. 강좌에서는 Array를 이용하여 아주 간단히 작성한 것에 불과합니다. 실제로 독자분들이 직접 작성을 해보시고, Linked List를 이용하여 Queue를 새로 작성 해보시면 실력향상에 더욱 도움이 되리라 믿습니다.

이제 전체 강좌의 반정도가 지났군요. 이제부터 연재될 강좌는 지금까지 했던 것보다는 많이 복잡하며 구현도 Array를 이용하는 것이 아닌 Linked List를 이용하여 많이 작성을 하게 될 것입니다. 앞의 내용을 이해하고 보신다면 더욱 수월하게 내용을 받아들일수 있지 않을까 싶네요.

독자분들 좋은하루 되시구요, 다음 강좌에서 뵙겠습니다.