#1 큐 - 큐의 기본 지식 및 배열 기반의 큐

1. 큐 설명 및 주요 연산

스택은 데이터의 입출력이 한곳에서 이루어진다. 그리고 먼저 들어간 데이터가 가장 마지막에 나오는 FILO(First In Last Out) 형식의 자료구조이다.

반대로 큐는 입력과 출력이 따로 이루어지고, 먼저 들어간 데이터가 가장 먼저 나오는 FIFO(First In First Out)구조이다. 즉 입력한 순서대로 처리를 한다.

큐를 사용하는 이유는 데이터 입력이 폭주할 경우 데이터를 보관할 장소로 적합하기 때문이다. 이러한 구조는 버퍼에서도 확인할 수 있다.

큐는 FIFO(First In First Out) 또는 선입선출 자료구조라고 한다. 우리말로는 '대기행렬' 이라고도 한다.

큐는 다음과 같이 생겼다.

큐의 가장 앞 요소를 전단(Front), 가장 마지막 요소를 후단(Rear) 라고 한다. 마치 자동차의 전면, 후면 김서리방지? 에어컨 스위치에 붙어있는 이름과 똑같다.

큐는 후단에서 데이터 삽입이, 전단에서 제거가 이루어진다. 

삽입하는 방법은 아래 그림처럼 후단에 새 노드를 덧붙여 새로운 후단을 만든다.

제거 또한 똑같다. 전단에 있는 노드를 제거하고 뒤 노드를 새로운 전단으로 만들면 된다.

2. 배열 기반 큐 구현하기

이제 배열 기반의 큐를 구현해보자.

1). 구조 구현하기

우선 Xcode를 열고 Queue 프로젝트를 만든다. 그다음 Queue.cpp과 Queue.hpp 파일을 만들어준다.

먼저 표준 라이브러리를 추가한 다음 큐의 각 요소를 표현할 노드를 구현한다. 노드에는 각 요소가 숫자를 가질수 있도록 데이터 변수만 만들어주면 된다.

(Queue.hpp에 추가)

#include <stdlib.h>
 
class Node {
public:
    int Data;
};

그 다음은 큐의 구조를 만들어보자.

(Queue.hpp에 추가)

class Queue {
private:
    int capacity;
    int front;
    int rear;
    Node *nodes;
};

큐 내부 변수의 용도는 아래와 같이 사용된다. capacity가 3인 큐의 노드 배열을 자유저장소에 할당하고, 그 노드의 front는 전단을, rear은 후단을 가리킨다.

2) 내부함수 구현하기

이번에는 큐 데이터를 자유 저장소에 할당하고 제거하는 함수다.

(Queue.hpp Queue 클래스에 추가)

public:
    Queue(int _capacity);
    void DestroyQueue();
 

(Queue.cpp에 추가)

Queue::Queue(int _capacity) {
    nodes = (Node*)malloc(sizeof(Node) * _capacity);
    front = 0;
    rear = 0;
    capacity = _capacity;
}
 
void Queue::DestroyQueue() {
    free(nodes);
}
 

이제 큐 삽입과 삭제를 구현해보자. 위에 있는 삽입, 삭제 사진을 보며 구현하면 쉽다.

(Queue.hpp Queue 클래스 public 멤버에 추가)

void EnQueue(int newData);
int DeQueue();

(Queue.cpp에 추가)

void Queue::EnQueue(int newData) {
    if(rear > capacity) {
        printf("Queue is full\n");
        return;
    }
    nodes[rear++].Data = newData;
}
 
int Queue::DeQueue() {
    if(front > capacity) {
        printf("Queue is empty\n");
        return -1;
    }
 
    return nodes[front++].Data;
}

3. 테스트 해보기

이제 구현한 큐로 테스트를 해보자. 10의 용량을 가진 큐를 생성하고, 그 안에 0~11까지 총 12개의 데이터를 넣어보고, 12번 DeQueue를 진행해 보자.

실행 결과를 예상해보면 0~9까지의 데이터가 큐에 들어가고, "Queue is full" 이라는 경고가 2번 출력되며, 0~9가 출력되고 "Queue is empty" 경고와 -1이 2번씩 출력될 것이다.

(main.cpp)

#include <iostream>
#include "Queue.hpp"
 
int main(int argc, const char * argv[]) {
    Queue queue(10);
 
    for(int i=0;i<12;i++) {
        queue.EnQueue(i);
    }
 
    for(int i=0;i<12;i++) {
        std::cout << "DeQueue : " << queue.DeQueue() << std::endl;
    }
 
    queue.DestroyQueue();
}

실행 결과는 아래와 같다. 우리가 예상한 대로 출력됐다.

이번시간에는 큐의 구조를 살펴보고 배열 기반의 큐를 구현해보았다. 다음시간에는 우리가 구현한 배열 기반의 큐의 문제점과 해결 방안에 대해 알아보자.