스택

스택은 나중에 넣은 것을 먼저 꺼내는 그릇입니다. 값이 드나드는 자리는 한쪽 끝 하나뿐입니다. 맨 위에 얹힌 것 말고는 손이 닿지 않습니다.

상세

스택은 값이 드나드는 자리를 한쪽 끝으로 제한한 자료구조입니다. 쌓아 올린 접시 더미에서 맨 위 접시만 집어낼 수 있는 것과 같습니다. 그 끝을 맨 위라고 부릅니다. 새로 넣은 값은 언제나 맨 위에 얹힙니다. 뺄 수 있는 값도 맨 위 하나뿐입니다. 그래서 가장 나중에 넣은 값이 가장 먼저 나옵니다. 이 성질을 후입선출이라고 부릅니다. 영어로는 LIFO(Last In First Out)라고 적습니다.

제한이 이 자료구조의 본체입니다. 중간에 놓인 값은 꺼낼 수 없습니다. 몇 번째 값인지로 지목할 수도 없습니다. 위에 쌓인 것을 다 걷어내야 그 아래가 맨 위가 됩니다. 대신 넣기와 빼기가 한쪽 끝에서만 일어나므로 나머지 값은 자리를 옮기지 않습니다. 중간을 내주고 끝을 얻은 것입니다.

스택은 추상 자료형입니다. 값을 안쪽에 어떤 모양으로 담는지는 정의에 들어 있지 않습니다. 정의에 들어 있는 것은 어떤 연산을 어떤 규칙으로 내놓느냐뿐입니다.

형태

스택이 내놓는 연산은 넷입니다. 넣기(push) · 빼기(pop) · 맨 위 보기(peek) · 비었나 묻기(empty) 입니다.

넷이 지키는 규칙은 네 줄로 적힙니다.

• 값을 하나 넣고 곧바로 빼면 넣기 전의 스택으로 돌아옵니다
• 값을 하나 넣고 맨 위를 보면 방금 넣은 그 값이 나옵니다
• 새로 만든 스택은 비어 있습니다
• 값이 하나라도 들어 있으면 비어 있지 않습니다

flowchart TD
    subgraph STK["스택 · 드나드는 자리는 맨 위 하나뿐이고 그 아래는 손이 닿지 않습니다"]
        TOP["맨 위 · 7"]
        MID["4"]
        BOT["맨 아래 · 3"]
        TOP --- MID
        MID --- BOT
    end
    IN["넣기"] --> TOP
    TOP --> OUT["빼기 · 맨 위 보기"]

그림에서 넣기와 빼기와 맨 위 보기가 붙는 자리는 맨 위 하나뿐입니다. 맨 아래에 깔린 3 은 그 위의 4 와 7 을 다 걷어내기 전까지 어느 연산으로도 건드릴 수 없습니다.

이 넷이 곧 스택의 정의입니다. 안쪽을 배열로 담든 연결 리스트로 담든, 바깥에 이 넷을 같은 규칙으로 내놓으면 스택입니다.

복잡도

n 은 스택에 담긴 원소의 개수입니다.

임의 위치 접근은 표에 없습니다. 비용이 커서 뺀 것이 아니라 연산 자체가 정의에 들어 있지 않습니다. k 번째 원소를 보려면 위에서부터 k 번 빼야 합니다. 그건 스택의 연산이 아니라 스택을 쓰는 쪽이 짜는 절차입니다.

넣기의 최악이 오는 자리

넣기의 최악은 배열로 담았을 때만 옵니다. 잡아둔 칸이 다 차면 더 큰 칸을 새로 잡고 원소를 전부 옮겨야 합니다. 그 한 번의 넣기가 O(n) 입니다. 다만 칸을 늘릴 때마다 배로 늘리면 옮기는 비용이 그 뒤의 넣기들에 나눠 실립니다. 그래서 넣기 한 번의 상환 비용은 O(1) 로 유지됩니다. 한 번의 최악과 상환 평균은 다른 값이라 따로 적습니다.

옮기기 전에는 잡아둔 칸이 값으로 꽉 차 있습니다.

flowchart TD
    subgraph BEF["옮기기 전 · 잡아둔 칸 셋이 다 찼습니다"]
        direction TD
        B1["3 · 맨 아래"] --- B2["4"] --- B3["7 · 맨 위"]
    end

한 칸을 더 넣는 순간 더 큰 칸을 새로 잡고 담겨 있던 값을 전부 그리로 옮깁니다. 옮기는 값의 개수가 곧 그 한 번의 비용입니다.

flowchart TD
    subgraph AFT["옮긴 뒤 · 칸을 배로 잡고 셋을 전부 옮겼습니다"]
        direction TD
        A1["3 · 맨 아래"] --- A2["4"] --- A3["7"] --- A4["9 · 맨 위"] --- A5["빈 칸"] --- A6["빈 칸"]
    end

담는 방식이 가르는 공간

연결 리스트로 담으면 재할당이 없습니다. 대신 원소마다 다음 마디를 가리키는 포인터가 하나씩 더 붙습니다. 값 자체가 작을수록 이 덧붙는 몫의 비율이 커집니다. 배열은 칸을 미리 잡아두는 대신 옮기는 최악을 가끔 치릅니다. 연결 리스트는 옮기는 최악이 없는 대신 원소마다 포인터를 늘 치릅니다.

같은 스택인데 안쪽 모양이 이렇게 갈립니다.

flowchart TD
    subgraph LNK["연결 리스트로 담기 · 마디마다 포인터가 하나씩 더 붙습니다"]
        direction TD
        N3["7 · 맨 위"] -->|포인터| N2["4"] -->|포인터| N1["3 · 맨 아래"]
    end
    subgraph ARR["배열로 담기 · 값이 붙은 칸에 나란히 놓입니다"]
        direction TD
        R1["3 · 맨 아래"] --- R2["4"] --- R3["7 · 맨 위"] --- R4["아직 안 쓴 칸"]
    end

배열 쪽은 값 말고 더 드는 것이 아직 안 쓴 칸뿐입니다. 연결 리스트 쪽은 빈 칸이 없는 대신 마디마다 화살표 하나를 값과 같이 들고 다닙니다.

예시

자바 가상 머신의 스레드 스택

자바 가상 머신(Java Virtual Machine, JVM) 명세는 스레드마다 전용 스택을 하나씩 둡니다. 스택은 스레드가 만들어질 때 같이 만들어집니다. 그 안에 담기는 것은 프레임입니다. 명세는 이 스택을 C 같은 기존 언어의 스택에 견줍니다. 지역 변수와 중간 결과를 담습니다. 메서드 호출과 반환에도 관여합니다.

여기서 스택의 제한이 그대로 드러납니다. 명세는 이 스택이 프레임을 넣고 빼는 것 말고는 직접 조작되지 않는다고 적습니다. 그래서 프레임을 힙에 할당해도 됩니다. 스택을 담는 메모리가 연속일 필요도 없습니다.

flowchart TB
    subgraph T2["스레드 2 전용 스택 · 쌓인 순서"]
        F2A["프레임 · 맨 위"] --- F2B["프레임 · 맨 아래"]
    end
    subgraph T1["스레드 1 전용 스택 · 쌓인 순서"]
        F1A["프레임 · 맨 위"] --- F1B["프레임"] --- F1C["프레임 · 맨 아래"]
    end
    subgraph HEAP["힙 · 프레임을 여기 할당해도 됩니다"]
        H1["프레임"]
        H2["프레임"]
        H3["프레임"]
        H4["프레임"]
        H5["프레임"]
    end
    F1A -.-> H3
    F1B -.-> H1
    F1C -.-> H5
    F2A -.-> H2
    F2B -.-> H4

위쪽 두 상자가 스레드마다 하나씩 딸린 전용 스택입니다. 그 안의 순서는 프레임이 쌓인 순서일 뿐입니다. 점선은 그 프레임이 실제로 놓일 수 있는 자리를 가리킵니다. 점선이 뒤엉킨 것은 그 자리가 이어져 있을 필요가 없다는 뜻입니다.

크기는 고정일 수도 있고 계산이 요구하는 대로 늘고 줄 수도 있습니다. 명세는 구현이 초기 크기를 프로그래머나 사용자가 정하게 해 줄 수도 있다고 적습니다. 늘고 주는 스택이면 최대 크기와 최소 크기도 정하게 해 줄 수 있습니다.

넘칠 때 무슨 일이 나는지도 명세가 정합니다. 한 스레드의 계산이 허용된 것보다 큰 스택을 요구하면 자바 가상 머신이 StackOverflowError 를 던집니다. 늘려야 할 때 그만한 메모리를 확보하지 못하면 OutOfMemoryError 를 던집니다. 새 스레드의 처음 스택조차 못 만들 때도 같습니다.

파이썬 리스트의 append 와 pop

파이썬 공식 튜토리얼은 리스트를 스택으로 쓰는 법을 따로 적습니다. 맨 위에 얹을 때는 append() 를 씁니다. 맨 위에서 꺼낼 때는 인덱스를 주지 않은 pop() 을 씁니다.

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

pop() 이 돌려주는 값이 7 · 6 · 5 순서라는 점이 이 예시의 전부입니다. 넣은 순서는 3 · 4 · 5 · 6 · 7 이었습니다. 마지막에 넣은 것부터 나옵니다.

C++ 표준의 stack 컨테이너 어댑터

C++ 표준 초안은 stack 을 컨테이너 어댑터로 규정합니다. 스스로 값을 담지 않습니다. 다른 컨테이너를 감쌀 뿐입니다. back() · push_back() · pop_back() 을 제공하는 시퀀스 컨테이너면 무엇이든 stack 을 만드는 데 쓸 수 있습니다. 표준은 vector · list · deque 를 그 예로 듭니다. 템플릿 인자를 안 주면 deque 가 됩니다.

classDiagram
    class stack {
        Container c
        +empty()
        +top()
        +push()
        +pop()
    }
    class SEQ["시퀀스 컨테이너 · vector · list · deque"] {
        +empty()
        +back()
        +push_back()
        +pop_back()
    }
    stack o-- SEQ : empty 는 empty · top 은 back · push 는 push_back · pop 은 pop_back 을 부릅니다

stack 이 가진 것은 감싼 컨테이너 하나뿐입니다. 바깥으로 내놓는 연산 넷은 전부 그 컨테이너의 연산으로 그대로 넘어갑니다.

template<class T, class Container = deque<T>>
class stack {
protected:
  Container c;
public:
  constexpr bool empty() const { return c.empty(); }
  constexpr reference top() { return c.back(); }
  constexpr void push(const value_type& x) { c.push_back(x); }
  constexpr void pop() { c.pop_back(); }
};

top() 은 감싼 컨테이너의 back() 을, push() 는 push_back() 을, pop() 은 pop_back() 을 그대로 부릅니다. 감싼 컨테이너가 무엇이든 밖으로 나오는 연산은 한쪽 끝을 다루는 것뿐입니다. 앞에서 적은 형태가 그대로 코드가 된 자리입니다.

POSIX 스레드의 스택 크기 속성

POSIX(Portable Operating System Interface) 스레드는 스레드마다 딸리는 스택의 크기를 속성으로 정합니다. pthread_attr_setstacksize() 가 스레드 속성 객체에 그 값을 박습니다. pthread_attr_getstacksize() 가 그 값을 읽어옵니다.

이 속성은 그 속성 객체로 만드는 스레드에 할당될 최소 크기를 바이트 단위로 정합니다. 값에 하한이 있습니다. PTHREAD_STACK_MIN(16384) 바이트보다 작으면 EINVAL 로 실패합니다. 어떤 시스템에서는 크기가 시스템 페이지 크기의 배수가 아닐 때도 EINVAL 로 실패할 수 있습니다.

관련 항목

이것이 속하는 상위 분류

추상 자료형 · 컨테이너 어댑터

같은 자리를 두고 겨루는 자료구조

큐 · 덱

안쪽 구현에 쓰이는 자료구조

배열 · 연결 리스트 · 시퀀스

이것을 정의하는 표준·문서

JVM · C++ · 파이썬 · POSIX 스레드

이것이 프로그램 실행에서 맡는 역할

호출 스택 · 스택 프레임 · 스택 포인터 · 오퍼랜드 스택 · 재귀 · 문맥 교환

이것을 도구로 쓰는 기법

깊이 우선 탐색 · 후위 표기법 · 되돌리기

이것의 하위 종류

경계 스택 · 캑터스 스택

이것에서 자주 나는 오류·장애

스택 오버플로 · StackOverflowError · OutOfMemoryError