스택(stack)
스택(stack)이란?
스택은 후입선출(Last In First Out)로 동작한다.
가장 마지막에 들어간 데이터가 가장 먼저 빠져나간다는 뜻이다.
스택이 실생활에 사용되는 예
제일 마지막에 작성한 코드부터 차례대로 되돌아가기 위해 우리는 Ctrl + z 키를 사용한다.
물건을 밑에서부터 차근차근 쌓아 올리고 계산할때는 맨 위, 즉, 제일 마지막에 올려서 위에 놓인 물건부터 계산대로 옮긴다.
컴퓨터는 사람처럼 계산을 할 수 없기 때문에 후위 표기법과 같이 계산한다.
쨌든 맨 처음 넣었던 데이터를 확인하려면 그 위에 쌓여있는 다른 데이터들을 꺼내야 확인할 수 있다.
스택의 구성
스택 구현
|
1
2
3
4
|
typedef struct Stack {
int arr[100];
int top;
}stack;
|
cs |
스택의 구조체 부분에는 100칸짜리 int형 배열과 맨 위에 있는 데이터를 저장할 수 있는 변수가 구성 되어있다.
|
1
2
3
4
|
void init(stack* s)
{
s->top = -1;
}
|
cs |
스택을 만들때마다 초기화 시켜주는 함수이다.
배열은 인덱스 0부터 시작하니, top 변수에 -1을 넣어 초기화시켜줘서 스택이 비어있음을 말한다.
|
1
2
3
4
5
6
|
int is_empty(stack* s)
{
if (s->top == -1)
return 1;
return 0;
}
|
cs |
스택이 비어있는지 확인하는 함수이다.
만약 top 변수에 -1이 들어가있으면 스택이 비었다는 뜻이므로 1('참')을 반환하고
비어있지 않으면 0('거짓')을 반환한다.
|
1
2
3
4
5
6
|
int is_full(stack* s)
{
if (s->top == 99)
return 1;
return 0;
}
|
cs |
스택이 가득 차있는지 확인하는 함수이다.
배열의 맨 끝 인덱스가 99이므로 top변수의 값이 99이면 1을 반환하고
그렇지 않다면 아직 가득 차지 않았으므로 0을 반환한다.
|
1
2
3
4
5
6
7
8
9
|
void push(stack* s, int data)
{
if (is_full(s)) {
printf("\nStack is full.\n");
exit(1);
}
printf("pushed: %d\n", data);;
s->arr[++(s->top)] = data;
}
|
cs |
데이터를 넣는 함수이다.
만약 스택이 가득 찼을 시 is_full 함수에서 1을 반환하여 스택이 가득 찼다는 문구를 남긴 뒤 시스템을 종료한다.
스택이 가득 차지 않았으면 push된 데이터를 출력한뒤 arr배열 현재 인덱스의 다음 인덱스에 데이터를 넣는다.
data = 1 일때, 현재 스택이 비어있다면 top = -1 이고, pushed : 1을 출력한다음 '++' 연산자가 앞에 놓여있으므로 배열의 인덱스가 0일때 data(1)를 넣는다.
|
1
2
3
4
5
6
7
8
|
int pop(stack* s)
{
if (is_empty(s)) {
printf("\nStack is empty.\n");
exit(1);
}
return s->arr[(s->top)--];
}
|
cs |
데이터를 빠져나오게 하는 함수이다.
만약 빼낼 데이터가 없는 스택이 비어있는 상태일 때 is_empty함수에서 1을 반환하여 스택이 비었다는 문구를 남긴뒤 시스템을 종료한다.
아직 빼낼 데이터가 있다면 top에 위치한 데이터를 반환시켜주고난 후 top이 있던 인덱스가 한칸 빠지기 때문에 '--'를 후에 해준다.
|
1
2
3
4
5
6
7
8
|
int peek(stack* s)
{
if (is_empty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->arr[(s->top)];
}
|
cs |
현재 top에 있는 데이터를 알려주는 함수이다.
스택이 비어있을시에는 pop함수와 마찬가지로 스택이 비어있음을 알린뒤 시스템을 종료한다.
비어있지 않다면 현재 스택의 맨 끝(위, top)에 위치한 데이터를 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int main()
{
stack s;
init(&s); // stack
push(&s, 3);
push(&s, 2);
push(&s, 1);
printf("\ntop check : %d\n\n", peek(&s));
printf("pop : %d\n", pop(&s));
printf("pop : %d\n", pop(&s));
printf("pop : %d\n", pop(&s));
printf("\npop : %d\n", pop(&s)); // empty
return 0;
}
|
cs |
스택에 데이터를 3, 2, 1 순으로 집어넣은 뒤 top에 있는 데이터가 무엇인지 확인한다. 그리고 pop함수를 이용해서 맨 나중에 들어간 데이터부터 빼내며 출력한다.
마지막에는 모든 데이터가 다 빠져나가서 스택이 비어있으니 스택이 비어있다고 알린 후 시스템을 종료한다.
결과♬