[ C언어 ] 자료구조_스택(배열)

스택은 추상 자료구조중 하나로 값이 들어가면 스택에 쌓이고 나올때는 마지막으로 들어간 순서대로 값이 나오는 구조입니다.

스택은 간단하게도 2가지의 기본 연산이 있습니다. 삽입연산 push 와 삭제연산 pop 가 기본입니다.

부가적으로 최상위 값을 읽는 연산도 있지만 기본 연산에는 제외합니다.

 

먼저 기능을 정의하는 해더코드입니다.

 

Stack.h

# define STACK_MAX 5

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

void init(StackType* stack);
int is_empty(StackType* stack);
int is_full(StackType* stack);
void push(StackType* stack, int value);
element pop(StackType* stack);
element peek(StackType* stack);

위 코드에는 6개의 함수를 정의하고 있습니다.

1. init 함수는 스택을 초기화 하는 함수로 처음 생성하거나 초기화 할 때 사용할 수 있습니다.

2. is_empty 함수는 스택이 공백상태인지 확인하는 함수로 삭제연산을 수행할 때 사용됩니다.

3. is_full 함수는 스택이 포화상태인지 확인하는 함수로 삽입연산을 할 때 사용됩니다.

4. push 함수는 스택에 값을 넣을 때 사용하는 함수입니다.

5. pop 함수는 스택에서 값을 꺼내는 동시에 삭제하는 함수입니다.

6. peek 함수는 스택에서 값을 읽을 때 사용하는 함수입니다.(pop함수와 비슷하지만 값을 꺼낼 때 삭제를 하지 않습니다.)

위에는 구조체로 스택의 타입을 element 라는 이름으로 사용하는데 이는 int 타입을 새로운 이름으로 정의한것입니다.

element(int) 타입으로 data 라는 5칸 배열을 생성하고 스택의 위치를 저장할 변수 top 를 선언하였습니다.

 

Stack.c

#include "Stack.h"
#include <stdio.h>

void init(StackType* stack) {
	stack->top = -1;
}
int is_empty(StackType* stack) {
	return stack->top == -1;
}
int is_full(StackType* stack) {
	return stack->top == STACK_MAX - 1;
}
void push(StackType* stack, int value) {
	if (is_full(stack)) {
		printf("스택 포화\n");
		return;
	}
	stack->data[++stack->top] = value;
}
element pop(StackType* stack) {
	if (is_empty(stack)) {
		printf("스택 공백\n");
		exit(0);
	}

	return stack->data[stack->top--];
}
element peek(StackType* stack) {
	if (is_empty(stack)) {
		printf("스택 공백");
		exit(0);
	}

	return stack->data[stack->top];
}

 

위 코드는 실제 함수를 구현한 코드입니다.

 

main.c

#include <stdio.h>
#include "Stack.h"

int main() {
	StackType stack;

	init(&stack);

	push(&stack, 1);
	push(&stack, 2);
	push(&stack, 3);
	printf("스택 값: %d\n", pop(&stack));
	push(&stack, 4);
	printf("스택 값: %d\n", pop(&stack));
	push(&stack, 5);
	push(&stack, 6);
	push(&stack, 7);
	push(&stack, 8);
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));

	return 0;
}

 

 

위 코드를 실행시켜보면 이렇게 정상적으로 동작을 하지만 문제는 정적배열을 사용했기 때문에 고정된 크기 한에서만 스택에 값을 넣을 수 밖에 없습니다.

 

이렇한 문제를 해결하기 위해 동적배열을 사용해서 구현해 보겠습니다.

 

Stack.h

typedef int element;
typedef struct {
	element* data;
	int stackSize;
	int top;
}StackType;

void init(StackType* stack);
int is_empty(StackType* stack);
int is_full(StackType* stack);
void push(StackType* stack, int value);
element pop(StackType* stack);
element peek(StackType* stack);
void delete(StackType* stack);

기존 코드에서 element 를 배열대신 포인터로 변경하고 할당받은 메모리를 해제하기 위한 delete 함수를 새로 만들었습니다.

 

그리고 Stack.c 파일에서는 변경된 부분만 확인하겠습니다.

void init(StackType* stack) {
	stack->top = -1;
	stack->stackSize = 1;
	stack->data = (element*)malloc(sizeof(stack->data) * stack->stackSize);
}
int is_full(StackType* stack) {
	return stack->top == stack->stackSize - 1;
}
void push(StackType* stack, int value) {
	if (is_full(stack)) {
		stack->stackSize *= 2;
		element* temp = realloc(stack->data, sizeof(element) * stack->stackSize);
		if (temp == NULL) {
			exit(1);
		}
		stack->data = temp;		

		if (stack->data == NULL) exit(1);
	}
	stack->data[++stack->top] = value;
}
void delete(StackType* stack) {
	free(stack->data);
}

init 함수에서는 1개의 데이터를 담을 수 있는 동적메모리를 할당받습니다.

그리고 push 함수에서 스택이 포화 상태라면 realloc 함수를 사용하여 메모리를 2배로 확장하게 됩니다.

 

main.c

#include <stdio.h>
#include "Stack.h"

int main() {
	StackType stack;
	
	init(&stack);

	push(&stack, 1);
	push(&stack, 2);
	push(&stack, 3);
	printf("스택 값: %d\n", pop(&stack));
	push(&stack, 4);
	printf("스택 값: %d\n", pop(&stack));
	push(&stack, 5);
	push(&stack, 6);
	push(&stack, 7);
	push(&stack, 8);
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));
	printf("스택 값: %d\n", pop(&stack));

	printf("스택 값: %d\n", pop(&stack));

	delete(&stack);
	return 0;
}

 

위 코드를 실행해 보면 스택이 포화되지 않고 문제없이 계속 값을 쌓을 수 있습니다.

 

이상으로 배열을 사용해서C언어로 스택을 구현해 보았습니다.