6강 / 20강

스택 — 마지막에 쌓은 접시를 먼저

실행 취소(Ctrl+Z)가 동작하는 원리

싱크대에 접시를 쌓았습니다. 이제 하나를 꺼내려면? 맨 위 것부터죠. 맨 아래 접시를 꺼내려면 위를 다 치워야 합니다.

이렇게 마지막에 넣은 것이 가장 먼저 나오는 규칙을 LIFO(Last In, First Out)라고 하고, 이 규칙을 지키는 자료구조가 스택(stack)입니다.

⬇️

push

맨 위에 올려놓기

⬆️

pop

맨 위 것 꺼내기

👀

peek

맨 위 것 보기만

파이썬에는 Stack 이라는 이름의 자료형이 따로 없습니다. 리스트의 append() 와 pop() 이 이미 정확히 스택이기 때문이에요.

고등학생마지막에 쌓은 접시를 먼저

스택은 규칙이 딱 하나인 자료구조입니다.

마지막에 넣은 것을 먼저 꺼낸다 — LIFO

비유 — 접시 쌓기

설거지한 접시를 위로 쌓습니다. 꺼낼 때는? 맨 위부터죠.

동작	어디서
넣기 (push)	맨 위
꺼내기 (pop)	맨 위

넣는 곳과 꺼내는 곳이 같다 — 그게 스택의 전부

이런 제한이 왜 유용한가

제한이 있으면 단순해집니다.

리스트	스택
어디든 넣고 뺀다	끝에서만
느릴 수 있다 (밀림)	항상 빠르다
실수 여지가 많다	적다

2강에서 본 "밀린다" 문제가 없다 — 끝만 건드리니까

일상에서 스택인 것들

것	왜 스택인가
Ctrl+Z	가장 최근 것부터 되돌린다
브라우저 뒤로가기	방금 온 곳으로
책 쌓기	위에서부터

공통점 — 되돌아가야 하는 일

리스트 두 함수만으로 스택이 완성됩니다.

Python 브라우저에서 실행

접시 = []                    # 빈 스택

접시.append("🍽️ 1번")        # push
접시.append("🍽️ 2번")
접시.append("🍽️ 3번")
print("쌓인 상태:", 접시)
print("맨 위(peek):", 접시[-1])

print("꺼냄:", 접시.pop())    # pop — 마지막에 넣은 3번이 먼저
print("꺼냄:", 접시.pop())
print("남은 것:", 접시)
print("비었나?", len(접시) == 0)

🎮 접시를 직접 쌓아 보세요

넣기와 빼기를 반복하면서 항상 맨 위에서만 일이 일어나는 걸 확인해 보세요. 빈 스택에서 꺼내려 하면 어떻게 되는지도 눌러 보시고요.

고등학생실행 취소가 동작하는 원리

Ctrl+Z 를 직접 만들어 봅시다. 생각보다 단순합니다.

한 동작을 할 때마다 되돌리는 법을 스택에 쌓는다

이렇게 됩니다

사용자가	스택에 쌓는 것
"안녕" 을 썼다	"뒤 2글자 지우기"
글자를 굵게 했다	"굵기 풀기"
그림을 넣었다	"그 그림 빼기"

Ctrl+Z 를 누르면 맨 위를 꺼내 실행한다

왜 반드시 스택이어야 하나

순서를 거꾸로 되돌려야 하니까요.

한 순서	되돌리는 순서
A → B → C	C → B → A

먼저 한 것을 먼저 되돌리면 엉킨다

비유 — 옷 입기

속옷 → 셔츠 → 재킷 순으로 입었습니다. 벗을 때는?

순서	가능한가
재킷 → 셔츠 → 속옷	된다 ✔
속옷부터	불가능

나중에 한 것이 위에 있으니 먼저 벗어야 한다

Ctrl+Y (다시 실행) 도 스택입니다

취소한 것을 또 다른 스택에 쌓아 둡니다.

동작	스택 이동
Ctrl+Z	실행취소 → 다시실행
Ctrl+Y	다시실행 → 실행취소
새 동작	다시실행 스택을 비운다

스택 두 개로 전부 구현된다

고등학생빈 스택에서 pop 하면

note 의 경고를 왜 그런지와 함께.

비었는데 꺼내면 오류 — 없는 것을 줄 수는 없다

언제 이런 일이 생기나

상황	예
Ctrl+Z 를 계속 누른다	더 되돌릴 게 없다
괄호 검사	여는 괄호 없이 닫는 괄호가 왔다
재귀가 너무 깊다	9강에서

두 번째가 실전에서 중요하다

괄호 검사 — 스택의 고전 문제

for 문자 in 식:
    if 문자 in "([{":
        스택.append(문자)
    else:
        if not 스택:              # ← 비었나 확인 ✔
            return "짝이 안 맞음"
        스택.pop()
return "OK" if not 스택 else "안 닫힘"

식	결과	왜
`([])`	OK	—
`(]`	오류	짝이 다르다
`())`	오류	빈 스택에서 pop
`((`	오류	끝났는데 스택이 남았다

두 가지를 다 확인해야 한다 — 중간에와 마지막에

왜 스택이 딱 맞나

괄호는 가장 최근에 연 것부터 닫아야 하니까요.

중첩 구조는 본질적으로 스택이다

HTML 태그, 프로그램의 블록, 수식의 괄호 — 전부 같은 구조입니다.

쓸모 ① 실행 취소 (Ctrl+Z)

여러분이 글을 쓸 때마다 프로그램은 직전 상태를 스택에 쌓아 둡니다. Ctrl+Z를 누르면 스택에서 하나 꺼내 되돌리죠. 그래서 가장 최근 것부터 취소되는 겁니다.

Ctrl+Z 를 12줄로 만들어 봅니다.

Python 브라우저에서 실행

글 = ""
역사 = []                       # 되돌리기용 스택

def 입력(글자):
    global 글
    역사.append(글)             # 바꾸기 전 상태를 쌓아 둔다
    글 = 글 + 글자
    print(f"입력 → '{글}'")

def 되돌리기():
    global 글
    if not 역사:
        print("더 되돌릴 게 없습니다")
        return
    글 = 역사.pop()             # 가장 최근 상태를 꺼낸다
    print(f"취소 → '{글}'")

입력("자"); 입력("료"); 입력("구"); 입력("조")
되돌리기()
되돌리기()
입력("실")

쓸모 ② 괄호 짝 맞추기

여는 괄호를 만나면 쌓고, 닫는 괄호를 만나면 꺼내서 짝이 맞는지 봅니다. 끝났을 때 스택이 비어 있으면 완벽하게 맞은 거예요. 코드 편집기가 괄호 오류를 잡아내는 방법이 바로 이겁니다.

편집기가 괄호를 검사하는 실제 알고리즘입니다.

Python 브라우저에서 실행

def 괄호검사(문자열):
    짝 = {")": "(", "]": "[", "}": "{"}
    스택 = []
    for 글자 in 문자열:
        if 글자 in "([{":
            스택.append(글자)
        elif 글자 in ")]}":
            if not 스택 or 스택.pop() != 짝[글자]:
                return False
    return len(스택) == 0

for 식 in ["(1+2)*[3-4]", "({[]})", "(1+2", "(]", "))((" ]:
    print(f"{식:12} → {'✅ 맞음' if 괄호검사(식) else '❌ 틀림'}")

고등학생스택은 '되돌아가야 할 때' 쓴다

note 의 이 한 줄이 스택을 알아보는 눈을 줍니다.

"어디서 왔는지" 를 기억해야 하면 스택이다

스택이 쓰이는 곳들

어디	기억하는 것
함수 호출	돌아갈 곳 (9강)
Ctrl+Z	되돌릴 동작
브라우저 뒤로가기	지나온 페이지
DFS	가야 할 갈림길 (15강)
수식 계산	계산 중인 값

가장 중요한 것이 첫 번째 — 함수 호출이 스택이다

함수가 스택인 이유

def a():
    b()      # b 가 끝나면 여기로 돌아와야
def b():
    c()      # c 가 끝나면 여기로

부를 때	끝날 때
a → b → c	c → b → a

호출 순서의 정확히 반대로 돌아온다 — 스택 그 자체

그래서 이걸 호출 스택(call stack) 이라 부릅니다. 오류 메시지에 나오는 그 목록이에요.

비유 — 심부름의 심부름

엄마가 심부름을 시켰는데, 가는 길에 다른 심부름이 생겼습니다.

순서	일
1	엄마 심부름 (기억)
2	가는 길의 심부름 (기억 위에 쌓음)
3	2번 끝 → 1번으로 돌아간다

머릿속에 "하던 일" 이 쌓인다 — 그게 스택이다

너무 많이 쌓이면? 잊어버리죠. 컴퓨터도 똑같습니다 — 스택 오버플로 (9강).

브라우저의 ← → 버튼을 스택 두 개로 재현합니다.

Python 브라우저에서 실행

# 브라우저 뒤로가기 — 스택 두 개면 앞으로가기까지 됩니다
뒤로 = []
앞으로 = []
현재 = "홈"

def 이동(주소):
    global 현재
    뒤로.append(현재)
    앞으로.clear()              # 새로 이동하면 앞으로 기록은 사라집니다
    현재 = 주소
    print(f"→ {현재}")

def 뒤로가기():
    global 현재
    if not 뒤로:
        print("뒤로 갈 곳이 없습니다"); return
    앞으로.append(현재)
    현재 = 뒤로.pop()
    print(f"← {현재}")

이동("검색"); 이동("뉴스"); 이동("영상")
뒤로가기(); 뒤로가기()
print("현재:", 현재, "| 뒤로:", 뒤로, "| 앞으로:", 앞으로)

🤔 확인 문제

스택에 1, 2, 3 을 순서대로 넣은 뒤 두 번 꺼내면 나오는 순서는?

🤔 확인 문제

다음 중 스택이 가장 어울리지 않는 상황은?

🤔 확인 문제

파이썬 리스트로 스택을 만들 때 pop() 대신 pop(0) 을 쓰면?

해설 pop(0)은 맨 앞을 꺼내므로 FIFO가 됩니다. 게다가 2강에서 본 것처럼 나머지가 전부 한 칸씩 밀려서 느려요. 스택은 반드시 양 끝 중 같은 쪽에서 넣고 빼야 합니다.