[자료구조] 스택(Stack)

 

 

이번에 설명하고자 하는 자료는 스택(Stack)이다.

 

스택은 한 문장으로 표현하면

"먼저 들어간 것이 나중에 나온다."

 

위 문장대로 스택은 후입선출(後入先出)또는 LIFO(Last-In, First-Out)의 자료구조라고 불린다.

 

이러한 스택의 구조는 우리 주변에서 많이 살펴볼 수 있다.

 

이러한 프링글스라던가..

 

이런 장난감 같은 경우도 스택구조이다.

 

 

먼저 배열기반으로 구현해보았다.

 

Candy.h

#pragma once   enum eCandy {     eRed = 1,     eGreen,     eBlack, };   class Candy { public:       Candy();     ~Candy();       virtual void TasteCandy() = 0;     virtual void SeeCandy() = 0;   private: };   class CRedCandy    : public Candy { public:       CRedCandy();     ~CRedCandy();       void TasteCandy();     void SeeCandy();   private: };   class CGreenCandy    : public Candy { public:     CGreenCandy();     ~CGreenCandy();       void TasteCandy();     void SeeCandy();   private: };     class CBlackCandy    : public Candy { public:           CBlackCandy();         ~CBlackCandy();           void TasteCandy();         void SeeCandy(); private: };

Candy.cpp

#include <iostream>   #include "Candy.h"     Candy::Candy() {     std::cout<<"Candy 생성자"<<std::endl; }   Candy::~Candy() {     std::cout<<"Candy 소멸자"<<std::endl; }   CRedCandy::CRedCandy() {     std::cout<<"빨간사탕 생성자"<<std::endl; }   CRedCandy::~CRedCandy() {     std::cout<<"빨간사탕 소멸자"<<std::endl; }   void CRedCandy::TasteCandy() {     std::cout<<"음... 딸기맛이네.."<<std::endl; }     CGreenCandy::CGreenCandy() {     std::cout<<"초록사탕 생성자"<<std::endl; }   CGreenCandy::~CGreenCandy() {     std::cout<<"초록사탕 소멸자"<<std::endl; }   void CGreenCandy::TasteCandy() {     std::cout<<"멜론맛이군.."<<std::endl; }     CBlackCandy::CBlackCandy() {     std::cout<<"검은사탕 생성자"<<std::endl; }   CBlackCandy::~CBlackCandy() {     std::cout<<"검은사탕 소멸자"<<std::endl; }   void CBlackCandy::TasteCandy() {     std::cout<<"아.. 계피맛이야!!!!"<<std::endl; }     void CRedCandy::SeeCandy() {     std::cout<<"빨간 사탕이네"<<std::endl; }   void CGreenCandy::SeeCandy() {     std::cout<<"초록색 사탕이네"<<std::endl; }   void CBlackCandy::SeeCandy() {     std::cout<<"검은 사탕이네"<<std::endl; }

stack.h

#pragma once   #include "Candy.h"   static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10;   enum eMenu {     ePush = 1,     ePop,     ePeek,     eExit, };   class CStack { public:       CStack();     ~CStack();       bool IsEmpty();    //스택이 빈경우 true ,아니면 false     bool IsFull();    //스택이 가득 찬경우 true, 아니면 false          int Start();       void Push();        //추가     void Pop();            //삭제     void Print();             void AllDelete();   private:       int nTopIndex;       static Candy *nArray[ARRAY_MAX];   };

stack.cpp

#include <iostream>   #include "stack.h"   //enum eCandy; Candy * CStack::nArray[ARRAY_MAX];   CStack::CStack() {     std::cout<<"Stack 생성자"<<std::endl;       this->nTopIndex = -1; }   int CStack::Start() {     int nChoiceMenu = 0;       while (true)     {         std::cout<<"1. 사탕넣기, 2. 사탕먹기. 3.사탕보기, 4.사탕버리기"<<std::endl;         std::cin>>nChoiceMenu;           switch (nChoiceMenu)         {         case ePush:             this->Push();             break;           case ePop:             this->Pop();             break;           case ePeek:             this->Print();             break;           case eExit:             this->AllDelete();             return eExit;           default:             std::cout<<"잘못 선택하셧습니다."<<std::endl;             break;         }     } }     CStack::~CStack() {     std::cout<<"Stack 소멸자"<<std::endl; }   bool CStack::IsEmpty() {     if( ARRAY_MIN > nTopIndex )     {         std::cout<<"스택이 비었습니다."<<std::endl;         return true;     }     else     {         std::cout<<"스택 안에 데이터가 있습니다."<<std::endl;         return false;     } }   bool CStack::IsFull() {     if( ARRAY_MAX-1 <= nTopIndex )     {         std::cout<<"스택이 가득찻습니다."<<std::endl;         return true;     }     else     {         std::cout<<"스택이 빈 공간이 있습니다."<<std::endl;         return false;     } }   void CStack::Push() {     if( this->IsFull() )     {         std::cout<<"배열이 가득 찼습니다."<<std::endl;     }     else     {         int nChoiceCandy = 0;           std::cout<<"색깔을 선택해 주세요"<<std::endl;         std::cout<<"1.빨강 , 2. 초록, 3.검정"<<std::endl;         std::cin>>nChoiceCandy;           switch (nChoiceCandy)         {         case eRed:             nTopIndex++;             this->nArray[nTopIndex] = new CRedCandy;             break;         case eGreen:             nTopIndex++;             this->nArray[nTopIndex] = new CGreenCandy;             break;         case eBlack:             nTopIndex++;             this->nArray[nTopIndex] = new CBlackCandy;             break;         default:             std::cout<<"잘못 선택하셧습니다."<<std::endl;             break;         }     }   }   void CStack::Pop() {     if( this->IsEmpty() )     {//스텍이 비었을 경우         std::cout<<"스텍이 비어있습니다."<<std::endl;     }     else     {         this->nArray[nTopIndex]->TasteCandy();         delete this->nArray[nTopIndex];         nTopIndex--;     } }   void CStack::Print() {     int nTempIndex = this->nTopIndex;       if(this->IsEmpty())     {         std::cout<<"비어있습니다."<<std::endl;     }     else     {         while( ARRAY_MIN <= nTempIndex )         {             this->nArray[nTempIndex]->SeeCandy();             nTempIndex--;         }     } }   void CStack::AllDelete() {     while (!this->IsEmpty())     {         this->Pop();     } }

main.cpp

#include <iostream>   #include "stack.h"   int main() {     CStack Stack;       Stack.Start();       return 0; }

 

출력결과

 

데이터를 꺼낼 때 먼저 들어간 데이터가 나중에 호출되는 것을 볼 수 있다.

 

여기서는 배열로 구현하였지만

스택도 연결리스트로 구현 가능하다..

단 저장의 순서의 역순으로 조회 및 삭제가 가능한 것 일뿐 다른 것은 없다.

 

저장하는 순서와 조회 및 삭제가 이와 같은 구조를 가진것을 스텍이라고 부를 뿐

만들 때 특별히 후입선출(後入先出)또는 LIFO(Last-In, First-Out) 이외에

정해진 방법(배열을 쓴다던가 리스트를 쓴다던가 하는 정해진 방법)은 없다.