스택(Stack)

• 스택 기본 구조

-스택은 입출력이 한방향으로 이루어 진다(자료를 입력하는 쪽과 출력하는 쪽이 같다).

-늦게 들어온 자료가 더 빨리 나가는 구조(LIFO : Last in First out).

-일반적으로 스텍에서 입력을 Push, 출력을 Pop이라고 한다.

현실에서 LIFO의 예

• 스택의 삽입(Push)

-스택의 삽입은 가장 앞쪽에서 이루어 진다.

-위 그림에서 Head노드는 데이터는 갖지 않고, 첫번째 노드의 위치를 저장하는 노드다

(Head노드에도 데이터를 저장한다면, 삽입 노드가 Head노드가 되게하면 된다).

Head노드의 다음노드(Next) = 삽입노드

삽입 노드의 다음노드(Next) = 노드#01(첫번째 데이터 노드)

삽입 완료

void Stack::Push(int data)

{

        //새 노드 생성 및 데이터 입력

        NODE *newNode = new NODE();

        newNode->Data = data;

       

        //새 노드의 Next로 현재 제일 앞에 있는 노드를 지정

        newNode->Next = m_top->Next;

 

        //현재 노드를 제일 앞 노드로 지정

        m_top->Next = newNode;

}

• 스택의 출력(Pop)

출력(Pop) 요청시 첫번째 노드를 출력

Head노드의 다음노드(Next)를 2번째 노드(출력 노드의 Next)로 지정

( = 2번째 노드를 첫번째 노드로 만듬)

데이터 전달 & 노드를 삭제를 완료하면

출력 종료

int Stack::Pop(void)

{

        //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

        if (m_top->Next == m_bottom)

               return NULL;

 

        //첫번째 노드 데이터 수령

        NODE *deleteNode = m_top->Next;

        int result = deleteNode->Data;

 

        //2번째 노드를 첫번째 노드로

        m_top->Next = m_top->Next->Next;

 

        //첫번째 노드 삭제

        delete deleteNode;

        deleteNode = NULL;

       

        //결과 반환

        return result;

}

• 전체 코드

#pragma once

class Stack

{

private:

        typedef struct _Node

        {

               int Data;

               struct _Node* Next;

        } NODE;

 

private:

        NODE *m_top, *m_bottom;

 

public:

        Stack();

        ~Stack();

 

        void Push(int data);

        int Pop(void);

        void Print(void);

};

#include "stdafx.h"

#include "Stack.h"

 

 

Stack::Stack()

{

        m_top = new NODE();

        m_bottom = new NODE();

 

        m_top->Next = m_bottom;

        m_bottom->Next = m_bottom;

}

 

 

Stack::~Stack()

{

}

 

void Stack::Push(int data)

{

        //새 노드 생성 및 데이터 입력

        NODE *newNode = new NODE();

        newNode->Data = data;

       

        //새 노드의 Next로 현재 제일 앞에 있는 노드를 지정

        newNode->Next = m_top->Next;

 

        //현재 노드를 제일 앞 노드로 지정

        m_top->Next = newNode;

}

 

int Stack::Pop(void)

{

        //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

        if (m_top->Next == m_bottom)

               return NULL;

 

        //첫번째 노드 데이터 수령

        NODE *deleteNode = m_top->Next;

        int result = deleteNode->Data;

 

        //2번째 노드를 첫번째 노드로

        m_top->Next = m_top->Next->Next;

 

        //첫번째 노드 삭제

        delete deleteNode;

        deleteNode = NULL;

       

        //결과 반환

        return result;

}

 

void Stack::Print(void)

{

        NODE* indexNode = m_top->Next;

 

        printf("\nPrint : ");

        for (indexNode; indexNode != m_bottom; indexNode = indexNode->Next)

        {

               printf("%d ", indexNode->Data);

        }

        printf("\n\n");

}

• 템플릿으로 구현한 스택

#pragma once

#include "stdafx.h"

 

template<typename T>

class tStack

{

private:

        typedef struct _Node

        {

               T Data;

               struct _Node* Next;

 

               _Node()

               {

                       Data = NULL;

                       Next = NULL;

               }

 

               _Node(T data)

               {

                       Data = data;

                       Next = NULL;

               }

        } NODE;

 

private:

        NODE *m_top, *m_bottom;

 

public:

        tStack()

        {

               m_top = new NODE();

               m_bottom = new NODE();

 

               Init();

        }

 

        ~tStack()

        {

               Clear();

 

               delete m_top;

               delete m_bottom;

 

               m_top = NULL;

               m_bottom = NULL;

        }

 

        //스택 비우기

        void Clear(void)

        {

               //비어 있으면 동작 안함

               if (IsEmpty())

                       return;

 

               NODE* indexNode = m_top->Next;

               for (indexNode; indexNode != m_bottom;)

               {

                       NODE* deleteNode = indexNode;

                       indexNode = indexNode->Next;

 

                       delete deleteNode;

                       deleteNode = NULL;

               }

 

               Init();

        }

 

        //입력

        void Push(T data)

        {

               //새 노드 생성 및 데이터 입력

               NODE *newNode = new NODE(data);

 

               //새 노드의 Next로 현재 제일 앞에 있는 노드를 지정

               newNode->Next = m_top->Next;

 

               //현재 노드를 제일 앞 노드로 지정

               m_top->Next = newNode;

        }

 

        //출력

        T Pop(void)

        {

               //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

               if (IsEmpty())

                       return NULL;

 

               //첫번째 노드 데이터 수령

               NODE *deleteNode = m_top->Next;

               T result = deleteNode->Data;

 

               //2번째 노드를 첫번째 노드로

               m_top->Next = m_top->Next->Next;

 

               //첫번째 노드 삭제

               delete deleteNode;

               deleteNode = NULL;     

 

               //결과 반환

               return result;

        }

 

        //비었는지 확인

        bool IsEmpty(void)

        {

               //첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음

               if (m_top->Next == m_bottom)

                       return true;

               else

                       return false;

        }

 

private:

        //초기화

        void Init(void)

        {

               m_top->Next = m_bottom;

               m_bottom->Next = m_bottom;

        }

};