자료구조 - 스택(배열 기반)

 스택이란 가장 먼저 들어간 것이 나중에 나오는 특성을 가진 자료구조를 말한다.

 

 

다음 그림처럼 가장 나중에 들어간 Data 가 나올 때는 가장 먼저 나온다.

이러한 구조를 Last In First Out(LIFO) 또는 First In Last Out(FILO) 라 한다.

 

 

스택의 ADT는 다음과 같은 연산들을 정의한다.

  - 자료를 삽입하는 push

  - 가장 마지막에 삽입된 자료를 꺼내는 pop

  - 가장 마지막에 삽입된 자료를 조회하는 peek

  - 스택이 비어 있는지 확인하는 empty

  - 스택 내 자료의 수를 확인하는 size

 

---

 

여기서 스택은 배열  또는  연결리스트로 구현할 수 있다.

 

먼저 배열로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다.

스택 헤더파일

 

스택 실행파일

 

 

코드 부분설명▼

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

스택 초기화 부분

(여기서 topIndex 는 마지막에 저장된 데이터의 위치를 가리키며 -1 은 빈 상태를 의미한다.)

 

 

 

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

스택이 비어있는지 확인하는 함수

( topIndex 가 -1인 경우는 빈 상태이며로 true 를 반환하고 아니면 false 를 반환한다.)

 

 

 

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

스택의 push 연산을 담당하는 함수

( topIndex 에 +=1 을 함으로써 -1 0 1 2 3 ... 순으로 데이터가 삽입되면서 인덱스가 증가한다.

또한 stackArr 배열에 데이터를 삽입한다.)

 

 

 

Data SPop(Stack* pstack)
{
	int rIdx;

	if (SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex;
	pstack->topIndex -= 1;

	return pstack->stackArr[rIdx];
}

스택의 pop 연산을 담당하는 함수

( 만약 스택이 비어있다면 "Stack Memory Error" 메시지를 출력하고 빠져나온다.

스택이 비어있지 않다면 rIdx 변수에 스택에서 마지막으로 저장된 데이터의 인덱스 값을 저장한 뒤 스택의 인덱스를 -1 한다.

그리고 마지막으로 저장된 데이터를 반환한다.)

 

 

 

 

Data SPeek(Stack* pstack)
{
	if (SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex];
}

스택의 peek 연산을 담당하는 함수

(peek 함수는 pop 함수와 다르게 스택의 데이터를 삭제하지 않고 그냥 반환하여 조회한다.)

 

 

 

 

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;
}

메인 문

(스택을 생성하고 초기화한 후 1 2 3 4 5 순으로 데이터를 삽입한 뒤 pop 연산을 통해 5 4 3 2 1 순으로 출력되도록 한다.)

 

 

실행 결과