C++로 구현하는 자료구조!!!큐(Queue)편@@@

강력한 언어, C++로 구현하는 자료구조

C++로 구현하는 Queue 자료구조

스택 포스팅에 이어서 큐 관련해서 업로드 이어나가도록 하겠습니다~ 큐 또한 스택과 동일하게 STL안에 정의되어 있기 때문에 간단하게 쓸 수 있지만, 그래도 직접 구현해보고 사용하는 것만큼, 좋은 게 없습니다. 물론 이해도도 그만큼 따라 올라가는 것이고요~

 

hazarddev.tistory.com/20?category=794281

큐가 뭔가요!!(c_queue)

이미 C언어로 큐를 구현하긴 했으나, 객체지향 개념을 얹어서 구현해보는 것은 또 다른 차원의 개념입니다. 물론 C언어로도 한번 작성해보시는 것을 추천드립니다.

 

Queue에 관련해 설명을 드리자면, 대기열이 존재하고 대기열의 순서대로 작업이 진행된다고 보시면 됩니다. 예를 들자면, 은행에 창구 관련 업무를 보러 간 상황에서 순번을 뽑지 않습니까? 그렇다면 순번대로 업무가 순차적으로 처리되고 먼저 온 사람은 당연히 먼저 은행을 나가게 됩니다. 즉, 큐 구조는 선형 자료구조의 형태를 띠며, FIFO(first in, first out) 형태를 지닙니다.

 

큐의 추상적 형태 출처 : geeksforgeeks.org

위와 같은 추상적 형태를 띠는 것이 큐 자료구조의 형태라고 보시면 됩니다. 그중에서도 가장 많이 구현되는 Circle Queue(원형 큐, 순환 큐라고도 함)을 class로 구현하고 stl내부에 정의되어 있는 queue로도 정의할 예정입니다.

 

1. Class로 구현하는 Queue

우선 클래스로 구현하기 전, 설계를 해봐야겠죠? 클래스로 구현하기 때문에 크게 데이터와 그다음 노드를 가리키는 포인터 변수를 가지고 있는 Node클래스를 선언하고, Queue를 담당하는, 컨트롤할 수 있는 멤버 함수, 멤버 변수를 담은 Queue클래스를 선언할 예정입니다. 우선 노드 클래스부터 보겠습니다.

 

class Node{
    public:
        int val;
        Node *nextVal;
};

template<class T> class CircleQueue{ 
    public:
       explicit CircleQueue(){front = NULL; rear = NULL;}
        ~CircleQueue(){delete []front,rear;}
        Node *front, *rear;
};
 
template<typename T> void push(CircleQueue<T> *q, const T val){
    Node * tempNode = new Node;
    tempNode->val = val;
    if(q -> front == NULL) q -> front = tempNode;
    else q -> rear -> nextVal = tempNode;
    q->rear = tempNode;
    q->rear -> nextVal = q->front;
}
template<typename T> T pop(CircleQueue<T> *q){
    if(q -> front == NULL){
        std::cout << "Queue is Empty" << std::endl;
        return 0;
    }
    T value;
    if(q -> front == q->rear){
        value = q->front->val;
        free(q->front);
        q->front = NULL; q->rear = NULL;
    }else{
        Node *temp = q -> front;
        value = temp->val;
        q->front = q->front -> nextVal;
        q->rear -> nextVal = q->front;
        free(temp);
    }
    return value;
}
 
template<typename T> void show(CircleQueue<T> * q){
    Node *tempNode = q -> front;
    while(tempNode -> nextVal != q->front){
        std::cout << tempNode->val << " ";
        tempNode = tempNode -> nextVal;
    }
    std::cout << tempNode -> val << std::endl;
}

우선 우리가 구현하고자 하는 Circle Queue의 추상적 형태는 위와 같습니다. front변수는 큐의 맨 첫 번째를 가리키며 동시에, 제일 먼저 제거될 변수를 가리킵니다. Rear변수는 제일 늦게 들어온 객체를 가리키며, 이는 front에서 변수가 제거되면, rear변수는 감소되어, 만약 가리키는 인덱스가 5였다면, 4를 가리키게 됩니다. 

그렇다면, 멤버 함수를 봅시다!

 

push() : tempNode를 보게 되면 새로운 노드로 선언되고, 인자로 들어온 데이터를 본인의 데이터로 삼습니다. 그리고 front변수가 NULL일 때, front변수는 tempNode가 됩니다. 아니라면, rear의 그다음 객체로 tempNode를 가리키고, rear는 tempNode가 됩니다. 그리고 rear의 다음 객체는 front를 가리키며 원형 구조를 이루게 됩니다!

 

pop() : front가 널 일 때는 당연히 큐가 empty statement이기 때문에 데이터를 빼낼 수 없겠죠? 그래서 표준 출력 함수를 이용해 비어있다는 것을 사용자에게 알려준 후 종료합니다. 그게 아니라면, 큐의 front와 rear와 같다면 front객체에 할당된 메모리를 해제하며 front, rear를 NULL초기화한 뒤 제거된 데이터를 반환하며 종료합니다. 즉, 위와 같은 상황이 아닐 때는 push와 비슷하게 새로운 노드를 선언해 front를 복사하고 연결부를 접합, 병합한 뒤 메모리를 할당 해제한 후 종료합니다.

 

show() : 그 별 다른 역할을 하는 함수는 아니고, 순차적으로 데이터를 출력하는 함수입니다...ㅎㅎㅎ

 

int main(){
    CircleQueue<int> * q = new CircleQueue<int>();
    push(q, 5);push(q, 6);push(q, 7);
    show(q);
    pop(q);
    show(q);
}
 
RESULT > 
5 6 7
6 7

int main(){
    std::queue<int> newQueue;
    newQueue.push(1); <--- 데이터 삽입
    newQueue.push(2);
    newQueue.push(3);
    newQueue.push(4);
    newQueue.push(5);
    while (!newQueue.empty()){ <--- 빈 상태인지 확인
        std::cout << newQueue.front() << std::endl;
        newQueue.pop(); <-- 데이터 제거
    }
    return 0;
}
 
RESULT > 
1
2
3
4
5

 

 

이상 큐 자료구조에 대해서도 포스팅을 마쳤는데요, 이해가 잘 안 가거나 하시면 댓글로 남겨주시면 친절히 답변드리도록 하겠습니다. 자료구조를 왜 배우지 왜 필요하지 이 생각이 드시는 분들이 많으실 수 있습니다. 맞습니다 물론 실제 프로그램을 이렇게 구현하지는 않죠, 하지만 프로그램을 구현하기 위해서 연습하는 과정이라고 생각하시면 됩니다!! 감사합니다!!

 

 

hazarddev.tistory.com/39

C++로 구현하는 자료구조!!!연결리스트(LinkedList)@@