배열 기반 스택(Stack) [C언어]

1. 스택이란?

스택의 구조

스택이란 한쪽 방향에서 데이터를 넣거나 뺄 수 있는 선형구조로 Last In First Out으로 LIFO라고도 불린다. 배열 기반으로 스택을 구현할 때 스택의 개수와 데이터 저장 위치를 알려주는 역할을 해주는 top과 적당한 크기의 배열로 이루어져 있다. 코드로 표현하면 아래와 같다.

#define MAX 100		//스택 최대 크기

typedef int element;

//스택 구조
typedef struct Stack{
	element stack[MAX];
	int top;
}Stack;

2. 스택의 기능

• INIT
• FULL
• EMPTY
• PUSH
• POP
• PEEK
• PRINT

이렇게 위 목록들의 기능들을 구현하였다.

//스택 초기화
void init(Stack * p) {
	p->top = 0;
}

INIT은 스택을 사용하기 전에 초기화 작업을 해주는 기능이다. top의 위치를 0으로만 설정하면 끝이다.

//스택이 가득차있는지 확인
int full(Stack* p) {
	if (p->top == MAX - 1) return 1;
	else return 0;
}

FULL은 해당 기능은 현재 스택의 용량이 최대치인지 확인해주는 기능이다. 데이터를 넣는 작업을 진행할 때 메모리 공간이 부족하다면 넣을 수 없기 때문에 사전에 이러한 검사를 진행하는 것이다. 변수 top을 이용하여 현재 스택의 크기를 확인하고 최대치의 크기를 확인한 후 두 개의 값을 비교한 뒤 현재 스택의 용량이 최대치라면 1을 반환하며 아니라면 0을 반환해준다.

//스택이 비었는지 확인
int empty(Stack * p) {
	if (p->top == 0) return 1;
	else return 0;
}

그리고 EMPTY은 스택에 현재 저장된 것이 아무것도 없는지 확인해주는 기능이다. FULL과 마찬가지로 변수 top을 이용하여 확인하는데 비어있다면 1로 반환하고 아니라면 0으로 반환한다.

//스택에 데이터 추가
void push(Stack * p, element x) {
	if (full(p)) {
		printf("현재 스택 용량이 가득찼습니다.\n");
	}
	else {
		p->top += 1;
		p->stack[p->top] = x;
	}
}

PUSH는 데이터를 밀어 넣는다는 의미로 스택에 데이터를 추가로 저장할 때 사용되는 기능이다. 먼저 스택에 데이터를 추가할 수 있는 상황인지 FULL 기능을 통해 확인 후 top 변수를 1 증가시키고 해당 위치에 데이터를 저장한다.

//스택 제일 위에 있는 데이터 반환 후 제거
element pop(Stack * p) {
	element e;
	if (empty(p)) {
		printf("현재 스택이 비어있습니다.\n");
		exit(1);
	}
	else {
		e = p->stack[p->top];
		p->top -= 1;
		return e;
	}
}

POP은 데이터를 꺼내서 제거한다는 의미로 스택에 데이터를 제거할 때 사용되는 기능이다. top이 가리키고 있는 위치의 데이터를 반환하고 top을 1 감소시켜준다. 그런데 스택이 비어있다면 반환을 할 수 없기에 exit(1) 함수를 통해서 프로그램을 종료합니다. exit(1)은 성공적으로 프로그램을 종료하지 못했다는 의미입니다.

//스택 제일 위의 데이터 반환
element peek(Stack * p)
{
	if (empty(p)) {
		printf("현재 스택이 비어있습니다.\n");
		exit(1);
	}
	else {
		return p->stack[p->top];
	}
}

PEEK는 POP과 같이 데이터를 확인하는 작업인데 데이터를 제거하지는 않는다. 단지 top이 가리키고 있는 위치의 데이터를 반한만 해준다.

//현재 스택 현황 출력
void print(Stack* p) {
	int i;
	printf("현재 스택 현황: ");
	for (i = 1; i <= p->top; i++)
		printf("%d ", p->stack[i]);
	printf("\n");
}

PRINT는 스택에 저장된 값들을 출력해주는 함수이다.

int main(void)
{
	Stack s;
	init(&s);

	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	print(&s);

	printf("peek 결과: %d\n", peek(&s));
	printf("pop 결과: %d\n", pop(&s));
	printf("pop 결과: %d\n", pop(&s));

	print(&s);
	return 0;
}

기능들을 구현을 전부 마쳤다면 main 함수에서 이를 위와 같이 다루면 성공적으로 배열 기반의 스택을 구현하게 될 것이다. 전체 코드는 아래와 같다.

#include <stdio.h>
#define MAX 100		//스택 최대 크기

typedef int element;

//스택 구조
typedef struct Stack{
	element stack[MAX];
	int top;
}Stack;

//스택 초기화
void init(Stack * p) {
	p->top = 0;
}

//스택이 비었는지 확인
int empty(Stack * p) {
	if (p->top == 0) return 1;
	else return 0;
}

//스택이 가득차있는지 확인
int full(Stack* p) {
	if (p->top == MAX - 1) return 1;
	else return 0;
}

//스택에 데이터 추가
void push(Stack * p, element x) {
	if (full(p)) {
		printf("현재 스택 용량이 가득찼습니다.\n");
	}
	else {
		p->top += 1;
		p->stack[p->top] = x;
	}
}

//스택 제일 위에 있는 데이터 반환 후 제거
element pop(Stack * p) {
	element e;
	if (empty(p)) {
		printf("현재 스택이 비어있습니다.\n");
		exit(1);
	}
	else {
		e = p->stack[p->top];
		p->top -= 1;
		return e;
	}
}

//스택 제일 위의 데이터 반환
element peek(Stack * p)
{
	if (empty(p)) {
		printf("현재 스택이 비어있습니다.\n");
		exit(1);
	}
	else {
		return p->stack[p->top];
	}
}

//현재 스택 현황 출력
void print(Stack* p) {
	int i;
	printf("현재 스택 현황: ");
	for (i = 1; i <= p->top; i++)
		printf("%d ", p->stack[i]);
	printf("\n");
}

int main(void)
{
	Stack s;
	init(&s);

	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	print(&s);

	printf("peek 결과: %d\n", peek(&s));
	printf("pop 결과: %d\n", pop(&s));
	printf("pop 결과: %d\n", pop(&s));

	print(&s);
	return 0;
}

3. 느낀 점

최근 풀타임 알바를 하고 있어서 그동안 공부를 못하고 있어서 복습을 해야겠다는 생각에 스택에 대해서 다시 공부를 하며 글로 정리를 해보았는데 역시나 복습을 안 했던 만큼 쉽게 만들지 못했다. 자료구조에 대해서 하나씩 정리하는 시간을 가져봐야겠다.