[자료구조] #7 Queue(1)

• Queue

 

큐는 '대기열'을 뜻한다.

큐의 가장 큰 특징은 'FIFO'(First In, Firtst Out) 이다.

먼저 온 순서대로 결제하는 계산대를 생각하면 쉽다.

스택과 큐의 차이

 

큐의 구조

front(앞단) & rear(끝단)

 

주요 연산자

Enqueue(인큐) : 큐의 끝단에 아이템을 삽입한다.

Dequeue(디큐) : 큐의 앞단에서 아이템을 제거한다.

 

• 부가 연산자

• empty() : 큐가 비어있으면 true를 반환한다. 그렇지 않으면 false.
• full() : 큐가 가득차면 true를 반환한다. 그렇지 않으면 false.
• peek() : 맨 앞단에 있는 아이템의 값을 반환한다.(삭제하지는 않는다.)
• size() : 큐에 있는 원소의 개수를 반환한다.

• 배열로 구현한 Queue

 

몇번의 연산 이후에 앞단에 빈공간이 생성된 것을 볼 수 있다.

 

공간적인 측면의 효율성이 줄어드는 것을 막기 위해 아이템들을 앞으로 움직일 필요가 있다.

 

따라서 실제로는 1차원 배열이지만, 유효공간을 사용할 수 있는 원형 큐에 대해 알아보자.

 

• Circular Queue

 

front & rear

첫번째 아이템 그 전 인덱스를 front로 지정한다.

마지막 아이템의 인덱스를 rear로 지정한다.

 

나머지 연산

예를 들어, 인덱스가 14이면 14 / 12 = 1 ··· 2 이다. 

인덱스의 이동이 시계 방향이면 +1, 반대 방향이면 -1을 해준다.

(14 + 1) / 12 = 1 ··· 3 이다.

 

만약 0일 경우 시계 반대 방향으로 이동하면 음수가 되기 때문에

공식의 일반성을 위해 +12를 해준다.

 

• Enqueue 연산

def enqueue(x):
   if full():
       throw "error : queue is full"
   else:
       rear <- (rear + 1) mod MAX_QUEUE_SIZE
       data[rear] <- x

 

그림으로 표현하면 아래와 같다.

이 상황에서 rear는 8이다.

 

• Dequeue 연산

def dequeue(x):
   if empty():
       throw "error : queue is empty"
   else:
       front <- (front + 1) mod MAX_QUEUE_SIZE
       return data[front]

 

front를 옮겨준다고 생각하면 쉽다.

 

Enqueue와 Dequeue의 시간복잡도는 Worst case일 경우 상수시간 걸린다.

 

• 예시

 

• Empty & Full

 

Empty state : front == rear

Full state : front == (rear + 1) % MQS

 

rear에서 한칸을 움직였는데 front와 같아지면 empty로 보겠다는 것인데,

이는 구현의 편리성을 위해서이다.

빈공간은 dummy item이라고 한다. 

 

• 큐 클래스 디자인

클래스 다이어그램

 

• ADT 구현

class CircularQueue {
protected:
    static const int MQS = 100; // MQS = MAX_QUEUE_SIZE
    int front; // 큐의 첫 번째 요소의 바로 전 위치를 가리키는 인덱스
    int rear; // 큐의 마지막 요소를 가리키는 인덱스
    int data[MQS]; // 데이터를 저장하는 배열
public:
    // 생성자: front와 rear를 초기화
    CircularQueue(){ front = rear = 0; }
    
    // 큐가 비어있는지 확인하는 함수
    bool empty(){ return front == rear; }
    
    // 큐가 가득 찼는지 확인하는 함수
    bool full(){ return (rear + 1) % MQS == front; }
    
    // 큐에 요소를 추가하는 함수
    void enqueue(int val) {
        // 만약 큐가 가득 찼다면 예외를 발생시킴
        if(full())
            throw "error: queue is full";
        else{
            // rear를 다음 위치로 이동하고 값을 추가
            rear = (rear + 1) % MQS;
            data[rear] = val;
        }
    }
    
    // 큐에서 요소를 제거하고 반환하는 함수
    int dequeue() {
        // 큐가 비어있다면 예외를 발생시킴
        if(empty())
            throw "error: queue is empty";
        else{
            // front를 다음 위치로 이동하고 해당 위치의 값을 반환
            front = (front + 1) % MQS;
            return data[front];
        }
    }
    
    // 큐의 첫 번째 요소를 반환하는 함수
    int peek() {
        // 큐가 비어있다면 예외를 발생시킴
        if(empty())
            throw "error: queue is empty";
        else
            // front의 다음 위치에 있는 값을 반환
            return data[(front + 1) % MQS];
    }
};

 

• Deque

 

덱은 double-ended queue로, 양 극단에서 연산이 가능한 형태이다.

 

스택과 큐를 모두 표현할 수 있는데,

스택은 addRear와 deleteRear를 사용하고

큐는 addRear와 deleteFront를 사용한다. 

 

• Deque 구현

 

CircularQueue 클래스에 덱의 양쪽에서 요소를 삽입하거나 삭제하는 기능을 추가하여 CircularDeque를 만들 수 있다.

덱을 구현하는 또 다른 방법으로는 linkedlist가 있다.

 

• 디큐 클래스 디자인

 

CircularQueue가 부모 클래스이고 CircularDeque가 자식 클래스이다.

따라서 CircularDeque가 상속받는 형태이다.

 

코드의 중복을 줄이기 위해 멤버 변수와 함수를 재활용하고 있다.

 

• ADT 구현

class CircularDeque : public CircularQueue {
public:
    // CircularDeque 클래스 정의, CircularQueue 클래스 상속
    CircularDeque() { }
    
    // 덱의 뒤에 요소를 추가하는 함수
    void addRear(int val) { enqueue(val); } // enqueue() 호출
    
    // 덱의 앞에서 요소를 삭제하고 반환하는 함수
    int deleteFront() { return dequeue(); } // dequeue() 호출
    
    // 덱의 앞에서 요소를 반환하는 함수
    int getFront() { return peek(); } // peek() 호출
    
    // 덱의 뒤에서 요소를 반환하는 함수
    int getRear() {
        // 덱이 비어있는 경우 예외 발생
        if(empty()) 
            throw "deque is empty";
        else 
            // rear가 가리키는 위치에 있는 값 반환
            return data[rear];
    }
    
    // 덱의 앞에 요소를 추가하는 함수
    void addFront(int val) {
        // 덱이 가득 차 있는 경우 예외 발생
        if(full()) 
            throw "deque is full";
        else{
            // front를 이전 위치로 이동하고 값을 추가
            data[front] = val;
            front = (front - 1 + MQS) % MQS;
        }
    }
    
    // 덱의 뒤에서 요소를 삭제하고 반환하는 함수
    int deleteRear() {
        // 덱이 비어있는 경우 예외 발생
        if(empty()) 
            throw "deque is empty";
        else{
            // rear가 가리키는 위치의 값을 임시 변수에 저장한 후 rear 이동
            int ret = data[rear];
            rear = (rear - 1 + MQS) % MQS;
            return ret;
        }
    }
};