[C] 스택 : 스택 구현하기

첫번째 공부할 자료구조는 스택!

스택이란?
LIFO(Last in First out)으로, 데이터의 삽입과 삭제가 후입선출인 자료구조를 말한다.
가장 나중에 들어온 데이터가 가장 먼저 나가게 되고
가장 먼저 들어온 데이터는 가장 나중에 나가게 된다...


추상 자료형으로 정의하면
.
.
creat(size) >> 최대 크기가 size만큼인 비어있는 스택 생성
is_full(s) >> 스택의 원소수 == size면 true (stack is full), 아니면 false
is_empty(s) >> 스택의 원소수 == 0 이면 true, 아니면 false
push(s, item) >> is_full(s) 이 false면 맨 위 (top)에 item 추가
pop(s) >> is_empty(s) 가 flase면 맨 위(top)의 원소를 제거하고 반환

이 정도의 함수가 쓰인다...


스택의 요소를 구조체로 사용해서 정수 데이터를 사용하는 스택을 구현해보자
.
.

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

#define STACK_SIZE 100 //stack의 최대 사이즈, 100으로 지정

typedef int element; // 스택에 저장되는 요소의 type은 element로 정의한다. 지금은 int형
typedef struct {
	element data[STACK_SIZE];
	int top; // -1이면 스택이 비어있음
}StackType;

//스택 초기화 함수 init_stack
void init_stack(StackType *s) { //포인터 s가 data배열의 시작주소를 가리킨다.
	s->top = -1; //-1로 바꿔서 스택이 비어있음을 명시
}

//스택이 공백인지 확인하는 함수 is_empty
int is_empty(StackType* s) {
	return (s->top == -1); //top이 -1이면 비어있음, 1리턴.
}

//스택이 포화상태인지 확인하는 함수 is_full
int is_full(StackType* s) {
	return(s->top == (STACK_SIZE - 1)); //top은 비어있으면 -1, 차있으면 0부터 시작하므로 전체size-1과 같으면 포화상태, 1리턴.
}

//데이터 삽입함수 push, 삽입하는 데이터 == item
void push(StackType* s, element item) {
	if (is_full(s)) { //오버플로우 검사
		fprintf(stderr, "stack is full\n");
		return; //오버플로우면 함수 끝내기
	}
	s->top++; //스택에 빈 공간이 있다면, push 가능. 현재 가리키고 있는 맨 위 데이터의 인덱스인 top을 하나 위로 올리고 ...
	s->data[s->top] = item; // 데이터를 삽입해라.
}

//데이터 삭제함수 pop, 삭제한 데이터를 반환하기
element pop(StackType* s) {
	if (is_empty(s)) { //스택이 비어있어서 삭제할 수 있나 없나 확인
		fprintf(stderr, "stack is empty\n");
		exit(1);
	}
	int item;
	item = s->data[s->top]; //제일 위에 있는 데이터 꺼내기
	s->top--; //top 을 한 칸 아래 가리키게 하기
	return item; //삭제한 item 반환하기
}

//메인코드
int main() {
	StackType s; //지역 구조체변수, 메모리할당을 함, 포인터가 아님
	init_stack(&s); //스택값 초기화
	push(&s, 1); // 스택 s에 데이터 1을 넣기
	push(&s, 2); //		... 데이터 2를 넣기
	push(&s, 3);
	push(&s, 4);
	push(&s, 5);
	push(&s, 6); // stack에 1, 2, 3, 4, 5, 6이 차례대로 들어감, top은 6을 가리킴
	printf("꺼낸 값 = %d\n", pop(&s));// 6이 출력되고 나중에 top은 5를 가리킴
}

꺼낸 값 = 6
.
.
이라는 결과를 볼 수 있다.

스택을 동적 메모리로 할당받아서 생성할 수 있다.
동적 메모리는, 실행 시간에 메모리를 할당받는 것이다.
동적 메모리를 이용하면 오버플로우 발생 시 스택의 크기를 동적으로 늘릴 수 있다.
.
.

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

typedef int element;
typedef struct {
	element* data; //data는 포인터로 정의된다
	int capacity; //현재 크기
	int top;
}StackType;

void init_stack(StackType* s) {
	s->top = -1;
	s->capacity = 1;
	//동적할당
	s->data = (element*)malloc(s->capacity * sizeof(element)); //처음에 4바이트를 할당한다
}

int is_full(StackType* s) {
	return s->top == s->capacity - 1;
}

void push(StackType* s, element item) {
	//overflow발생시 메모리를 동적으로 할당한다
	if (is_full(s)) {
		s->capacity = s->capacity * 2; //크기를 2배 늘린다.
		s->data = (element*)realloc(s->data, s->capacity * sizeof(element));
		//realloc은 현재 내용은 유지하면서 주어진 크기로 동적 메모리를 다시 할당함.
		//capacity가 *2 되었으므로 할당되는 크기도 2배 늘어나게된다
	}
	s->data[++s->top] = item;
}

int is_empty(StackType* s) {
	return s->top == -1;
}

element pop(StackType* s) {
	//underflow check
	if (is_empty(s)) {
		printf("스택이 비어있음\n");
		exit(1);
	}
	else
		return s->data[s->top--];
}

//메인함수
int main() {

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

	printf("%d\n", s.data[s.top]); //맨 위에 있는 데이터 '6' print
	printf("pop vlaue = %d\n", pop(&s)); // '6'을 pop하고 print
	printf("pop vlaue = %d\n", pop(&s)); // '5'를 pop하고 print

	free(s.data); // 동적 메모리 반환
}

6
pop value = 6
pop value = 5
.
.
가 출력된다.
첫번째 코드의 #define STACK_SIZE 10 처럼

맨 처음 스택의 크기를 지정해주지 않아도

실행 도중에 동적으로 할당된다 굿!



다음 포스팅은 스택의 응용에 대해 하려고 한다.
파이팅!


[참고자료]
c언어로 쉽게 풀어쓴 자료구조 (천인국 공용해 하상호 지음, 생능출판)