본문 바로가기
[Public] 컴퓨터공학/자료구조

[자료구조] 3. 스택

by 차출발 2009. 10. 19.
반응형

스택 (Stack)

 

2009. 10. 19()

 

 

1.      스택의 개요

1)      스택의 정의

-       여러 개의 데이터 항목들이 일정한 순서로 나열된 자료 구조에서 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제하는 자료구조의 한 형태를 말한다. 보통 나중에 들어온 데이터가 가장 먼저 나가는 형태라 하여 LIFO(Last In First Out)이라는 말을 많이 쓰기도 한다. 이는 데이터가 입력되는 위치와 출력되는 위치가 같은 특징을 지니고 있다.

 

2)     스택의 예

-       스택은 우리 일상에서 많이 볼 수 있다. 음료수 자판기에 음료수를 집어 넣으면 먼저 넣으면 앞에 있는 음료수를 먼저 빼 먹는 이런 원리와 비슷하다고 할 수 있다. 이 뿐만 아니라 골목길 안에 주차를 할 때 나중에 먼저 주차를 한 차가 나가야지만 나갈 수 있는 이러한 구조도 포함한다.

 

3)     스택의 원리

-       스택의 일반적인 구조는 아래 그림과 같다.

 

-       그림을 이해하기 위하여 색으로 구분해서 보장

 

첫 번째로 파랑색에 보이는 POP PUSH 가 있다. PUSH는 데이터를 집어 넣는 것이고 POP은 데이터를 빼는 것 즉 삭제라 생각하자.

 

그림에서 주황색을 보자 먼저 base는 공간의 시작이라 생각하면 된다.  limit는 공간의 끝이라 생각하라. 한 마디로 스택영역의 전체크기라 생각하면 된다. 그럼 여기서 나타내는 Top은 무엇인가? Top은 보통 Stack Pointer 라고도 많이 불린다. 한 마디로 현재 위치를 나타내는 포인터라 생각하면 쉽겠다. 당연히 PUSH가 들어오면 TOP은 하나 증가하겠고 POP이 들어오면 TOP은 하나 감소 할 것이다.

 

이렇게 PUSH 시키다 보면 Limit 영역을 벗어나게 될 경우는 어떻게 되는가 이럴 때는 빨간색 보이는 OVERFLOW 현상이 일어난다. 또 이와 반대로 계속 POP하다가는 BASE 영역을 벗어나게 되는 경우에는 UNDERFLOW 현상이 일어나는 것이다.

 

이 원리만 알고 있다면 당신은 이제 스택을 만들수 있다. 저번 시간에 배운 배열과 연결리스트로 한번 구현해보자. 이건 직접 구현해보는 걸 추천한다.

 

2.     배열로 스택 구현

-       스택을 구현 해보았다. 비효율적인 면도 있으니 양해 바란다.

#include <stdio.h>

#include <memory.h>

#include <stdlib.h>

#define TRUE true

#define FALSE false

 

bool OverFlow(int StackPoint, int nLimit);

bool UnderFlow(int StackPoint);

 

void PushData(int nData, int& StackPoint, int* Stack);

void PopData(int& StackPoint, int* Stack);

 

void PrintStack(int StackPoint, int* Stack);

void InputData(int& nSize);

void OutPut(int nData);

 

void main()

{

       int nSize;

       printf("스택크기를설정하세용: ");

       InputData(nSize);

       int* Stack = new int [nSize];

       memset(Stack, 0, sizeof(int)*nSize);

       printf("\n 크기%d 인스택이만들어졌습니다.\n", nSize);

 

       int StackPoint = 0;

       bool bContinue = TRUE;

       while(bContinue)

       {

             OutPut(0);

             int nNum;

             InputData(nNum);

 

             switch(nNum)

             {

                    case 1:

                           system("cls");

                           if(OverFlow(StackPoint, nSize))

                           {

                                 OutPut(5);

                           }

                           else

                           {

                                 OutPut(1);

                                 int nData;

                                 scanf("%d", &nData);

                                 PushData(nData, StackPoint, Stack);

                           }

                    break;

 

                    case 2:

                           system("cls");

                           if(UnderFlow(StackPoint))

                           {

                                 OutPut(6);

                           }

                           else

                           {

                                 OutPut(2);

                                 PopData(StackPoint, Stack);

                           }

 

                    break;

 

                    case 3:

                           system("cls");

                           OutPut(3);

                           PrintStack(StackPoint, Stack);

                    break;

 

                    case 4:

                    default:

                           system("cls");

                           OutPut(4);

                           bContinue = FALSE;

                    break;

                   

             }

            

       }

       delete [] Stack;

       Stack = NULL;

}

void InputData(int& nSize)

{

 

       scanf("%d", &nSize);

 

}

void OutPut(int nData)

{

       switch (nData)

       {

             case 0:

                    printf("1. Push \n2. Pop\n3. OutPut\n4. End\n");

             break;

 

             case 1:

                    printf(" Push Data 입력:");

             break;

 

             case 2:

                    printf(" Pop 실행\n");

             break;

 

             case 3:

                    printf("출력\n");

             break;

 

             case 4:

                    printf("종료\n");

             break;

 

             case 5:

                    printf("OverFlow!\n");

             break;

 

             case 6:

                    printf("UnderFlow!\n");

             break;

 

             default:

                    break;

       }     

}

 

void PrintStack(int StackPoint, int* Stack)

{

       printf("↓↓↓↓\n");

       if(StackPoint)

       {

             for(int i=StackPoint-1 ; i>=0 ; i--)

             {

                    printf("[%5d]\n", Stack[i]);

             }

       }

       else

       {

             printf("비어있습니다.\n");

       }

}

 

bool OverFlow(int StackPoint, int nLimit)

{

       if(StackPoint == nLimit)

       {

             return TRUE;

       }

       return FALSE;

}

bool UnderFlow(int StackPoint)

{

       if(StackPoint == 0)

       {

             return TRUE;

       }

       return FALSE;

}

 

void PushData(int nData, int& StackPoint, int* Stack)

{

       Stack[StackPoint] = nData;

       StackPoint++;

}

void PopData(int& StackPoint, int* Stack)

{

       printf("%d 제거\n", Stack[StackPoint]);

       Stack[StackPoint] = 0;

       StackPoint--;

}

 

 

-       사진을 모두 넣기 귀찮아 전체 구조만 넣겟다.