[자료구조] Stack

1. 개념

LIFO ( Last In First Out )

가장 늦게 들어간 원소가 먼저 나옴
ex) undo, redo, 함수 호출스택

---

2. 예시코드

#pragma once

#include <stdio.h>
using namespace std;

struct SBL_Node
{
    int Data;

    SBL_Node* NextNode;
};

class stackByLinkedList
{
public:
    stackByLinkedList();
    ~stackByLinkedList();

    void Push(SBL_Node* node);
    SBL_Node* Pop();

    SBL_Node* Top() { return top; }
    int size();
    bool IsEmpty() { return head == NULL; }

    static SBL_Node* CreateNode(int data);
    static void DestoryNode(SBL_Node** node);

private:
    SBL_Node* head = NULL;
    SBL_Node* top = NULL;
};

#include "StackByLinkedList.h"

stackByLinkedList::stackByLinkedList()
{
}

stackByLinkedList::~stackByLinkedList()
{
    while(IsEmpty() == false)
    {
        SBL_Node* node = Pop();
        DestoryNode(&node);
    }

    head = NULL;
    top = NULL;
}

void stackByLinkedList::Push(SBL_Node* node)
{
    if(head != NULL)
    {
        SBL_Node* oldTop = head;
        while (oldTop->NextNode != NULL)
            oldTop = oldTop->NextNode;

        oldTop->NextNode = node;
    }
    else
    {
        head = node;
    }

    top = node;
}

SBL_Node* stackByLinkedList::Pop()
{
    SBL_Node* temp = top;

    if(head == top)
    {
        head = NULL;
        top = NULL;
    }
    else
    {
        SBL_Node* currentTop = head;
        while (currentTop != NULL && currentTop->NextNode != top)
            currentTop = currentTop->NextNode;

        top = currentTop;
        currentTop->NextNode = NULL;
    }

    return temp;
}

int stackByLinkedList::size()
{
    int count = 0;
    SBL_Node* node = head;
    while (node != NULL)
    {
        node = node->NextNode;
        count++;
    }

    return count;
}

SBL_Node* stackByLinkedList::CreateNode(int data)
{
    SBL_Node* node = new SBL_Node();
    node->Data = data;
    node->NextNode = NULL;

    return node;
}

void stackByLinkedList::DestoryNode(SBL_Node** node)
{
    delete* node;
    *node = NULL;
}