[C++] 자료구조 Queue(큐) 만들어 보기

자료구조에서 Queue는 FIFO(First In First Out)의 구조를 가집니다.

먼저 들어온 자료는 먼저 처리되는 형식입니다.

 

그렇기 때문에 자료의 삽입은 구조의 맨 뒤에서, 자료의 삭제는 맨 앞에서 이루어집니다.

 

C++ 에서 포인터를 이용하여 Queue 만들기

Queue를 포인터를 이용해 만들어 보겠습니다.

여러 데이터를 사용할 수 있게 제네릭으로 구성하였습니다.

Queue는 위와 같은 그림처럼 이루어져 있습니다.

Queue라는 구조 안에 Node라는 데이터들이 줄지어 있습니다.

이 Node들은 단방향으로 길게 이어져 있으며 Queue는 이 Node들의 시작 지점(Start)과 끝 지점(End)을 기억하고 있습니다.

데이터의 삭제는 시작 지점(Start)에서, 삽입은 끝 지점(End)에서 이루어집니다.

 

template <class T>
class Node
{
private:
    // 데이터
    T m_data;
    // 다음 노드를 가리키는 포인터
    Node<T>* m_ptrNext;

public:
    // 생성자
    Node() : m_ptrNext(nullptr)
    { 
        printf("Create\n"); 
    }
    Node(T data, Node<T>* ptrNext = nullptr) : m_data(data), m_ptrNext(ptrNext) 
    {
        printf("Create\n"); 
    }
    // 소멸자
    ~Node() 
    {
        printf("Delete\n");
    }

    // 데이터를 반환하는 함수
    T GetData() 
    { 
        return m_data;
    }
    // 데이터를 설정하는 함수
    void SetData(T data)
    { 
        m_data = data;
    }
    // 다음 노드를 가리키는 포인터를 설정하는 함수
    void SetNext(Node<T>* ptr)
    { 
        m_ptrNext = ptr;
    }
    // 다음 노드를 가리키는 포인터를 반환하는 함수
    Node<T>* GetNext()
    { 
        return m_ptrNext;
    }
};

먼저 Queue를 구성하는 Node에 관한 Class 입니다.

Node Class는 데이터와 다음 노드의 포인터를 가지고 있습니다.

 

template <class T>
class MyQueue
{
private:
    // 시작 노드 포인터
    Node<T>* m_pStart;
    // 끝 노드 포인터
    Node<T>* m_pEnd;
    // 큐의 전체 크기
    int m_nSize;

public:
    // 생성자
    MyQueue() : m_pStart(nullptr), m_pEnd(nullptr), m_nSize(0) {}
    // 소멸자
    ~MyQueue() { Clear(); }

    int GetSize() const { return m_nSize; }

    T GetFront() const { return m_pStart ? m_pStart->GetData() : NULL; }
    T GetEnd() const { return m_pEnd ? m_pEnd->GetData() : NULL; }

    // 데이터를 Queue에 쌓는 함수
    void EnQueue(T data)
    {
        Node<T>* pData = new Node<T>(data);

        // 시작이 null인 경우는 처음 생성한 케이스
        // (시작이 null인 경우는 끝도 null)
        if (m_pStart == nullptr)
        {
            m_pStart = pData;
            m_pEnd = pData;
        }
        // 데이터가 있는 경우
        else
        {
            // 끝 다음에 현재 생성한 데이터의 포인터를 위치한 후
            // 새로운 데이터를 끝 포인터로 지정
            m_pEnd->SetNext(pData);
            m_pEnd = m_pEnd->GetNext();
        }

        m_nSize++;
    }

    // Queue에 있는 데이터를 빼는 함수
    T DeQueue()
    {
        if (m_pStart != nullptr)
        {
            // 시작 위치의 데이터 포인터를 임시로 기록
            Node<T>* pData = m_pStart;
            // 시작 위치의 데이터를 저장
            T data = m_pStart->GetData();

            // 시작 데이터의 다음 데이터가 있다면
            if (m_pStart->GetNext() != nullptr)
            {
                // 시작 데이터 포인터를 다음 데이터 포인트로 이동
                m_pStart = m_pStart->GetNext();
                // 이전의 시작 데이터 포인터를 삭제
                delete pData;
                pData = nullptr;
            }
            // 시작 데이터가 마지막 데이터라면
            else
            {
                delete m_pStart;
                m_pStart = nullptr;
                m_pEnd = nullptr;
            }

            m_nSize--;
            return data;
        }
        else
        {
            return NULL;
        }
    }

    // 전체 데이터 클리어
    void Clear()
    {
        while (m_pStart != nullptr)
        {
            if (m_pStart->GetNext() != nullptr)
            {
                Node<T>* pData = m_pStart;

                m_pStart = m_pStart->GetNext();
                delete pData;
                pData = nullptr;
            }

            if (m_pStart->GetNext() == nullptr)
            {
                delete m_pStart;
                m_pStart = nullptr;
                m_pEnd = nullptr;
            }
        }

        m_pEnd = nullptr;

        m_nSize = 0;
    }
};

Node들을 이용해서 Queue를 구성해보았습니다.

 

int main(void)
{
    MyQueue<int> queue;

    queue.EnQueue(1);
    queue.EnQueue(2);
    queue.EnQueue(3);
    queue.EnQueue(4);
    queue.EnQueue(5);

    printf("Front : %d\n", queue.GetFront());
    printf("End : %d\n", queue.GetEnd());
    printf("Size : %d\n\n", queue.GetSize());

    int nDeq = queue.DeQueue();
    printf("Dequeue : %d\n", nDeq);
    printf("Front : %d\n", queue.GetFront());
    printf("End : %d\n", queue.GetEnd());
    printf("Size : %d\n\n", queue.GetSize());

    printf("Enqueue(10)\n");
    queue.EnQueue(10);
    printf("Front : %d\n", queue.GetFront());
    printf("End : %d\n", queue.GetEnd());
    printf("Size : %d\n\n", queue.GetSize());

    queue.Clear(); 

    return 0;
}

포인터로 구성했기 때문에 꼭 Create와 Delete의 개수가 같아야합니다.

 

 

Queue Test