[자료구조/정리] 스택(Stack)

[ 스택(Stack) ]

선입후출의 자료구조.

먼저 들어간 데이터가 나중에 나오는 방식.

 

구현 방법 : 배열 기반, 리스트 기반(싱글 리스트 기반으로 활용)

 

[ 전체 코드 ]

Stack.h

#pragma once

#include <assert.h>

template <typename T>
class CStackNode
{
    template <typename T>
    friend class CStack;
private:
    CStackNode()
    {
        m_pNext = nullptr;
    }
    ~CStackNode()
    {
    }
private:
    T m_Data;
    CStackNode<T>* m_pNext;
};

// 리스트 기반 구현.
template <typename T>
class CStack
{
public:
    CStack()  // 생성자.
    {
        m_pNode = nullptr;
        m_iSize = 0;
    }
    ~CStack()  // 소멸자.
    {
        clear();
    }
private:
    typedef CStackNode<T>	Node;
    typedef CStackNode<T>* PNode;
private:
    PNode m_pNode;
    int m_iSize;
public:
    // 데이터를 넣음.
    void push(const T& data)
    {
        PNode pNode = new Node;  // 새로운 노드 생성.

        pNode->m_Data = data;  // 데이터를 넣음.

        if (m_pNode)  // 처음 추가하는 노드가 아닐 경우
            pNode->m_pNext = m_pNode;  // pNode의 다음 노드를 m_pNode로 설정.

        m_pNode = pNode;  // m_pNode를 pNode로 설정. 

        ++m_iSize;
    }

    T top() const
    {
        assert(m_iSize != 0);  // 비어있으면 경고창을 띄우고 종료시킴.

        return m_pNode->m_Data;
    }

    // 지움.
    void pop()
    {
        assert(m_iSize != 0);
    
        PNode pNode = m_pNode->m_pNext;  // m_pNode의 다음 노드의 정보를 저장할 노드 생성.

        delete m_pNode;  // 맨 뒤 노드 제거.

        m_pNode = pNode;  // m_pNode를 pNode로 설정.

        --m_iSize;
    }

    // 모두 지움.
    void clear()
    {
        PNode pNode = m_pNode;

        while (pNode)
        {
            PNode pNext = pNode->m_pNext;

            delete pNode;

            pNode = pNext;
        }

        m_pNode = nullptr;
        m_iSize = 0;
    }

    // 크기.
    int size() const
    {
        return m_iSize;
    }

    // 비어있는 지 확인.
    bool empty() const
    {
        return m_iSize == 0;
    }
};

// 배열 기반 구현.
template <typename T>
class CStackArray
{
public:
    CStackArray()
    {
        m_iCapacity = 4;
        m_iSize = 0;
        m_pArray = new T[m_iCapacity];
    }
    ~CStackArray()
    {
        delete[] m_pArray;
    }
private:
    T* m_pArray;
    int	m_iSize;
    int	m_iCapacity;
public:
    // 데이터를 넣음.
    void push(const T& data)
    {
        if (m_iSize == m_iCapacity)  // 꽉차있을 경우, 재할당.
        {
            m_iCapacity *= 2;  // 크기 늘림.

            T* pArray = new T[m_iCapacity];

            memcpy(pArray, m_pArray, sizeof(T) * m_iSize);  // 전에  있던 거 새로운 곳에 옮김.

            delete[] m_pArray;  // 전에 있던 거 지움.

            m_pArray = pArray;  // 새로운 걸로 바꿔줌.
        }

        m_pArray[m_iSize] = data;
        ++m_iSize;
    }

    T top() const
    {
        assert(m_iSize != 0);  // 비어있을 경우 경고창을 띄우고 종료 시킴.

        return m_pArray[m_iSize - 1];
    }

    // 지움.
    void pop()
    {
        assert(m_iSize != 0);  // 비어있을 경우 경고창을 띄우고 종료 시킴.

        --m_iSize;
    }

    // 모두 지움.
    void clear()
    {
        m_iSize = 0; 
    }

    // 크기.
    int size() const
    {
        return m_iSize;
    }

    // 비어있는 지 확인.
    bool empty() const
    {
        return m_iSize == 0;
    }
};

 

main.cpp

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

int main()
{
    std::cout << "================= Stack - 리스트 기반 =================" << std::endl;

    CStack<int> stack;

    for (int i = 0; i < 10; ++i)
    {
        stack.push(i);  // 0 1 2 3 ...  9
    }

    while (!stack.empty())
    {
        std::cout << stack.top() << " ";  // 제일 위에 있는 데이터 출력 >> 9 8 7 ... 0

        stack.pop();  // 지움.
    }
    std::cout << std::endl;

    std::cout << "================= Stack - 배열 기반 =================" << std::endl;
    CStackArray<int> stack1;

    for (int i = 0; i < 10; ++i)
    {
        stack1.push(i);  // 0 1 2 3 ... 9 
    }

    while (!stack1.empty())
    {
        std::cout << stack1.top() << " ";  // 제일 위에 있는 데이터 출력 >> 9 8 7 ... 0
    
        stack1.pop();  // 지움,
    }
    std::cout << std::endl;

    return 0;
}

[ 결과 ]

================= Stack - 리스트 기반 =================
9 8 7 6 5 4 3 2 1 0
================= Stack - 배열 기반 =================
9 8 7 6 5 4 3 2 1 0

 

[ 설명 ]