20210802 Stack, Queue, CircleQueue

안녕하세요 틴구입니다!

오늘은 링크드에 이어서 Stack, Queue, CirlceQueue에 대해서 알아보도록 할게요.

먼저 Stack부터 알아볼까요?

Stack

// Stack.h (인라인으로 생성해준다.)

#pragma once

#include <assert.h>

template <typename T>
class CStackNode
{

    // CStack에서 CStackNode의 private을 이용하기 위해 friend를 해준다.
    template <typename T>
    friend class CStack;
private:
    CStackNode() :
        m_Next(nullptr)
    {
    }
    ~CStackNode()
    {
    }

private:
    CStackNode<T>* m_Next;
    T                      m_Data;
};

template <typename T>
class CStack
{
public:
    CStack()
    {
        m_LastNode = nullptr;
        m_Size = 0;
    }
    // 소멸자로 clear를 반드시 해준다.
    ~CStack()
    {
        clear();
    }
    
private:
    CStackNode<T>* m_LastNode;  // 마지막 노드
    int m_Size;  // 전체 노드의 개수

public:
    void push(const T& data)
    {
        // 노드를 저장할 변수를 만들어준다
        CStackNode<T>* Node = new CStackNode<T>;
        // 만들어준 노드에 데이터를 할당한다.
        Node->m_Data = data;
        // 노드 다음을 라스트노드로 설정한다.
        Node->m_Next = m_LastNode;
        // 라스트노드를 노드로 갱신해준다.
        m_LastNode = Node;
        // ++사이즈 해준다.
        ++m_Size;
    }

    T& top() const
    {
        if (empty())
            assert(false);
        // 마지막 노드의 데이터를 리턴해준다.
        return m_LastNode->m_Data;
    }

    void pop()
    {
        if (empty())
            assert(false);
        // 지우기 전에 Next노드를 LastNode의 다음노드로 설정한다.
        CStackNode<T>* Next = m_LastNode->m_Next;
        // 마지막노드를 삭제한다.
        delete m_LastNode;
        // 삭제한자리에 설정해두었던 Next노드를 불러온다.
        m_LastNode = Next;
        // 사이즈를 하나 줄인다.
        --m_Size;
    }

    bool empty() const
    {
        return m_Size == 0;
    }

    int Size() const
    {
        return m_Size;
    }

    void clear()
    {
        // 마지막노드가 nullptr이 아닐때까지 돌린다.
        while (m_LastNode)
        {
            // pop이랑 동일
            CStackNode<T>* Next = m_LastNode->m_Next;

            delete m_LastNode;

            m_LastNode = Next;
        }
        // 전부 삭제되었으면 while문을 빠져나오게 되고 노드가 없는것을 의미하니깐
        // m_Size = 0을 해준다.
        m_Size = 0;
    }
};


main.cpp


#include <iostream>
#include "Stack.h"

int main()
{
    CStack<int> StackInt;

    // 0 ~ 9까지의 숫자를 push에 넣어준다.
    for (int i = 0; i < 10; ++i)
    {
        StackInt.push(i);
    }

    // m_Size가 0이 아닐때까지 돌려준다
    while (!StackInt.empty())
    {
        // 스택의 경우 마지막에 넣어준 숫자부터 pop을 통해 -가 되어 출력이 된다.
        // 결국 9 ~ 0 순서로 출력이 되게 된다.
        std::cout << StackInt.top() << std::endl;
        StackInt.pop();
    }
    return 0;
}

 

Queue

Queue.h (인라인으로 만든다)

#pragma once

#include <assert.h>

template <typename T>
class CQueueNode
{
    template <typename T>
    friend class CQueue;
private:
    CQueueNode() :
        m_Next(nullptr)
    {
    }
    ~CQueueNode()
    {
    }

private:
    CQueueNode<T>* m_Next;
    T m_Data;
};

template <typename T>
class CQueue
{
public:
    CQueue()
    {
        m_FirstNode = nullptr;
        m_LastNode = nullptr;
        m_Size = 0;
    }
    ~CQueue()
    {

    }

private:
    CQueueNode<T>* m_FirstNode;
    CQueueNode<T>* m_LastNode;
    int m_Size;

public:
    void push(const T& data)
    {
        // 데이터를 받아올 변수를 생성한다.
        CQueueNode<T>* Node = new CQueueNode<T>;
        // 변수에 데이터 값을 넣어준다.
        Node->m_Data = data;

        // 처음에 LastNode를 nullptr 해줬기 때문에
        // 첫 시작에는 동작하지 않고 아래에서 FirstNode가 Node값을 받아오게 되면
        // 그 이후로 동작이 된다.
        if (m_LastNode)
            m_LastNode->m_Next = Node;

        // 생성자에서 m_FirstNode를 nullptr로 설정해 두었기때문에 !을 붙여서
        // 처음 시작에만 동작이 되도록 설정을 한다.
        if (!m_FirstNode)
            m_FirstNode = Node;
        
        m_LastNode = Node;

        ++m_Size;
    }

    T& front() const
    {
        if (empty())
            assert(false);

        // m_FistNode값의 데이터를 리턴한다.
        return m_FirstNode->m_Data;
    }

    void pop()
    {
        if (empty())
            assert(false);

        // 삭제할 다음 노드를 얻어오기위해서 Next 변수를 생성한다.
        CQueueNode<T>* Next = m_FirstNode->m_Next;


        // m_FirstNode를 삭제한다.
        delete m_FirstNode;


        // 삭제한 m_FirstNode 자리에 미리 설정해둔 Next값을 얻어온다.
        m_FirstNode = Next;

        // 만약에 다 삭제가 되었다면 m_FirstNode가 0이 되기 때문에 !을 붙여주어
        // true가 되어 동작되게 만들어 m_LastNode도 nullptr을 시켜준다.
        if (!m_FirstNode)
            m_LastNode = nullptr;

        --m_Size;
    }

    bool empty() const
    {
        return m_Size == 0;
    }

    int Size() const
    {
        return m_Size;
    }

    void clear()
    {
        // m_FirstNode가 있으면 동작되게 while문으로 구성을 한다.
        while (m_FirstNode)
        {
            // 삭제할 m_FirstNode의 다음 노드를 Next변수로 만들어둔다.
            CQueueNode<T>* Next = m_FirstNode->m_Next;

            // m_FirstNode를 삭제한다.
            delete m_FirstNode;

            // 삭제한 m_FirstNode에 Next값을 받아온다.
            m_FirstNode = Next;
        }
        // 다 삭제가 되었다면 while문을 빠져나오게 되고
        // m_LastNode, m_Size 를 nullptr, 0으로 초기화 시켜준다.
        m_LastNode = nullptr;
        m_Size = 0;
    }
};


main.cpp


#include <iostream>
#include "Queue.h"

int main()
{
    CQueue<int> Queue;

    for (int i = 0; i < 10; ++i)
    {
        // 0 ~ 9까지의 숫자 데이터를 넣어준다.
        Queue.push(i);
    }

    // 넣어준 데이터의 노드가 0일때까지 돌려준다.
    while (!Queue.empty())
    {
        // Queue의 경우는 선입 선출이므로 front를 출력하면 0부터 출력이 된다.
        std::cout << Queue.front() << std::endl;
        Queue.pop();
    }
    return 0;
}

 

이렇게 출력을 하게되면

0 ~ 9가 출력이 된다.

CircleQueue

CircleQueue.h (인라인으로 생성)



#pragma once

#include <assert.h>

template <typename T, int SIZE = 200>
class CCircleQueue
{
public:
    CCircleQueue()
    {
        m_Size = 0;
        m_Head = 0;
        m_Tail = 0;
        m_Capacity = SIZE + 1;
    }
    ~CCircleQueue()
    {
    }

private:
    T   m_Queue[SIZE + 1];  // 헤드와 테일이 같은 공간에 머물 +1을 만들어준다.
    int m_Size;  // 추가될 노드
    int m_Head;  // 노드를 지울때 사용하는 변수이자 가장 처음 추가된 곳의 이전 인덱스
    int m_Tail;  // 노드를 생성할 때 사용하는 변수이자 마지막으로 추가된 곳의 인덱스
    int m_Capacity;  // 배열의 총 크기

public:
    void push(const T& data)
    {
        // 나머지 연산자를 이용해서 테일의 인덱스 값을 구해준다.
         int Tail = (m_Tail + 1) % m_Capacity;
         
         if (Tail == m_Head)
             return;
         // Tail의 인덱스에  data값을 넣어준다.
         m_Queue[Tail] = data;
         // m_Tail을 갱신해준다.
         m_Tail = Tail;
         
         ++m_Size;
    }

    T& front()
    {
        if (empty())
            assert(false);
        // 나머지 연산자를 이용해 Head인덱스 값을 구해준다.
        int Head = (m_Head + 1) % m_Capacity;

        return m_Queue[Head];
    }

    void pop()
    {
        if (empty())
            assert(false);

        m_Head = (m_Head + 1) % m_Capacity;

        --m_Size;
    }

    bool empty() const
    {
        return m_Size == 0;
    }

    int Size() const
    {
        return m_Size;
    }

    void clear()
    {
        m_Head = 0;
        m_Tail = 0;
    }
};


 CircleQueue.cpp


#include <iostream>
#include "CircleQueue.h"

int main()
{
    CCircleQueue<int, 200> CQueue;

    for (int i = 0; i < 10; ++i)
    {
        CQueue.push(i);
    }

    for (int i = 0; i < 5; ++i)
    {
        std::cout << CQueue.front() << std::endl;
        CQueue.pop();
    }

    

    std::cout << "======================" << std::endl;

    for (int i = 0; i < 20; ++i)
    {
        CQueue.push(i);
    }

    while (!CQueue.empty())
    {
        std::cout << CQueue.front() << std::endl;
        CQueue.pop();
    }

    return 0;
}

위의 코드를 출력하게 되면

0 1 2 3 4 || 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 가 출력이 됩니다.