[C/C++][자료구조] 스택(Stack)에 대하여

[C/C++][자료구조] 스택(Stack)에 대하여

• 스택(Stack)은 LIFO(Last In First Out)의 원리로 동작하는 선형적인 자료구조이다.
• 같은 타입의 자료 집합을 관리한다는 면에서는 배열이나 연결 리스트와 동일하지만 자료를 관리하는 방식이 미리 정해져 있다는 점이 다르다.
• 스택은 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여 있다가 들어간 반대 순서로 나온다.

스택을 구현하기 위해서는 다음과 같은 세 개의 변수가 필요하다.

int *Stack;
int Size;
int Top;

• Stack : 데이터를 저장할 저장소인데 필요한만큼 동적으로 할당하기 위해 포인터로 선언했다. 스택에 저장할 데이터와 같은 타입의 포인터를 선언하면 이 포인터가 곧 스택이 된다. 또한 위에서는 정수형 포인터로 선언했으므로 이 스택은 정수를 저장하는 스택이 되는데 임의의 모든 타입에 대한 스택 생성이 가능하다. 문자, 실수는 물론이고 구조체같은 큰 타입도 가능하다.
• Size : 스택의 할당 크기이다.
• Top : 스택의 현재 위치를 가리키는 값이며 스택의 어디까지 차 있는지를 기억한다.

필요한 변수에 대해 알아보았으니 다음으로 필요한 함수에 대해 알아보도록 하겠다.

void InitStack(int aSize)
{
     Size=aSize;
     Stack=(int *)malloc(Size*sizeof(int));
     Top=-1;
}

• InitStack 함수는 스택을 초기화하는데 인수로 전달된 aSize를 Size에 대입해 놓고 Size 크기만큼 메모리를 할당하여 Stack 포인터에 대입한다.따라서 Stack은 Size 크기의 정수형 배열이 되며 Size개의 정수를 저장할 수 있게된다. 정적 배열로도 스택을 구현할 수 있지만 이렇게 하면 크기가 고정되어 버린다. 동적으로 할당하면 스택을 쓰는 쪽에서 필요한 크기를 결정할 수 있는데 필요한 최대 크기로 잡는 것이 좋다. 최소 스택에는 아무런 데이터가 들어있지 않으므로 Top은 비어 있다는 뜻의 -1로 초기화한다. 배열이 0부터 시작하기 때문에 0은 자료가 없는 상태가 아니라 하나 들어 있는 상태이므로 비어 있는 것과는 다르다.

void FreeStack()
{
     free(Stack);
}

• FreeStack 함수는 스택을 파괴하는데 동적으로 할당된 메모리만 해제하면 된다.

BOOL Push(int data)
{
     if (Top < Size-1) {
          Top++;
          Stack[Top]=data;
          return TRUE;
     } else {
          return FALSE;
     }
}

• Push 함수는 스택에 데이터를 저장하는 동작을 한다. 데이터가 들어 있는 Top을 1 증가시킨 후 이 자리에 인수로 전달된 data를 집어 넣는다. 푸시 동작은 Top 증가, 그리고 Top에 data 대입 두 동작만으로 구현된다. 나머지 코드는 스택 오버플로우 일 경우에 대한 에러 처리 코드인데 스택의 크기가 무한하지 않기 때문에 가득차 있는지를 점검하는 것이다.

• *스택 오버플로우(stack overflow) : 스택이 가득 차서 더 데이터를 삽입할 수 없는 상태

int Pop()
{
     if (Top >= 0) {
          return Stack[Top--];
     } else {
          return -1;
     }
}

• Pop 함수는 스택에 저장한 값을 빼 내는 동작을 한다. Top 위치의 값을 읽고 Top을 하나 감소시킨다. 스택 언더플로우가 발생할 경우 -1값을 리턴하도록 코드를 작성하였는데, 이때 -1이라는 값은 스택에서 꺼낸 값이 -1인 경우와 구분되지 않는 모호함이 있으므로 에러값을 좀 더 특이한 값(예:-10992)으로 선택하거나 아니면 별도의 출력용 인수를 사용하는 것이 바람직하다.

• *스택 언더플로우(stack underflow) : 스택이 텅 비어서 더이상 꺼낼 데이터가 없는 상태

필요한 변수와 함수에 대해 다 알아보았으니 위 코드들을 하나의 소스로 합쳐서 보도록 하겠다.

#include ...

int *Stack;
int Size;
int Top;
 
void InitStack(int aSize)
{
     Size=aSize;
     Stack=(int *)malloc(Size*sizeof(int));
     Top=-1;
}
 
void FreeStack()
{
     free(Stack);
}
 
BOOL Push(int data)
{
     if (Top < Size-1) {
          Top++;
          Stack[Top]=data;
          return TRUE;
     } else {
          return FALSE;
     }
}
 
int Pop()
{
     if (Top >= 0) {
          return Stack[Top--];
     } else {
          return -1;
     }
}
 
void main()
{
     InitStack(256);
     Push(7);
     Push(0);
     Push(6);
     Push(2);
     Push(9);
     printf("%d\n",Pop());
     printf("%d\n",Pop());
     printf("%d\n",Pop());
     printf("%d\n",Pop());
     printf("%d\n",Pop());
     FreeStack();
}

• 추가적으로 구현된 스택 코드를 테스트 하기 위한 main 함수를 구현해주었다. 최조 Top이 -1일 때는 스택이 비어 있으며 데이터가 삽입되면 Top이 위로 이동하면서 Top 위치에 데이터가 저장된다. Push 되는 순서대로 스택에 데이터가 차곡차곡 쌓이며 Pop할 때는 Push된 역순으로 꺼내진다. 위 소스에서는 7, 0, 6, 2, 9를 차례대로 넣었다가 역순으로 빼서 출력되는 것을 확인해 볼 수 있을 것이다.

• *스택은 같은 타입의 집합이므로 연결리스트로도 만들 수 있다. 연결리스트를 쓸 경우 스택 크기가 처음부터 고정되지 않고 필요한만큼 얼마든지 늘릴 수 있다는 장점이 있다. 그러나 Push, Pop 할 때마다 메모리를 할당하고 해제해야 하므로 속도가 느리고 메모리도 더 많이 소모된다는 단점이 있다. 임시적인 정보를 저장하는 용도상 스택은 굳이 길이가 가변적일 필요가 없으므로 연결리스트로 스택을 구현하는 것은 합리적이지 않으며 배열이 더 잘 어울린다.

* 참고 - 소프트웨어 공학연구소 C/C++ 강좌 (http://soen.kr/)