[C 자료구조] 스택(Stack)

스택(Stack)이란?

 

스택(Stack)은 자료구조의 한 종류입니다. 두 개의 포인터로 많은 양의 데이터를 관리하는 이론? 구조? 이죠.

 

자료구조 중에서 '선형구조'에 해당하는 자료구조인데요, 어려울 거 없이 프링글스를 생각하시면 됩니다.

 

 

 

자료 구조 설명하는데 왜 뜬금없는 과자가 나오나 싶지만, 이 구조가 스택 구조와 매우 유사합니다.

우리가 프링글스를 먹을 때 맨 아래 프링글스나 중간 프링글스를 먼저 먹을 수 있나요? 아니죠. 위에서 순서대로 먹어야만 합니다. 그리고 아래에는 구멍이 안 뚫려있고, 위에만 구멍이 뚫려 있는 구조입니다.

 

위에는 뚫려있고, 위에서 부터 가져올 수 있으며 반대로는 뺄수없는 형태를 스택구조 라고 합니다.

이를 FILO(First In Last Out), 혹은 LIFO(Last In First Out) 구조라고 합니다.

 

 

스택에는 가장 기본적으로 2개의 연산이 있습니다. 바로 PUSH 와 POP 입니다.

push

PUSH 연산은 스택에 데이터를 넣는 연산입니다. push 연산시 가장 위에 원소를 추가하고, 반대로 POP 연산시에는 가장 위의 원소를 반환합니다.

pop

 

이런 스택을 구현하고자 할 때 배열이나 연결리스트로 구현할 수 있습니다. 오늘 포스팅에서는 우선 배열로 구현하는 방법에 대해서만 다룹니다.

 

우리가 데이터를 꺼내고 싶다면, 어느 데이터가 제일 위에 있는지 그 위치는 어디인지를 알아야 맨 위의 원소를 꺼낼 수 있습니다. 따라서 포인터 혹은 배열의 인덱스로 맨 위의 원소의 위치를 함께 저장해야만 stack 자료구조를 사용할 수 있습니다. 단계별로 스택의 배열 구현을 보겠습니다.

 

1. 스택의 선언 및 초기화

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100  // 스택의 사이즈

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType* s)
{
	s->top = -1;
}

먼저 스택 타입을 구조체로 정의해줍니다. 구조체 안에는 데이터를 저장할 배열(stack) 과 스택의 최상단 데이터의 위치를 가르키는 배열의 인덱스를 저장할 int형 top 변수를 저장해줍니다. 그리고 init_stack 함수는 스택을 초기화 시켜주는 함수로, 하는 역할은 top 변수를 -1로 초기화 시켜주는 역할을 합니다. 이는 스택의 인덱스를 0부터 시작하기 위해서입니다.

 

배열은 인덱스가 0부터 시작되기 때문에 배열에 원소가 1개 있다면 그 원소의 인덱스는 0입니다. 현재는 아직 아무것도 넣지 않았으니 -1 이라고 초기화를 하고 push를 통해 데이터를 한 개 추가할 때마다 top 도 1씩 증가시키는 방식입니다.

 

그리고 아직 포인터 개념이 익숙치 않으시다면 init 함수에서 왜 StackType* 를 인수로 받는지 헷갈릴 수 있는데요, 쉽게 이해해보자면 저 구조체 자체가 하나의 스택이라고 생각하시면 됩니다. 왜냐하면 저 구조체 안에는 배열과 배열의 top 을 가르켜주는 변수가 선언되어 있기 때문이죠. 따라서 우리가 StackType s; 이런 식으로 StackType 자료형의 s라는 변수를 만들게 되면 s라는 스택이 구조체 자료형으로 생성되는 것이고 그 스택의 원소인 스택 배열이나 인덱스에 접근하기 위해서는 포인터를 사용하게 됩니다.

 

2. isfull(), inempty() 함수 구현

스택이 꽉 차 있는 경우에 원소를 집어넣으려고 push 연산을 하게 되면 스택이 넘치게 됩니다. 위 예시처럼 100 칸짜리 배열을 만들어놨는데 101 번째에 데이터를 집어넣으려고 하면 당연히 오류가 발생하겠죠? 혹은 동적으로 배열을 할당한다고 하더라도, 스택의 범위가 지정 범위를 넘어서는 스택 오버플로우가 발생할 수 있습니다.

 

반대로 스택이 비어있는 상태에서 pop 연산을 하게 되면 아무것도 없는 상태에서 원소를 반환해야 하기 때문에 오류가 발생하거나 쌩뚱맞은 다른 값을 반환하게 됩니다. 따라서 스택의 구현에서 가득 차 있는지, 비어있는지를 체크하는 함수가 필요합니다.

 

isfull() 함수는 스택이 가득 차 있는지, isempty() 함수는 스택이 비어있는지를 검사하는 함수입니다.

// 공백 상태 검출 함수
int isempty(StackType* s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int isfull(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}

이 때 주의할 점으로는 top 이 MAX_STACK_SIZE 가 아닌 1을 뺀 값과 같을 때 스택이 가득 차있다는 겁니다. 만약 10으로 배열을 선언했다고 생각하면 그 배열의 인덱스는 0 ~ 9가 됩니다. 9가 마지막 원소의 인덱스이므로 top 이 (스택 크기 - 1) 과 같을 때 스택이 가득 차 있다는 것을 알 수 있습니다.

 

3. push() 함수

// 삽입 함수
void push(StackType* s, element item)
{
	if (isfull(s))
	{
		fprintf(stderr, "스택 포화 오류\n");
		return;
	}
	else s->data[++(s->top)] = item;
}

위에서 구현한 isfull() 함수를 통해 스택이 꽉차 있는지 검사하고 그렇지 않다면 스택의 가장 윗 부분에 추가합니다.

마지막의 s->data[++(s->top)] = item; 코드는 아래처럼 2줄로 나눠서 생각할 수 있습니다.

top++;
s->data[top] = item;

맨 처음의 인덱스를 생각하면 이해하기 쉽습니다. 초기화 할 때 인덱스가 -1인데, 배열의 -1 인덱스에 데이터를 넣을 수 없으니 먼저 top 을 증가시킨 이후, 데이터를 스택에 삽입합니다.

 

4. pop() 함수

// 삭제 함수
element pop(StackType* s)
{
	if (isempty(s))
	{
		fprintf(stderr, "스택 공백 오류\n");
		return;
	}
	else return s->data[(s->top)--];
}

마찬가지로 isempty() 함수를 통해 스택이 비어있는지 검사하고 비어있지 않다면 데이터를 꺼내서 반환합니다.

마지막 줄의 s->data[(s->top)--]; 데이터를 먼저 꺼낸 이후에 top 변수를 감소시킵니다. 먼저 top을 감소시키고 데이터를 꺼낸다면 맨 위의 데이터가 아닌 2번째 데이터를 꺼내는 것이기 때문에 꼭 데이터를 먼저 가져온 이후 top을 감소시켜야 합니다.

 

5. peek() 함수 / printStack() 함수

// 피크 함수
element peek(StackType* s)
{
	if (isempty(s))
	{
		fprintf(stderr, "스택 공백 오류\n");
		return;
	}
	else return s->data[(s->top)];
}

void printStack(StackType* s) {
	int i;
	for (i = 0; i <= s->top; i++)
	{
		printf("[%d]", s->data[i]);
	}
	printf("\n");
}

push 와 pop 에서 이미 스택의 구현은 끝났으나 몇 가지 추가적인 기능을 함수로 구현하면 위와 같습니다. peek() 는 스택의 맨 위의 원소를 확인하는 함수입니다. 꺼내지는 않고 맨 위의 데이터만 확인하는 것이므로 pop 과 거의 유사한데 마지막에 top을 감소시키지 않는 점만 다릅니다.

 

다음으로 스택의 내용을 모두 print 하는 함수인데 배열의 인덱스를 의미하는 top 변수를 통해 0 ~ top 까지 print 하여 스택의 데이터를 모두 출력해줍니다.

 

이를 종합한 전체 코드를 마지막으로 보겠습니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100  // 스택의 사이즈

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType* s)
{
	s->top = -1;
}

// 공백 상태 검출 함수
int isempty(StackType* s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int isfull(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(StackType* s, element item)
{
	if (isfull(s))
	{
		fprintf(stderr, "스택 포화 오류\n");
		return;
	}
	else s->data[++(s->top)] = item;
}

// 삭제 함수
element pop(StackType* s)
{
	if (isempty(s))
	{
		fprintf(stderr, "스택 공백 오류\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}

// 피크 함수
element peek(StackType* s)
{
	if (isempty(s))
	{
		fprintf(stderr, "스택 공백 오류\n");
		exit(1);
	}
	else return s->data[(s->top)];
}

void printStack(StackType* s) {
	int i;
	for (i = 0; i <= s->top; i++)
	{
		printf("[%d]", s->data[i]);
	}
	printf("\n");
}

int main()
{
	StackType s;

	init_stack(&s);
	push(&s, 5);
	push(&s, 4);
	push(&s, 3);
	push(&s, 2);
	push(&s, 1);
	printStack(&s);

	pop(&s);
	pop(&s);
	printStack(&s);

	push(&s, 9);
	push(&s, 10);
	printStack(&s);

	return 0;
}

실행 결과

 

 

조금 더 자세하게 스택에 대해 알고 싶으시면 아래 포스팅을 참고하시면 됩니다. 감사합니다.

 

스택(Stack) - C, C++ 구현 코드

스택 프레임(Stack Frame)

참고 문헌 : C언어로 쉽게 풀어쓴 자료구조 - 생능출판