Chapter 06. 스택의 배열 기반 구현Chapter 06. 스택의 배열 기반 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

배열 기반 스택의 구조는 정말 단순합니다. 만약 배열이 10개 선언되었다면, 배열의 0번지가 스택의 바닥이 됩니다. 탄창의 밑바닥과 같은 곳입니다. 그리고 데이터를 저장할 때마다 0번지, 1번지, 2번지, ... 순으로 저장 위치를 증가시킵니다. 그리고 가장 마지막에 데이터가 저장된 위치를 변수 top에 저장합니다. 따라서 만약 배열 기반 스택의 0번지부터 7번지까지 데이터가 저장되었다면 top은 7이 되는 것입니다.

---

앞서 스택의 ADT도 정의했고 구조도 이해했으니 이를 기반으로 스택 헤더 파일을 정의해 보겠습니다.

//ABStack.h 헤더 파일로 저장
#ifndef AB_STACK_H
#define AB_STACK_H

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

typedef int Data;

typedef struct ArrayStack
{
	Data StackArr[STACK_LEN];
	int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);

#endif

---

이제 위 헤더 파일을 바탕으로 각각의 함수들을 구현해 보겠습니다. 스택의 구현은 정말 간단합니다.

 

먼저 스택을 초기화하는 StackInit 함수의 구현입니다.

void StackInit(Stack* pstack)
{
	pstack->topIndex = -1;
}

topIndex는 가장 마지막에 저장된 데이터의 위치(번지수)를 나타냅니다. 배열은 0번지부터 시작하기 때문에 이를 0으로 초기화하면 0번지에 데이터가 하나 저장되어 있는 것이 됩니다. 따라서 -1로 초기화합니다.

 

다음은 스택이 비어있는지 확인하는 함수인 SIsEmpty의 구현입니다.

int SIsEmpty(Stack* pstack)
{
	if (pstack->topIndex >= 0) return FALSE;
	return TRUE;
}

스택이 비어 있는지는 topIndex로 판단합니다. 참고로 스택에는 저장된 데이터의 수를 저장하는 변수가 존재하지 않습니다.

 

다음은 스택에 데이터를 추가하는 SPush 함수의 구현입니다.

void SPush(Stack* pstack, Data data)
{
	pstack->topIndex++;
	pstack->StackArr[pstack->topIndex] = data;
}

topindex를 하나 올리고, 해당 위치에 데이터를 저장합니다.

 

다음은 스택에서 가장 마지막에 저장된 데이터를 삭제하고, 해당 값을 반환하는 SPop 함수의 구현입니다.

Data SPop(Stack* pstack)
{
	if (pstack->topIndex == -1)
	{
		printf("스택의 참조 범위를 벗어나는 접근입니다.");
		exit(1);
	}

	Data data = pstack->StackArr[pstack->topIndex--];
	return data;
}

삭제할 데이터가 있는지 먼저 확인하고, topIndex를 하나 낮춥니다. 그리고 해당 데이터를 반환합니다.

 

다음은 스택에서 가장 마지막에 저장된 데이터를 반환하는 SPeek 함수의 구현입니다.

Data SPeek(Stack* pstack)
{
	if (pstack->topIndex == -1)
	{
		printf("스택의 참조 범위를 벗어나는 접근입니다.");
		exit(1);
	}

	Data data = pstack->StackArr[pstack->topIndex];
	return data;
}

SPop 함수와 비교해서 topIndex를 하나 낮추지 않는다는 것이 유일한 차이점입니다.

 

이렇게 헤더 파일의 정의와 구현이 완료되었습니다. 이를 바탕으로 main 함수를 작성하여 그 실행결과를 보겠습니다.

//ABStack.h 헤더 파일로 저장
#ifndef AB_STACK_H
#define AB_STACK_H

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

typedef int Data;

typedef struct ArrayStack
{
	Data StackArr[STACK_LEN];
	int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);

#endif

//ABStack.c 소스 파일로 저장 
#include "ABStack.h"
#include <stdio.h>
#include <stdlib.h>

void StackInit(Stack* pstack)
{
	pstack->topIndex = -1;
}

int SIsEmpty(Stack* pstack)
{
	if (pstack->topIndex >= 0) return FALSE;
	return TRUE;
}

void SPush(Stack* pstack, Data data)
{
	pstack->topIndex++;
	pstack->StackArr[pstack->topIndex] = data;
}

Data SPop(Stack* pstack)
{
	if (pstack->topIndex == -1)
	{
		printf("스택의 참조 범위를 벗어나는 접근입니다.");
		exit(1);
	}

	Data data = pstack->StackArr[pstack->topIndex--];
	return data;
}

Data SPeek(Stack* pstack)
{
	if (pstack->topIndex == -1)
	{
		printf("스택의 참조 범위를 벗어나는 접근입니다.");
		exit(1);
	}

	Data data = pstack->StackArr[pstack->topIndex];
	return data;
}

//main.c 소스 파일로 저장
#include "ABStack.h"
#include <stdio.h>

int main(void)
{
	//Stack의 성생 및 초기화
	Stack stack;
	StackInit(&stack);

	//데이터 넣기
	SPush(&stack, 1);
	SPush(&stack, 2);
	SPush(&stack, 3);
	SPush(&stack, 4);
	SPush(&stack, 5);

	//데이터 꺼내기
	while (!SIsEmpty(&stack))
	{
		printf("%d ", SPop(&stack));
	}

	return 0;
}

/*
실행결과

5 4 3 2 1

*/

실행결과를 보면 데이터를 저장한 반대 순서로 출력되고 있음을 확인할 수 있습니다. 이것이 스택의 특징입니다.