Queue

Queue 전체 구조

LIFO(Last In First Out) 구조로 먼저 들어간 데이터가 먼저 추출되는 구조를 가집니다.

Node

template <typename T>
class Node { // 노드 클래스
public:
    Node<T>* m_Next;
    T m_Data;

public:
    Node() {
        m_Next = nullptr;
    };
    Node(const T& data) {
        m_Data = data;
        m_Next = nullptr;
    };
    ~Node() {
        m_Next = nullptr;
    }
};

Node* m_Next 변수는 다음으로 가는 변수의 주소를 담고 있습니다. 즉 아래에서부터 데이터를 꺼내므로 자신의 위에있는 Node의 주소를 가르키며 T m_Data 변수는 데이터 값을 가지고 있습니다.

Queue

template <typename T>
class Queue {
private:
    Node<T>* m_Front; // 앞
    Node<T>* m_Back; // 뒤

public:
    Queue() {
        m_Front = nullptr;
        m_Back = nullptr;
    }
    ~Queue() {
        Node<T>* moveNode = m_Front;
        while (moveNode != nullptr) {
            Node<T>* temp = moveNode;
            moveNode = moveNode->m_Next;
            delete temp;
        }
    }

Node<T>* m_Front 변수는 현재 데이터들 중에서 가장 먼저 들어온 노드의 주소값을 가지고 있고 Node* m_Back 변수는 가장 마지막에 들어온 노드의 주소값을 가지고 있습니다. 생성자에서는 null로 초기화 하고 소멸자에서는 노드를 하나씩 메모리 해제 합니다.

Node Push

 void push(T data) {
        Node<T>* newNode = new Node<T>(data);
        if (m_Back == nullptr) {
            m_Front = newNode;
        }
        else {
            m_Back->m_Next = newNode;
        }
        m_Back = newNode;
    }

매개변수로 받은 데이터를 가진 새로운 노드를 만듭니다. 만약 큐가 비어 있다면 m_Front에 새로운 노드의 주소를 가르키고 큐기 비어있지 않다면 기존 m_Back과 새로운 노드의 주소를 m_Next로 연결하고 m_Back에 새로운 주소를 가르키게 합니다.

Node Pop

 T pop() {
        if (m_Front == nullptr) {
            throw runtime_error("큐가 비어 있습니다.");
        }
        else {
            T data = m_Front->m_Data;

            Node<T>* temp = m_Front;
            m_Front = m_Front->m_Next;
            delete temp;

            if (m_Front == nullptr) {
                m_Back = nullptr;
            }

            return data;
        }
    }

m_Front에서 데이터를 꺼낸 후 m_Front가 가르키는 주소를 큐 위에 있는 노드의 주소로 옮기고 기존 m_Front의 메모리를 해제합니다.

Node Front

 T front() {
        if (m_Front == nullptr) {
            throw runtime_error("큐가 비어 있습니다.");
        }
        else {
            return m_Front->m_Data;
        }
    }

m_Front의 데이터를 꺼내서 return 합니다.

Node isEmpty

 bool isEmpty() {
        if (m_Front == nullptr) {
            return true;
        }
        else {
            return false;
        }
    }

m_Front가 null이면 true 아니면 false를 리턴합니다.

Node print

void print() {
        Node<T>* moveNode = m_Front;
        cout << "queue 데이터 출력" << endl;
        while (moveNode != nullptr) {
            cout << moveNode->m_Data << " ";
            moveNode = moveNode->m_Next;
        }
        cout << endl;
    }

큐의 맨 아래 node부터 m_Next지역 변수를 이용해서 하나씩 위로 올라가면서 data 값을 출력합니다.