[자료구조] 큐

반응형

 

큐

자료의 입력과 출력이 FIFO(First In First Out)의 형태를 띄는 자료구조이다. LIFO의 스택과는 달리, 먼저 들어간 자료가 먼저 출력된다. 입력은 뒤(rear)에서, 출력은 앞(front)에서 일어난다. 줄을 서서 차례를 기다릴 때를 생각해보자. 앞에 있는 사람의 뒤에 줄을 서 차례를 기다리다가, 앞 사람이 빠져야 나의 차례가 되는 것과 같다.

 

 

큐에는 선형 큐와 원형 큐가 있다. 선형 큐는 구현하기는 쉽지만, front와 rear가 배열의 끝에 도달하게 된다면? 더 이상 사용할 수 없게 된다. 배열 앞부분에 값이 남는 데도! 이 방식을 해결하려면 요소들을 앞으로 당기거나 하는 번거로움이 필요하다. 이 문제를 해결한 것이 원형 큐이다.

 

원형 큐에서는 front는 항상 맨 앞 요소의 앞을 가리키고, rear는 마지막 요소를 가리킨다. 만약 rear가 배열의 크기를 초과하면? 0번째를 가리키게 된다. 배열의 전체 부분을 다 사용할 수 있게된다!

 

큐의 추상 자료형은 다음과 같다.

init() : 큐를 초기화한다.
is_empty() : 큐가 비어있는지 확인한다.
is_full() : 큐가 가득 차 있는지 확인한다.
size() : 큐에 저장된 요소들의 수를 반환한다.
enqueue(x) : x를 큐의 맨 뒤에 추가한다.
dequeue() : 큐의 맨 앞 요소를 삭제하고 반환한다.
peek() : 큐의 맨 앞 요소를 반환한다.

---

큐의 구현

배열을 이용한 큐

정수를 저장할 큐를 queue[MAX_SIZE] 라고 하자. MAX_SIZE는 큐의 최대 크기이다. 큐는 앞과 뒤 두 곳에서 연산이 일어나므로, 변수를 2개 선언해 주어야 한다.

const int MAX_SIZE = 256; // 큐에 저장될 요소의 최대 개수
int queue[MAX_SIZE];
int front, rear; // 큐의 맨 앞과 뒤를 가리킬 변수

 

init()

초기화는 front와 rear 둘다 -1을 가리키게 하면 된다.

void init() {
    front = 0;
    rear = 0;
}

 

is_empty(), is_full(), size()

공백상태 검사는 rear과 front의 값이 같은지 검사하면 된다.

bool is_empty() { return front == rear; }

포화상태와 크기를 구하는 연산은 어떨까. 크기가 8인 배열이 있다고 하자. front가 0을 가리키고 있고, rear는 7을 가리키고 있다고 하자. 명백한 포화상태이다. 그렇다면 rear = MAX_SIZE 로 표현하면 될까?

bool is_full() { return rear == MAX_SIZE - 1; } // 이렇게 한다면?

아니다이다. front가 1이고 rear가 0이라면 이 또한 포화상태이다. 그러나, return 값은 false가 될 것이다. 그러니 다른 방식으로 접근해야한다. 이 상태에서 front는 rear + 1을 MAX_SIZE로 나눈 나머지와 같음을 알 수 있다. 즉, 아래의 경우라면 포화상태로 true를 반환한다는 뜻이다.

bool is_full() { return front == (rear + 1) % MAX_SZIE; }
int size() { return (rear - front + MAX_SIZE) % MAX_SIZE; }

size도 복잡해졌다. 큐의 크기는 일반적인 상황에서 본다면, front가 0이고 rear가 7일 때에는 7이 된다. rear - front이다. 하지만, front가 1이고 rear가 0이 된다면? -1이 되어버린다. 이곳에 MAX_SIZE를 더해주면 드디어 큐의 크기인 7이 나오게 된다. 이는 다른말로 rear과 front의 차에서 MAX_SIZE값을 더한 뒤, MAX_SIZE로 나눈 나머지와 같다는 소리다.

 

enqueue(x)

삽입 연산은 rear를 하나 증가시키고 그 위치에 x를 추가한다. 단, MAX_SIZE를 넘게 된다면 나머지 연산을 통해 0번부터 다시 시작할 수 있도록 하자.

void enqueue(int e) {
    if (is_full()) {
        cout << "큐 포화" << endl;
        exit(1);
    }
    esle {
        rear = (rear + 1) % MAX_SIZE;
        queue[rear] = e;
    }
}

 

dequeue(), peek()

삭제 연산도 마찬가지이다. front를 증가시키고 그 값을 반환하면 된다. 마찬가지로 MAX_SIZE를 넘었을 때를 대비한다. 삭제 연산을 했다면 peek은 쉽다.

int dequeue() {
    if (is_empty()) {
        cout << "큐 공백" << endl;
        exit(1);
    }
    else {
        front = (front + 1) % MAX_SIZE;
        return queue[front];
    }
}

int peek() {
    if (is_empty()) {
        cout << "큐 공백" << endl;
        exit(1);
    }
    else {
        return queue[(front + 1) % MAX_SIZE];
    }
}

 

마지막으로 큐를 출력해주는 코드를 작성하자.

void print() {
    int size = rear;
    
    if (size <= front) size += MAX_SIZE; // rear가 front보다 앞에 있거나 같은 곳일 경우.
    cout << "현재 큐 : ";
    for (int i = front + 1; i <= size; i++) {
        cout << queue[i % MAX_SIZE] << " ";
    }
    cout << endl;
}

전체코드

#include <iostream>
#include <cstdlib>

using namespace std;

class Array_Queue {
    static const int MAX_SIZE = 256; // 큐에 저장될 요소의 최대 개수
    int queue[MAX_SIZE];
    int front, rear; // 큐의 맨 앞과 뒤를 가리킬 변수

public:
    Array_Queue() { 
        front = 0;
        rear = 0;
    }
    ~Array_Queue() { }
    void init() { // 초기화
        front = 0;
        rear = 0;
    }

    bool is_empty() { return front == rear; } // 공백 검사
    bool is_full() { return front == (rear + 1) % MAX_SIZE; } // 포화 검사
    int size() { return (rear - front + MAX_SIZE) % MAX_SIZE; } // 크기 반환

    // 삽입 연산
    void enqueue(int e) {
        if (is_full()) {
            cout << "큐 포화" << endl;
            exit(1);
        }
        else {
            rear = (rear + 1) % MAX_SIZE;
            queue[rear] = e;
        }
    }

    // 삭제 연산
    int dequeue() {
        if (is_empty()) {
            cout << "큐 공백" << endl;
            exit(1);
        }
        else {
            front = (front + 1) % MAX_SIZE;
            return queue[front];
        }
    }
    
    // 요소 반환
    int peek() {
        if (is_empty()) {
            cout << "큐 공백" << endl;
            exit(1);
        }
        else {
            return queue[(front + 1) % MAX_SIZE];
        }
    }
    
    // 큐 출력
    void print() {
        int size = rear;
    
        if (size <= front) size += MAX_SIZE; // rear가 front보다 앞에 있거나 같은 곳일 경우.
        cout << "현재 큐 : ";
        for (int i = front + 1; i <= size; i++) {
            cout << queue[i % MAX_SIZE] << " ";
        }
        cout << endl;
    }
};

int main() {
    Array_Queue aq;
    
    for (int i = 0; i < 4; i++) {
        aq.enqueue(i);
    }
    
    aq.print();
    cout << "dequeue : " << aq.dequeue() << endl;
    cout << "peek \t: " << aq.peek() << endl;
    cout << "size \t: " << aq.size() << endl;
    aq.print();
    
    return 0;
}

출력

현재 큐 : 0 1 2 3
dequeue : 0
peek    : 1
size    : 3
현재 큐 : 1 2 3

 

연결 리스트를 이용한 큐

연결리스트를 이용한 큐도 is_full() 연산이 의미가 없다는 것을 알아두자. 이번에도 스택처럼 구조체를 사용해서 노드를 표현해보자. 스택과는 달리 노드를 가리킬 포인터가 2개(front, rear)가 되어야 한다.

struct Node {
    int data;
    Node* link;
};

Node* front;
Node* rear;

 

init()

초기화는 front와 rear를 NULL로 초기화시켜주자.

void init() {
    front = NULL;
    rear = NULL;
}

 

 

is_empty()

공백 검사는 front와 rear이 둘다 NULL인지 확인하면 된다. size()는 스택과 비슷하지만, 다른 점이라면 큐는 front에서부터 시작해서 마지막 노드까지 따라간다는 것 뿐이다.

bool is_empty() { return front == NULL; }

int size() {
    int count = 0;
    
    for (Node *n = front; n != NULL; n = n->link) {
        count++;
    }
    return count;
}

 

enqueue(x)

삽입 연산은 아래 단계에 따라 행해진다.

 

1. 새로운 노드를 하나 만들어 값을 저장하고, link가 NULL을 가리킨다.
2. 큐가 공백이라면 front와 rear이 둘 다 새 노드를 가리킨다. 아니라면 마지막 노드가 새 노드를 가리키고 rear가 새 노드를 가리키게 한다.

void enqueue(int element) {
    Node* node = new Node;
    node->data = element;
    node->link = NULL;
    
    if (is_empty()) { // 큐가 공백일 경우
        front = node;
        rear = node;
    }
    else { // 큐에 노드가 있을 경우
        rear->link = node;
        rear = node;
    }
}

 

dequeue(), peek()

삭제 연산은 front를 뒤로 밀어주고 앞에 있던 노드를 반환하면 된다.

 

1. front가 가리키는 노드를 임시로 저장한다.
2. front가 다음 노드를 가리킨다.
3. 할당 해제해주고 값을 반환한다.

int dequeue() {
    Node* node;
    int item;
    
    if (is_empty()) { // 큐 공백일 때의 예외처리
        cout << "큐 공백" << endl;
        exit(1);
    }
    else {
        node = front; // node가 맨 앞 노드를 가리키고
        front = node->link; // front는 바로 뒤의 노드를 가리킨다.
        
        item = node->data;
        delete node;
        return item;
    }
}

peek()은 그저 맨 앞의 요소만 반환하면 되므로 생략하였다. 물론, 큐 공백에 대한 예외처리를 해야 한다. 전체코드에 그 함수를 작성해놨다. 마지막으로 큐를 출력해줄 함수를 만들어 주자.

void print() {
    cout << "현재 큐 : ";
    for (Node* n = front; n != NULL; n = n->link) {
        cout << n->data << " ";
    }
    cout << endl;
}

전체코드

#include <iostream>
#include <cstdlib>

using namespace std;

class Linked_Queue {
    struct Node {
        int data;
        Node* link;
    };

    Node* front;
    Node* rear;
    
public:
    Linked_Queue() {
        front = NULL;
        rear = NULL;
    }
    ~Linked_Queue() { }
    
    void init() {
        front = NULL;
        rear = NULL;
    }
    
    bool is_empty() { return front == NULL; } // 공백 검사
    
    // 큐의 크기
    int size() {
        int count = 0;
    
        for (Node *n = front; n != NULL; n = n->link) {
            count++;
        }
        return count;
    }
    
    // 삽입
    void enqueue(int element) {
        Node* node = new Node;
        node->data = element;
        node->link = NULL;
    
        if (is_empty()) { // 큐가 공백일 경우
            front = node;
            rear = node;
        }
        else { // 큐에 노드가 있을 경우
            rear->link = node;
            rear = node;
        }
    }
    
    // 삭제
    int dequeue() {
        Node* node;
        int item;
    
        if (is_empty()) { // 큐 공백일 때의 예외처리
            cout << "큐 공백" << endl;
            exit(1);
        }
        else {
            node = front; // node가 맨 앞 노드를 가리키고
            front = node->link; // front는 바로 뒤의 노드를 가리킨다.
        
            item = node->data;
            delete node;
            return item;
        }
    }
    
    // 맨 앞의 값
    int peek() {
        if (is_empty()) {
            cout << "큐 공백" << endl;
            exit(1);
        }
        else {
            return front->data;
        }
    }
    
    // 큐 출력
    void print() {
        cout << "현재 큐 : ";
        for (Node* n = front; n != NULL; n = n->link) {
            cout << n->data << " ";
        }
        cout << endl;
    }
};

// 큐 테스트
int main() {
    Linked_Queue lq;
    
    for (int i = 0; i < 6; i++) {
        lq.enqueue(i);
    }
    
    lq.print();
    cout << "dequeue : " << lq.dequeue() << endl;
    cout << "peek \t: " << lq.peek() << endl;
    lq.print();
    cout << "현재 큐 크기 : " << lq.size() << endl;
    
    return 0;
}

출력

현재 큐 : 0 1 2 3 4 5
dequeue : 0
peek    : 1
현재 큐 : 1 2 3 4 5
현재 큐 크기 : 5

 

큐의 활용

컴퓨터에서 데이터를 주고받을 때 사용하는 메모리 영역을 버퍼(Buffer)라고 하는데, 이 버퍼가 큐이다.

키보드 타이핑도 입력 버퍼라는 큐를 이용한 방법이다. 이 외에도 실시간 스트리밍 시 버퍼링이 걸리는 것과, 컴퓨터와 프린터 사이의 인쇄 큐 등 여러 곳에서 많이 사용된다.

 

 

[Reference]

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788970509419&orderClick=LAG&Kc= 

자료구조 - 교보문고

 

 

728x90