원형 큐 c++로 만들기

원형 큐 (물론 여기서 구현할거는 queue size를 원하는 만큼 늘릴수 있다.)

우선 원형 큐(Queue)에 들어갈 노드(Node)부터 정의를 하였다 (linked list로 원형 큐 구현함)

#include <iostream>

using namespace std;

// Node that will go inside of circular queue
struct Node {
    string name;
    int items;
    Node *next;
    Node(string n, int i, Node *nextNode=nullptr): name(n), items(i), next(nextNode) {};
};

노드에는 데이터와 다음 노드로 이어주는 next가 있다.

데이터 부분은 이름과 아이템 개수로 정의 했으며

next는 노드를 가리키는 포인터이다.

그 후 constructor를 구현했는데, 스트링과 정수를 받으면 포인터는 nullptr이 되도록 default condition을 넣어주었다.

 

이제 그 밑에 원형큐 클래스를 만들어보았다.

아직은 클래스 틀만 만든거라 아래 코드는 돌아가지 않는다.

public: 밑의 두줄은 각각 constructor과 destructor이다.

constructor에서 볼 수 있듯이 Queue가 생길때 tail이 생성이 되는데 아직 값이 없으므로 nullptr로 지정해준다.

보통 맨 앞의 노드를 가리시는 말로 헤드(head)를 많이 쓰는데, 여기서는 테일(tail)을 지정했다.

원형큐의 특성상 그런건데, 원형큐는 헤드와 테일이 이어져 있기 때문이다. 즉 테일의 다음 노드가 헤드인것.

그래서 Enqueue에서 노드를 tail뒤에 붙일때와 Dequeue에서 head를 내보낼때

head노드는 tail->next로 접근한다.

PeekHead()와 IsEmpty()는 코드가 짧아서 미리 구현해놓았다.

자세한 설명은 아래 참고.

#include <iostream>

using namespace std;

struct Node {
    string name;
    int items;
    Node *next;
    Node(string n, int i, Node *nextNode=nullptr): name(n), items(i), next(nextNode) {};
};

class Queue {
private:
    Node *tail;
public:
    Queue(): tail(nullptr) {};
    ~Queue() {};
    void Enqueue(string s, int i) {
    	//Node를 생성해서 Queue에 더한다
        //처음에는 노드가 하나이므로 맨앞(tail->next)에 더해주고
        //tail역시 같은 노드여야하므로 tail을 만들고 tail->next도 자기자신인 tail로 해준다.
        
        //하나 이상일시 tail뒤에 새로운 노드를 더해주고 연결고리들을 수정해준다.
    };
    Node* Dequeue() {
    	//맨 앞 (tail->next)의 노드를 없애고
        //없어진 노드는 되돌려준다.
        //그래서 method/function(함수) 타입이 Node*(노드 포인터이다)
        //노드가 하나일시 tail도 없애줘야하므로 따로 조건을 만들어준다.
    };
    string ToString() {
    	//있는 노드들을 쭉 읽고 결과를 스트링으로 돌려준다.
    };
    Node* PeekHead() {
    	//맨 앞의 노드를 볼 수 있게 해준다.
        return tail->next;
    };
    bool IsEmpty() {
    	//큐에 아무것도 없는지 확인시켜준다.
        //처음에 Queue를 만들때 tail = nullptr이라고 했는데
        //tail이 nullptr이면 tail==0이 참 값이 되고
        //tail에 무언가가 지정되어있으면 (Queue에 노드가 들어가있으면) 거짓 값이 된다.
        return tail == 0;
    }
};

아래의 코드는 완성된 Queue클래스이다.

#include <iostream>
#include <sstream>

using namespace std;

struct Node {
    string name;
    int items;
    Node *next;
    Node(string n, int i, Node *nextNode=nullptr): name(n), items(i), next(nextNode) {};
};

class Queue {
private:
    Node *tail;
public:
    Queue(): tail(nullptr) {};
    ~Queue() {};
    void Enqueue(string s, int i) {
        Node *newNode = new Node(s, i);
        if (tail == 0) {
            tail = newNode;
            tail->next = newNode;
        }
        else {
            newNode->next = tail->next;
            tail->next = newNode;
            tail = newNode;
        }
    };
    Node* Dequeue() {
        Node *popped = tail->next;
        if (tail->next == tail) {
            tail = nullptr;
        }
        else {
            tail->next = popped->next;
        }
        popped->next = nullptr;
        return popped;
    };
    string ToString() {
        string str = "";
        if (tail == 0) {
            return "()";
        }
        for (Node* current = tail->next; current != tail; current = current->next) {
            if (current != tail->next) {
                str += "->";
            }
            str = str + "(" + current->name + ", " + to_string(current->items) + ")";
        }
        if (tail != tail->next)
            str += "->";
        str = str + "(" + tail->name + ", " + to_string(tail->items) + ")";
        return str;
    };
    Node* PeekHead() {
        return tail->next;
    };
    bool IsEmpty() {
        return tail == 0;
    }
};

int main() {
    Queue cq;
    int size = 0;
    //Enqueue
    cq.Enqueue("Jane", 2);
    size++;
    cq.Enqueue("Zed", 10);
    size++;
    cq.Enqueue("Tom", 6);
    size++;
    cq.Enqueue("Jake", 20);
    size++;

    //ToString
    cout << cq.ToString() << endl;

    //PeekHead
    Node *currentHead = cq.PeekHead();
    cout << "(" << currentHead->name << ", " << currentHead->items << ")" << endl;

    //Dequeue and ToString
    while (!cq.IsEmpty()) {
        Node *popped = cq.Dequeue();
        cout << "(" << popped->name << ", " << popped->items << ")" << endl;
        cout << cq.ToString() << endl;
        size--;
    }
}

코드가 돌아가는걸 보고 싶으면 main에서 테스트 해보면 된다.

지금은 임의로 이름-items을 넣고서 돌려봤는데, 돌아가는걸 확인하였다.

시간이 되면 이걸 활용해서 문제 하나를 풀어볼 예정이다.