스택

왜 배우는가: 스택은 함수 호출 복귀 주소 저장, 수식 계산, 되돌리기 기능 등 소프트웨어 전반의 기본 구조이며, 자료구조와 알고리즘 문제에서 삽입·삭제 알고리즘과 예외 처리를 묻는 문항으로 반복해 출제된다. 실무에서 오버플로·언더플로 처리가 빠진 코드가 메모리 오류의 원인이 되므로 정확한 조건 검사 순서를 익혀야 한다.

출제 이력: 제122회 2교시 6번, 제102회 4교시 6번

1. 한 줄 정의와 핵심 키워드

스택(Stack)은 한쪽 끝(Top)에서만 삽입과 삭제가 일어나는 후입선출(LIFO) 구조의 선형 자료구조이다.

스택은 한쪽 끝에서만 삽입(Push)과 삭제(Pop)가 이루어지는 LIFO 선형 자료구조이다.

• 핵심 키워드: LIFO(Last-In First-Out), Push(삽입), Pop(삭제), Top(스택 포인터), Overflow, Underflow, 배열 스택, 호출 스택

2. 개념 풀이

쉽게 말하면 접시를 쌓는 것과 같다. 가장 나중에 올린 접시가 가장 먼저 꺼내진다. 한가운데 접시는 위의 접시를 치워야 꺼낼 수 있다.

정식으로는 스택은 리스트의 한쪽 끝으로만 자료를 넣고 빼는 자료구조이며, 가장 나중에 삽입된 자료가 가장 먼저 삭제된다. 이 성질을 LIFO(Last-In First-Out) 라 한다.

핵심 용어는 다음과 같다.

• Push(삽입): Top 위치를 한 칸 올린 뒤 그 자리에 자료를 저장하는 연산이다. 저장 공간이 가득 찬 상태에서 실행하면 Overflow가 발생한다.
• Pop(삭제): Top 위치의 자료를 꺼내고 Top을 한 칸 내리는 연산이다. 스택이 비어 있으면 Underflow가 발생한다.
• Top(스택 포인터): 가장 최근에 삽입된 원소의 위치를 가리키는 변수이다. 배열 구현에서는 다음 삽입 위치나 현재 원소 수를 나타낸다.
• Overflow(오버플로): 스택 크기(K)를 넘어서 삽입하려는 상황이다. 예외로 처리해야 한다.
• Underflow(언더플로): 자료가 없는 스택에서 삭제하려는 상황이다. 예외로 처리해야 한다.

LIFO 구조는 새 자료를 쌓을 때 기존 자료의 위치를 바꾸지 않으므로, 연산 비용이 상수 시간 O(1)에 머문다.

3. 등장 배경과 필요성

프로그램이 함수를 호출하면 돌아올 주소를 기억해야 한다. 함수가 중첩되어 호출될수록 가장 나중에 호출된 함수가 가장 먼저 끝난다. 이 순서를 자연스럽게 따르는 구조가 스택이다. 그래서 대부분의 컴퓨터는 함수 호출과 복귀를 스택으로 처리한다.

수식 계산에서도 필요하다. 후위 표기법(Postfix Notation)으로 표현된 수식은 피연산자를 스택에 쌓아 두었다가 연산자를 만나면 꺼내서 계산하면 된다. 되돌리기(Undo) 기능이나 깊이 우선 탐색, 재귀 프로그램의 순서 제어에도 같은 원리가 쓰인다.

스택은 배열이나 연결 리스트로 구현할 수 있다. 배열로 구현하면 크기를 미리 정해야 하므로 Overflow 검사가 필요하다. 연결 리스트로 구현하면 크기 제한은 줄어들지만 노드마다 포인터 기억 공간이 추가된다. 따라서 구현 방식과 무관하게 Overflow와 Underflow를 예외로 처리하는 것이 자료구조의 무결성을 지키는 기본 조건이다.

Overflow 판정 기준은 Top이 스택 크기 K를 넘는지이다. 배열의 마지막 주소 M번지를 기준으로 Top이 M보다 커지면 Overflow로 본다. Underflow 판정 기준은 Top이 0인지이다. 삭제 전에 자료가 있는지 먼저 확인해야 한다.

4. 구성요소·원리·절차

스택은 배열 한 개와 스택 포인터 한 개로 구현한다. 정보관리기술사 답안에서는 구성요소를 먼저 나열하고 push와 pop의 절차를 순서대로 쓴다. 구성요소는 다음과 같다.

표의 구성요소는 모두 두 가지 연산의 판정에 쓰인다. 스택 포인터가 항상 최상단 원소의 위치를 가리키므로 연산은 한쪽 끝에서만 일어난다. 이것이 LIFO 원리의 근거다.

원리는 다음과 같다. push는 포인터를 먼저 판정하고 값을 쓴 뒤 포인터를 올린다. pop은 빈 상태를 먼저 판정하고 포인터를 내린 뒤 값을 꺼낸다. 두 연산 모두 검사가 먼저 와야 배열 범위를 벗어나지 않는다. 자료 개수 n과 크기 K 사이에는 항상 0 \le n \le K 가 성립한다.

push 전에 가득 참을, pop 전에 빈 상태를 먼저 검사한다

NFTC나 KS 같은 공식 기준은 스택 구현에 없다. 따라서 이 부분의 내용은 자료구조 교재의 일반 원리다.

push 절차는 다음과 같다.

• 스택 포인터가 크기와 같은지 검사한다. 같으면 Overflow 처리 후 종료한다.
• 다음 칸(Top)에 Data를 저장한다.
• 스택 포인터를 1 증가시킨다.

pop 절차는 다음과 같다.

• 스택 포인터가 0인지 검사한다. 0이면 Underflow 처리 후 종료한다.
• 스택 포인터를 1 감소시킨다.
• 감소된 위치의 값을 꺼내 반환한다.

수식으로 쓰면 push는 Top \leftarrow Top + 1 후 Nodes[Top-1] \leftarrow Data 이고, pop은 Top \leftarrow Top - 1 후 Data \leftarrow Nodes[Top] 이다. 여기서 Top은 원소 개수를 나타내는 정수이고 단위는 개이다.

5. 관련 법령·기준·표준

스택 자료구조에는 법령이나 고시가 적용되지 않는다. 관련 기준은 자료구조 교재와 C 언어 구현 관례다. 기준값은 다음 표와 같다.

표의 수치는 배열 기반 구현에 한정된다. 연결 리스트 기반 스택은 크기 제한이 없으므로 Overflow가 발생하지 않는다. 동적 배열 기반 스택은 용량이 부족하면 크기를 늘린다. 이때 재할당 비용이 생기므로 평균 O(1)이라고 쓴다.

스택 기준 개정 연혁은 없다.

6. 유형과 비교

스택은 구현 방식과 용도에 따라 몇 가지 유형으로 나눌 수 있다. 가장 기본은 배열 스택(Array Stack) 과 연결 리스트 스택(Linked List Stack) 의 구현 방식 차이이며, 응용에 따라 함수 호출 스택(Call Stack) 과 수식 계산 스택(Expression Stack) 으로 쓰임이 나뉜다. 구현 방식의 차이는 아래 표와 같다.