4-2. 큐(Queue)

<큐(Queue)>

: 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과 다르다.

 

*인큐(enqueue): 큐에 데이터를 넣는 작업

*디큐(dequeue): 데이터를 꺼내는 작업

 

 

 

 

 

・배열로 큐 만들기

 

-인큐: 리어(rear)에 새로운 데이터를 저장. O(1)의 복잡도로 적은 비용으로 구현 가능

-디큐: front에서 데이터를 꺼낸 다음 두 번째 이후의 요소를 모두 맨 앞으로 이동. O(n)의 복잡도, 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어짐

 

 

 

 

 

 

・링 버퍼(ring buffer)로 큐 만들기

: 배여래의 처음과 끝이 연결되어있는 자료구조로, 배열 요소를 앞쪽으로 옯기지 않는다. 논리적으로 첫 번재 요소와 마지막 요소를 식별하기 위한 변수 프런트(front)와 리어(rear)가 필요하다.

 

 

 

1. 생성자

: 큐 본체용 배열을 생성하는 등의 준비 작업을 수행

 

public IntQueue(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[max];
        } catch(OutOfMemoryError e) {
            max = 0;
        }
    }

 

 

 

2. 인큐 메서드 enque

: 큐에 데이터를 인큐하는 메서드. 인큐에 성공하면 인큐한 값을 그대로 반환

 

public int enque(int x) throws OverflowIntQueueException {
        if(num >= max)
            throw new OverflowIntQueueException();
        
        que[rear++] = x;
        num++;
        
        if(rear == max)
            rear = 0;
        
        return x;
    }

 

 

 

3. 디큐 메서드 deque

: 큐에서 데이터를 디큐하고 그 값을 반환하는 메서드

 

public int deque() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        
        int x = que[front++];
        num--;
        
        if(front == max)
            front = 0;
        
        return x;
    }