yeolyi.com성열의 컴퓨터공학

스택

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

문서 편집기에서 실행 취소를 누르면 가장 최근에 한 작업부터 되돌리고, 한 번 더 누르면 그 전의 작업을 되돌립니다. 브라우저의 뒤로 가기 버튼도 마찬가지입니다. 이런 일에는 배열이나 연결 리스트처럼 아무 위치에나 넣고 뺄 수 있을 필요가 없습니다. 가장 최근에 넣은 것만 꺼낼 수 있으면 됩니다.

접시 쌓기

식당에서 씻은 접시를 쌓아 두는 모습을 생각해 봅시다. 새 접시는 맨 위에 올리고, 접시를 쓸 때도 맨 위에서 가져갑니다.

이처럼 한쪽 끝에서만 넣고 빼는 구조가 스택 포인터 글에서 돌아올 주소를 쌓던 스택(stack)입니다. 이번에는 이를 프로그램에서 직접 쓰는 자료구조로 만들어 봅시다. 넣는 일을 푸시(push), 꺼내는 일을 팝(pop)이라 부릅니다. 넣고 빼는 쪽 끝은 맨 위라는 뜻으로 top이라 합니다. 가장 나중에 들어간 것이 가장 먼저 나오므로 LIFO(Last In, First Out)라고도 합니다.

스택 (배열 6칸)
0← top
1
2
3
4
5
꺼낸 순서

top = 0

스택은 배열 하나와 숫자 하나로 만들 수 있습니다. 숫자 top은 다음에 넣을 칸의 인덱스입니다. 넣을 때는 top 칸에 값을 쓰고 top을 하나 늘립니다. 꺼낼 때는 top을 하나 줄이고 그 칸의 값을 읽습니다. 배열의 맨 끝에서만 일하니 몇 개가 쌓여 있든 한 칸만 건드립니다.

1#include <stdio.h>
2
3int main(void) {
4 int stack[4] = {0, 0, 0, 0};
5 // 다음에 넣을 칸
6 int top = 0;
7 // 1, 2, 3 넣기
8 for (int value = 1; value <= 3; value++) {
9 stack[top] = value;
10 top = top + 1;
11 }
12 // 모두 꺼내기
13 while (top > 0) {
14 top = top - 1;
15 printf("%d\n", stack[top]);
16 }
17 return 0;
18}

변수 없음
출력 없음

배열 대신 연결 리스트로 만들어도 됩니다. 연결 리스트는 맨 앞에서 넣고 빼는 일이 빨랐으니, 첫 노드를 스택의 맨 위로 삼으면 됩니다. 배열처럼 칸 수를 미리 정할 필요도 없습니다.

괄호 짝 맞추기

컴파일러는 (a+[b*c])처럼 괄호가 여러 겹 들어간 식에서 괄호가 제대로 짝지어졌는지 확인합니다.

([)]는 여는 괄호와 닫는 괄호의 개수가 같지만 짝이 틀렸습니다. [가 닫히기 전에 )가 먼저 나왔기 때문입니다. 규칙은 이렇습니다. 가장 나중에 열린 괄호가 가장 먼저 닫혀야 합니다. 가장 나중에 넣은 것이 가장 먼저 나오는 스택과 같은 모양입니다.

그래서 글자를 왼쪽부터 읽으며 여는 괄호는 스택에 쌓습니다. 닫는 괄호가 나오면 스택의 맨 위를 꺼내 짝인지 확인합니다. 꺼낼 것이 없거나 짝이 아니면 틀린 것입니다. 끝까지 읽었을 때 스택이 비어 있으면 짝이 모두 맞은 것입니다.

검사할 글
읽는 위치
(a+[b*c])
스택 (오른쪽 끝이 맨 위)
비어 있음

왼쪽부터 한 글자씩 읽습니다.

도전 문제

1, 2, 3, 4, 5를 이 순서대로만 스택에 넣을 수 있고, 넣기 사이사이 언제든 맨 위를 꺼낼 수 있습니다. 다섯 값을 모두 꺼냈는데 처음 꺼낸 값이 3이었습니다. 다섯 번째로 꺼낸 값이 될 수 있는 수를 작은 것부터 이어 적으세요. 예를 들어 2와 4라면 24입니다.