스택(Stack): LIFO 자료구조

스택이란

스택은 한쪽 끝에서만 삽입과 삭제가 일어나는 선형 자료구조다.

가장 나중에 넣은 자료가 가장 먼저 나온다. 이것이 LIFO 성질이다.

접시를 쌓는 것과 같다. 가운데 접시를 꺼내려면 위의 접시를 먼저 치워야 한다.

Push 절차

Push는 가득 찼는지 먼저 검사한 뒤 자료를 Top 위의 칸에 저장한다.

저장 뒤 Top을 한 칸 올리면 Top은 현재 자료 개수를 센다.

빈 스택에 값 3을 넣으면 Top은 0에서 1로 바뀐다.

예제 추적

용량 4인 배열 스택에 3, 7, 2, 9를 차례로 넣어 보자.

Pop을 두 번 하면 9와 2가 나온다. 마지막에 넣은 것부터 나온다.

남은 원소는 3과 7이며 Top은 2가 된다.

Overflow와 Underflow

Push는 Top을 올린 뒤 Top이 K를 넘는지 검사한다. 넘으면 Overflow다.

Pop은 먼저 Top이 0인지 검사한다. 0이면 빈 스택이므로 Underflow다.

두 예외는 연산 안에서 반드시 처리해야 자료구조의 무결성이 지켜진다.

정리

정리하면 스택은 LIFO 구조이며 삽입과 삭제가 한쪽 끝에서만 일어난다.

Push는 Top 증가 뒤 Overflow를, Pop은 빈 상태 검사 뒤 Underflow를 처리한다.

앞의 문제 정답은 Overflow다. Top이 5가 되어 K 4를 넘기 때문이다.