[자료구조] 스택(Stack)

스택의 특징

• LIFO ( Last-In First-Out ) : 후입선출로 가장 늦게(최근에) 들어온 데이터가 가장 먼저 나감
• 프링글스 통을 스택이라고 생각하자

스택 ADT

• is_empty(s) : 스택이 비어있는지 검사
• is_full(s) : 스택이 가득 찼는지 검사
• push(s, e) : 스택의 맨 위에 요소 e를 추가
• pop(s) : 스택 맨 위의 요소 삭제

 

스택 생성

#define MAX_SIZE 10
typedef int element; // 추후 int형 스택을 다른 자료형으로 바꿀때 이부분만 수정하면 편리함
typedef struct {
	element stack[MAX_SIZE];
	int top;
}StackType;

 

init 함수

void init(StackType* s)
{
	s->top = -1;
}

top은 현재 스택의 맨위(최근)의 자료를 가리키는 변수이다.

top이 -1이라면 스택이 비어있는 상태이다.

0이라면 0번째 자료를 가리킴

 

is_empty 함수

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

스택의 top이 -1이라면 0번째 자료를 가리키는것도 아니고 없는거니깐 비어있는 상태이다.

 

is_full 함수

bool is_full(StackType* s)
{
	return s->top == MAX_SIZE - 1;
}

 

push 함수

void push(StackType* s, element item)
{
	if (is_full(s)) { // 꽉 찼다면 삽입이 불가능하다
		printf("STACK IS FULL\n");
		return;
	}
	s->stack[++(s->top)] = item; // 요소를 삽입전 ++연산을 통해 한칸 위의 자리를 가리키게 한다.
}

 

pop 함수

element pop(StackType* s)
{
	if (is_empty(s))
	{
		printf("STACK IS EMPTY\n");
		return -1; // 비어있다면 -1을 반환해주자
	}
	return s->stack[(s->top)--]; // top이 가리키는 원소를 반환한 후 -- 연산을 통해 내려가자
}

 

main 함수

int main(void)
{
	StackType s; // 스택 생성
	init(&s);
	pop(&s); // 비어있는데 pop을 했으므로 비어있다는 메세지가 나올 것이다.
	for (int i = 0; i < 11; i++) // 10까지는 잘 push 했지만 11을 넣을려니 꽉차서 메세지가 나올것
		push(&s, i+1);
	for (int i = 0; i < 11; i++) // 10부터 1까지는 잘 pop했지만 비어있는 스택을 pop할려니 에러나올것
		printf("%d\n",pop(&s)); // i가 10일때 pop시 요소가 없어서 에러 메세지와 -1을 출력할 것

}

 

전체 코드

#include <stdio.h>
#define MAX_SIZE 10
typedef int element;
typedef struct {
	element stack[MAX_SIZE];
	int top;
}StackType;
void init(StackType* s)
{
	s->top = -1;
}
bool is_empty(StackType* s)
{
	return s->top == -1;
}
bool is_full(StackType* s)
{
	return s->top == MAX_SIZE - 1;
}
void push(StackType* s, element item)
{
	if (is_full(s)) {
		printf("STACK IS FULL\n");
		return;
	}
	s->stack[++(s->top)] = item;
}
element pop(StackType* s)
{
	if (is_empty(s))
	{
		printf("STACK IS EMPTY\n");
		return -1;
	}
	return s->stack[(s->top)--];
}
int main(void)
{
	StackType s;
	init(&s);
	pop(&s);
	for (int i = 0; i < 11; i++)
		push(&s, i+1);
	for (int i = 0; i < 11; i++)
		printf("%d\n",pop(&s));

}

 

출력 결과