티스토리 뷰

반응형

원형큐 (Circular Queue)


원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 앞선 포스팅에서 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없었습니다. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해집니다.

 

Enqueue

rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다.

 

배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arraysize == front 라면 배열이 포화상태인걸로 판단하여 데이터 삽입이 이루어지지 않게 됩니다.

 

■ Dequeue

front의 포인터를 1증가 시키고 그 위치의 데이터를 배열에서 가지고 옵니다. rear==front 조건이라면 배열이 공백상태인걸로 판단하여 Dequeue가 실행되지 않습니다.

 

■ 원형 큐 데이터 입출력 과정

                

 

먼저 rear과 front는 0 인덱스를 가지고 시작합니다. 현재 상태에서 Dequeue가 실행되면 rear==front이므로 실행이 되지 않습니다.

 

데이터 1이 Enqueue 실행 된 상태입니다. (rear+1)%4 == front 조건을 검사하고 (rear+1)%4을 증가하여 해당 인덱스에 데이터 1의 값을 삽입 하였습니다.

         

마찬가지로 Enqueue 2를 실행 한 상태입니다. 포화상태가 아니므로 정상적으로 데이터 삽입이 이루어집니다.

 

      

Enqueue 3의 실행 상태입니다. 이제 한번 더 Enqueue를 할려고 하면 포화 조건인 (rear+1)%4==front를 만족하게 됩니다. 이 상태에서는 더 이상 Enqueue가 실행되지 못합니다.

             

Dequeue를 실행한 상태입니다. 공백 상태 조건인 front==rear을 만족하지 않기 때문에 (front+1)%4한 인덱스에 존재하는 배열의 데이터를 가지고 옵니다.

       

한번 더 Dequeue를 실행 한 상태입니다. 마찬가지로 공백 조건에 만족하지 않으므로 (front+1)%4 인덱스의 데이터를 가지고 옵니다. 이 상태에서 두 번 연속 Dequeue를 실행하게 되면 두 번째 Dequeue에서 공백 조건에 만족하게 되므로 Dequeue가 실행되지 않습니다.

 

Enqueue 4를 한 결과입니다. 그림에서 보면 0번째 인덱스에 삽입이 이루어졌는데, rear 포인터 연산이 (rear+1)%4의 형태로 이루어지기 때문입니다. 즉 배열의 크기로 나머지 연산을 함으로써 배열의 인덱스를 계속해서 순환할 수 있도록 하는 것입니다.



 

■ 원형 큐 구현

 

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
45
46
47
48
49
50
51
52
53
54
55
56
public class Circular_Queue {
    
    int rear = 0;            //최초 0에서부터 시작
    int front = 0;            //최초 0에서부터 시작
    int maxsize = 0;        //배열의 크기
    int[] circular_Queue;          //배열
    
    public Circular_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        circular_Queue = new int[this.maxsize];
    }
    
    public boolean Isempty()    //배열이 공백 상태인지 체크하는 메서드입니다.
    {
        if(rear == front)
        {
            return true;
        }
        return false;
    }
    public boolean Isfull()        //배열이 포화 상태인지 체크하는 메서드입니다.
    {
        if((rear+1)%maxsize == front)
        {
            return true;
        }
        return false;
    }
    
    public void EnQueue(int num)
    {
        if(Isfull())            //배열이 포화상태일경우
        {
            System.out.println("큐가 가득 찼습니다");
        }
        else                //배열이 포화상태가 아닐경우
        {
            rear = (rear+1) % maxsize;
            circular_Queue[rear]=num;
        }
    }
    
public int DeQueue()
    {
        if(Isempty())         //배열이 공백상태이면 -1반환
        {
            return -1;
        }
        else                 //배열이 공백상태가 아니라면
        {
            front = (front+1)%maxsize;
            return circular_Queue[front];
        }
    }
}

 

 

 

 

 

반응형