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

스택(Stack)이란?

데이터를 쌓아 올리는 자료형 -> 후입 선출 형태(LIFO:Last-In First-Out, 가장 최근에 들어온 데이터가 가장 먼저 나감)

 

스택의 구조

• 스택에서의 입출력은 맨 위에서만 발생한다. (한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조)
• 스택 상단(top) : 스택에서 입출력이 이루어지는 부분
• 요소(element) : 스택에 저장되는 것

출처 : C언어로 쉽게 풀어쓴 자료구조

스택의 연산

• push 연산 : 스택에 데이터 추가
• pop 연산 : 스택의 데이터 삭제
• peek 연산 : 삭제하지 않고 보기만 하는 연산

출처 : C언어로 쉽게 풀어쓴 자료구조

스택의 구현

is_empty() : 스택이 비어있는지를 검사하는 함수 -> top이 -1이면 공백

is_full() : 스택이 포화 상태인지를 검사하는 함수 -> top이 MAX_STACK_SIZE-1이면 포화 상태

push() : 먼저 스택이 포화상태인지를 검사한 후(is_full()), top을 먼저 증가시키고 stack[top]에 데이터를 추가

pop() : 먼저 스택이 공백상태인지를 검사한 후, stack[top]의 데이터를 반환 후 top 감소

 

1. 1차원 배열을 이용한 구현

출처 : C언어로 쉽게 풀어쓴 자료구조

• top 변수 : 가장 최근에 입력되었던 자료를 가리키는 변수 -> 공백 상태이면 -1
• 가장 먼저 들어온 요소는 stack[0]에, 마지막으로 들어온 요소는 stack[top]에 존재함

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

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element  stack[MAX_STACK_SIZE]; // 1차원 배열
int  top = -1;	//top의 초기상태

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item; //증가 후 삽입
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--]; //반환 후 감소
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

2. 구조체를 이용한 구현

#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 is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}

int main(void)
{
	StackType s;

	init_stack(&s); //call-by-reference : stack의 원본 변경 가능
	push(&s, 1);
	push(&s, 2);
	push(&s, 3);
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
}

3. 스택의 요소를 구조체로 하기

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100


typedef struct {
	int student_no;
	char name[MAX_STRING];
	char address[MAX_STRING];
} element;
element  stack[MAX_STACK_SIZE];
int  top = -1;

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
// 피크함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void)
{
	element ie = { 	20190001,
			"Hong",
			"Soeul"	};
	element oe;

	push(ie);
	oe = pop();

	printf("학번: %d\n", oe.student_no);
	printf("이름: %s\n", oe.name);
	printf("주소: %s\n", oe.address);
	return 0;
}