스택
스택은 일상생활에서 많이 사용되는 자료구조이다. 예를 들면 뒤로 가기 기능이 있다.
뒤로 가기를 누르면 현재 탭에서 이전에 사용하던 탭으로 되돌아가게 된다.
이때 스택이 사용된다.
스택은 "쌓다"라는 의미이다.
1번부터 차례대로 상자를 쌓게 되면 위와 같은 사진처럼 된다. 이것이 바로 스택이다.
3개의 상자가 있을 때 맨 아래부터 상자를 꺼낼 수 없다.
무조건 3번, 즉 위에 있는 상자부터 꺼내야 한다. 이것이 스택의 기본 구조인 LIFO 이다.
LIFO는 (Last In First Out)이고, 마지막에 넣은 것을 첫 번째로 꺼낸다는 말이다.
위의 상자에서 3번은 스택 상단(stack top),
1번은 스택 하단(stack bottom)이라 하고,
스택에 저장되는 것을 요소(element)라고 한다.
스택에 요소가 없으면 공백 스택(empty stack)이라고 한다.
코드 설명(스택을 전역변수로)
한번 스택을 C언어로 구현해보자.
#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef int 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)
{
push(1);
push(2);
push(3);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
return 0;
}우리가 필요한 것은 간단하다.
1. 스택
2. 스택이 비었는가?
3. 스택이 다 찼는가?
4. 스택에 값을 넣기(push)
5. 스택에서 값을 꺼내기(pop)
#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;1. 먼저 define문을 사용하면 stack의 최대 사이즈를 정해준다. 스택의 사이즈는 100이다.
2. typedef를 사용하여 int 타입을 element라고 부르도록 새롭게 정의해준다.
3. 스택을 정의해준다.
4. top을 -1로 선언한다. 이 이유는 컴퓨터는 0부터 시작하는데 현재 스택은 비어 있기 때문에 -1인 것이다.
int is_empty()
{
return (top == -1);
}is_empty는 스택이 비었는가?를 확인하는 함수이다.
만약 top이 -1(비어있다)이면 true(1)를 반환하고, 아니면 false(0)를 반환한다.
int is_full()
{
return (top == (MAX_STACK_SIZE - 1));
}is_full은 스택이 다 찼는가?를 확인하는 함수이다.
만약 top(스택 상단)이 99면 true(1)를 반환하고, 아니면 false(0)를 반환하다.
스택 사이즈는 100이기 때문에 top은 0~99까지 가능하다. 그래서 MAX_STACK_SIZE -1과 top이 같은 지 확인하는 것이다.
void push(element item)
{
if (is_full())
{
fprintf(stderr, "스택 포화 에러\n");
return;
}
else stack[++top] = item;
}push 함수는 파라미터로 item을 받는다. 만약 push(1)을 하면 1을 스택에 넣는다는 의미이다.
데이터를 스택에 저장하기 전에 스택이 다 찼는지 확인해야 한다.
그래서 is_full()을 하여 스택이 다 찼는지 확인하고, 스택이 다 안 찼으면 stack 상단을 1 증가 시킨뒤 해당 배열에 item을 집어 넣는다.
element pop()
{
if (is_empty())
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top--];
}pop 함수는 데이터를 꺼내는 함수이다. 따라서 파라미터가 필요 없다. 왜냐하면 값만 꺼내면 되기 때문이다.
데이터를 꺼내기 전에 스택이 비었는지 확인해야 한다.
따라서 is_empty를 하여 스택이 비었는지 확인하고, 스택이 안 비었으면 stack의 상단을 return 하고 스택 상단을 -1해준다.
*주의!! stack[--top]은 stack[top--]과 다르다.
예를 들어 top이 5면
전자는 stack[4]이고, 후자는 stack[5]이다.
element peek()
{
if (is_empty())
{
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top];
}peek 함수는 스택의 상단 값을 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;
}이렇게 하면
1을 스택에 넣고,
2를 스택에 넣고
3을 스택에 넣는다.
그다음 3을 꺼내고,
2를 꺼내고,
1을 꺼낸다.
3
2
1실행결과는 위와 같다.
마무리
다음 편은 스택의 요소를 구조체로 구현하는 방법에 대해 다룰 것이다.
궁금한 점은 댓글로 ㄱㄱ