3. 데이터 구조 - ADT의 개념과 stack의 이해 및 구현

1. ADT란 ?

실제적인 구현으로 부터 분리되어 정의된 자료형이다.

즉 복잡한 소프트웨어 시스템을 관리하기 위해 각각의 주요한 부분을 분리해 추상적으로 관리하는 것이다.

 

2. stack의 개념

스택이란 더미, 낟가리라는 뜻으로, 어떠한 것들이 쌓여있는 상태를 의미한다.

만약 상자라고 예를 든다면, 쌓여있는 상자에서 상자를 빼야할때 밑에서 빼거나 중간에서 빼면 상자가 무너져 내릴것이다.

즉 상자를 뺄때는 맨 위(맨 마지막)에 놓은 상자부터 차례대로 빼야 무너지지 않는다. 

이러한 과정을 후입선출(LIFO)라고 한다. 그래서 stack은 중간이나 맨 처음(맨 아래)에 넣은 상자를 자신의 차례(맨 위)가 될 때까지 어떤 상자인지 확인 할 수 없다. 무조건 맨 위에 있는 상자만 확인 할 수 있는 것이다!

 

즉 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 때 매우 요긴하게 사용된다.

밑의 그림처럼 말이다..

스택의 예

3. stack의 ADT

그렇다면 stack의 ADT에 대해서 살펴보자.

일단 stack을 기본적인 배열을 통해서 구현한다고 가정했을 때, 

상자를 쌓아 올리는 곳이 비어 있는지 확인하는 과정 -> is_empty
상자를 쌓아 올리는 곳이 꽉 차있는지 확인하는 과정 -> is_full
상자를 쌓는 과정 -> push
상자를 빼는 과정 -> pop
맨 위의 상자가 무슨 상자인지를 확인하는 과정 -> peek

 

으로 나눌 수 있다.

 

 

4. stack의 구현

#include <stdio.h>
#define stack_size 100

int top = -1; //상자의 높이를 확인할 변수 (배열로 구현하기 때문에 맨 아래가 1이 아닌 0이다. 
		//그래서 초기화(아무것도 없는 상태)일때는 -1로 표시한다.)
int size[stack_size];

int is_empty() {
	return(top == -1);
}

int is_full() {
	return(top == stack_size - 1); //배열이 0부터 시작하기때문에 (끝 - 1)를 해줘야 
					//꽉 찼음을 나타낸다.
}

void push(int a) {
	if (is_full()) {
		printf("꽉찼습니다");
		return;
	} //만약 상자를 쌓아 올릴 곳이 꽉 찼다면 더이상 상자를 쌓지말고 중지한다.

	size[++top] = a; //top 즉 상자의 높이를 하나 올려주고 a라는 상자를 추가한다.
}

int pop() {
	if (is_empty()) {
		printf("비어있습니다");
		return 0;
	}//만약 상자를 쌓아 올릴 곳이 비어있다면 더이상 상자를 빼지말고 중지한다.

	int result = size[top--]; //top높이에 있는 상자를 빼고 top높이를 하나 줄인다.

	return result;
}

int peek() {
	if (is_empty()) {
		printf("비어있습니다");
		return 0;
	}

	int result = size[top]; //top높이의 있는 상자가 무엇인지 확인한다.(빼지는 않음))

	return result;
}

int main(void) {
	push(1);
	push(2);
	push(3);
	// 1 2 3 순서대로 상자를 넣었다.
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	// 3 2 1 순서대로 상자가 나온다.
	return 0;
}

 

여기서 주의해야 할 점은 top이라는 높이를 상자를 빼거나 넣을 때마다 수동으로 늘리거나 줄여줘야 한다는 점이다.

그림을 그리면서 따라가면 훨씬 더 쉽게 이해 할 수 있을 것이다.