chorock.page
소개글시리즈프로젝트실험
© 2026 chorock.page
← 목록으로
자료구조 · 3/5
← 이전 글다음 글 →
python자료구조

스택(Stack) - ADT, 응용, DFS

2026.10.15 · 11분 읽기 · 조회 0

목차
StackStack ADT스택의 용도스택의 구현배열 구조함수 버전클래스 버전응용: 괄호 검사괄호 검사 알고리즘구현테스트 프로그램소스파일에서 괄호검사응용 : 수식의 계산후위표기 수식 계산 구현중위 -> 후위 변환 알고리즘변환 알고리즘 구현응용 : 미로 탐색깊이 우선 탐색(DFS)탐색 알고리즘구현테스트 프로그램

Stack

  • 스택은 후입선출(Last-In First-Out)의 자료구조다
  • 스택(stack) : 쌓아 놓은 더미
  • 삽입과 삭제가 Top에서만 일어나는 선형구조다
  • 가장 나중에 삽입된 자료가 가장 먼저 삭제된다

Stack ADT

  • push(e)는 맨 위에 추가, pop()은 맨 위 항목을 꺼내 반환한다.
  • peek()는 맨 위의 값을 반환한다

스택의 용도

  • 자료의 출력순서가 입력의 역순이어야 할 때 유용한 자료구조이다

ex)

  • 편집기의 되돌리기 기능
  • 함수호출에서 복귀주소 저장
  • 괄호 검사
  • 계산기: 후위 표기식 계산, 중위 표기식의 후위 표기식 반환
  • 웹 브라우저의 뒤로가기
  • 미로 탐색 등

스택의 구현

  • 스택의 항목을 저장하는 가장 간단한 방법은 배열구조를 이용하는 것이다.
  • 파이썬에서는 리스트를 사용한다. 단, 한쪽에서만 삽입•삭제한다.

배열 구조

배열을 통해 스택을 구현할 때 삽입/삭제 위치는 리스트의 맨 뒤가 유리하다

  • 전단 사용 : 모든 항목을 한 칸씩 뒤로 옮겨야 해서 O(n) -> 비효율적
  • 후단 사용 : 맨 뒤에 바로 추가, 삭제만 하면 되니 O(1)

함수 버전

python
top = []
def isEmpty():
    return len(top) == 0
 
def push(item):
    top.append(item)
 
def pop():
    if not isEmpty():
        return top.pop(-1)
        
def peek():
    if not isEmpty():
        return top[-1]
 
def size(): return len(top)
 
def clear():
    global top
    top = []
  • 전역 리스트 top 하나와 함수들로 스택을 만든다. clear()는 global 선언이 필요하다.

클래스 버전

python
class Stack:
    def __init__(self):
        self.top = []
    
    def isEmpty(self): return len(self.top) == 0
    def size(self): return len(self.top)
    def clear(self): return self.top = []
    
    def push(self, item):
        self.top.append(item)
    
    def pop(self):
        if not self.isEmpty():  
            self.top.pop(-1)
    
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]
    
    def __str__(self):
        return str(self.top[::-1])
  • top이 멤버변수가 되어 전역변수와 global이 필요없어졌다

응용: 괄호 검사


올바른 괄호 문자열이 되려면 3가지 조건을 모두 만족해야 한다. 어기는 조건에 따라 오류 종류가 갈린다.

괄호 검사 알고리즘

  • 가장 가까운 거리에 있는 괄호끼리 서로 쌍
  • 왼쪽 괄호가 나오면 스택에 저장하고, 오른쪽 괄호가 나오면 스택에서 괄호를 꺼내 짝을 맞추어 보면서 오류를 검사한다.
tsx
왼쪽 괄호 -> 스택에 push
오른쪽 괄호 -> pop()으로 가장 최근 괄호를 꺼낸다
스택이 비었을 때 pop -> 조건 2 위반
꺼낸 괄호가 짝이 안 맞다 -> 조건 3 위반
완수했는데 스택에 괄호가 남는다 -> 조건 1 위반

구현

python
def checkBrackets(statement):
    stack = Stack()
    for ch in statement:
        if ch in ( '{', '[', '(' ):
            stack.push(ch)
        elif ch in ( '}', ']', ')' ):
            if stack.isEmpty():
                return False  # 조건 2 위반
            else:
                left = stack.pop()
                if (ch == "}" and left != "{") or \
                   (ch == "]" and left != "[")
                   (ch == ")" and left != "(")
                   return False  # 조건 3 위반
     return stack.isEmpty()  # False면 조건 1 위반

테스트 프로그램

tsx
str = ( "{A[(i+1)]=0;}", "if((i==0) && (j==0))", "A[(i+1]) = 0;")
for s in str:
    m = checkBrackets(s)
    print(s," ---> ", m)

튜플에 넣고 돌리면 True, False, False 가 나온다.

소스파일에서 괄호검사

python
def checkBracketsV2(lines):
    for line in lines:
        res = checkBrackets(line)
        if not res:
            return False
    return True
 
filename = "ArrayStack.h" # 괄호를 검사할 소스 파일
infile = open(filename , "r") # 파일 열기
lines = infile.readlines(); # 파일 전체를 라인별로 읽은 리스트
infile.close() # 파일 닫기
 
result = checkBracketsV2(lines) # 검사 함수 호출 (약간 수정 필요)
print(filename, " ---> ", result) # 결과 출력
  • 파일을 줄 단위로 읽어 괄호를 검사한다

응용 : 수식의 계산

수식의 표기 방법

전위(prefix)중위(infix)후위(postfix)
연산자 피연산자1 피연산자2피연산자1 연산자 피연산자2피연산자1 피연산자2 연산자
+ A BA + BA B +
+ 5 * A B5 + A * B5 A B * +

수식 표현 방식은 크게 3가지로 나뉜다.
사람은 중위 표기로 쓰지만, 계산기는 이를 후위표기로 바꾼 뒤 스택으로 계산한다.

컴퓨터가 후위표기를 사용하는 이유

  1. 괄호가 필요없다.
    연산자의 위치 자체가 실행 순서를 결정한다.
    ((A + B) * C) => A B + C *
  2. 연산자 우선순위를 고려할 필요가 없다.
    마찬가지로 곱셈/나눗셈/덧셈/뺄셈 등 우선순위 규칙을 고려할 필요가 없어진다.
  3. 스택 자료구조를 이용해 간결하고 빠른 처리가 가능하다.
  • 피연산자: 만나면 그대로 Push
  • 연산자: pop 두 번 후 계산하고 결과를 push
  • 결과: 스택에 하나만 남고, 그 값이 최종 결과

후위표기 수식 계산 구현

python
def evalPostfix(expr):
    s = Stack()
    for token in expor:
        if token in "+-*/":
            val2 = s.pop()
            val1 = s.pop()
            if (token == '+'): s.push(val1 + val2)
            elif (token == '-'): s.push(val1 - val2)
            elif (token == '*'): s.push(val1 * val2)
            elif (token == '/'): s.push(val1 / val2)
        
        else:                      # 항목이 피연산자이면
            s.push(float(token))   # 실수로 변경해서 스택에 저장
            
    return s.pop()                 # 결과 반환
  • 수식은 리스트에 저장 ex) ['8', '2', '/', '3', '-', '3', '2', '*', '+']

테스트 프로그램

python
expr1 = [ '8', '2', '/', '3', '-', '3', '2', '*', '+' ]
expr2 = [ '1', '2', '/', '4', '*', '1', '4', '/', '*' ]
print(expr1, ' --> ', evalPostfix(expr1))
print(expr2, ' --> ', evalPostfix(expr2))
 
# ['8', '2', '/', '3', '-', '3', '2', '*', '+']  -->  7.0
# ['1', '2', '/', '4', '*', '1', '4', '/', '*']  -->  0.5

결과물이 잘 나온다.

중위 -> 후위 변환 알고리즘

  • 중위와 후위 표기의 공통점: 피연산자의 순서가 동일하다.
  • 연산자들의 순서만 다르다.
  1. 피연산자를 만나면 스택에 저장하지 않고 그대로 출력
  2. 연산자를 만나면 스택에 저장 재시도
  3. 스택의 top 연산자 보다 우선순위가 높은 연산자만 push, 낮거나 같으면 top을 출력하고 다시 비교
  4. 왼쪽괄호는 무조건 push하고 스택 안에서 가장 낮은 우선순위. 오른쪽 괄호는 왼쪽 괄호까지 모두 출력
python
2 + 3 * 4 -> 2 3 4 * +
 
2 : 숫자이므로 바로 출력 -> 출력: 2
+ : 연산자이므로 스택에 넣음 -> 스택: [+]
3 : 숫자이므로 바로 출력 -> 출력: 2 3
* : +보다 우선순위가 높으므로 스택에 얹음 -> 스택: [+, *]
4 : 숫자이므로 바로 출력 -> 출력: 2 3 4
수식 끝 : 스택에 남은 것들을 위에서부터 꺼냄 (* 후 +) -> 최종 출력: 2 3 4 * +
python
A * B + C -> A B * C +
 
초기 상태 : 스택: [] -> 출력: 없음
A : 피연산자이므로 바로 출력 -> 스택: [] -> 출력: A
* : 연산자이므로 스택에 넣음 -> 스택: ['*'] -> 출력: A
B : 피연산자이므로 바로 출력 -> 스택: ['*'] -> 출력: A B
+ : *를 꺼내 출력 후 +를 스택에 넣음 -> 스택: ['+'] -> 출력: A B *
C : 피연산자이므로 바로 출력 -> 스택: ['+'] -> 출력: A B * C
수식 끝 : 스택에 남은 연산자(+)를 꺼냄 -> 스택: [] -> 최종 출력: A B * C +
python
(A + B) * C -> A B + C *
 
( : 여는 괄호이므로 스택에 넣음 -> 스택: ['('] -> 출력: 없음
A : 피연산자이므로 바로 출력 -> 스택: ['('] -> 출력: A
+ : 연산자이므로 스택에 넣음 -> 스택: ['(', '+'] -> 출력: A
B : 피연산자이므로 바로 출력 -> 스택: ['(', '+'] -> 출력: A B
) : '('를 만날 때까지 출력 -> 스택: [] -> 출력: A B +
* : 연산자이므로 스택에 넣음 -> 스택: ['*'] -> 출력: A B +
C : 피연산자이므로 바로 출력 -> 스택: ['*'] -> 출력: A B + C
수식 끝 : 스택에 남은 연산자(*)를 꺼냄 -> 스택: [] -> 최종 출력: A B + C *

변환 알고리즘 구현

연산자들의 우선순위를 결정하는 함수가 먼저 필요하다.

python
def precedence (op):
    if op == '(' or op == ')' : return 0
    elif op == '+' or op == '-' : return 1
    elif op == '* or op == '/' : return 2
    
    else : return -1

각 연산다마다 숫자를 매겨 두면 우선순위 비교가 간단해진다.

python
def Infix2Postfix(expr):    # expr: 입력 리스트(중위 표기식)
    s = Stack()
    output = []
    
    for term in expr:
        if term in '(':
            s.push('(')     # 왼쪽 괄호는 바로 삽입
            
        elif term in ')':   
            while not s.isEmpty():
                
                op = s.pop()        # 왼쪽 괄호가 나올때 까지 출력
                if op == '(' : break;
                else:
                    output.append(op)
        
        elif term in "+-*/":        # 연산자일때
            while not s.isEmpty():
                op = s.peek()      # top 값을 op에 반환
                if (precedence(term) <= precedence(op)):
                    output.append(op)   # 우선순위가 더 낮으면 top을 출력
                    s.pop()
                else: break             # 우선순위가 높으면 멈추고 push   
            
            s.push(term)
        
        else:                        # 피연산자일때
            output.append(term)
    
    while not s.isEmpty():           # 처리 긑 -> 스택의 모든 항목 출력
        output.append(s.pop())
    
    return output                    # 후위식 리스트 반환 결과

테스트 프로그램

python
infix1 = [ '8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')' ]
infix2 = [ '1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')' ]
 
postfix1 = Infix2Postfix(infix1)
postfix2 = Infix2Postfix(infix2)
 
result1 = evalPostfix(postfix1)
result2 = evalPostfix(postfix2)
 
print(' 중위표기: ', infix1)
print(' 후위표기: ', postfix1)
print(' 계산결과: ', result1, end='\n\n')
 
print(' 중위표기: ', infix2)
print(' 후위표기: ', postfix2)
print(' 계산결과: ', result2)
 
# 실행 결과:
#  중위표기:  ['8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')']
#  후위표기:  ['8', '2', '/', '3', '-', '3', '2', '*', '+']
#  계산결과:  7.0
 
#  중위표기:  ['1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')']
#  후위표기:  ['1', '2', '/', '4', '*', '1', '4', '/', '*']
#  계산결과:  0.5

응용 : 미로 탐색

문제 상황

  • 미로를 N x N 크기의 격자로 표현하고, 시작칸에서 출구 칸 까지 길을 찾아야 한다.
  • 미로에 빠진 생쥐를 구한다.
tsx
map = [ [ '1', '1', '1', '1', '1', '1' ],
        [ 'e', '0', '0', '0', '0', '1' ],
        [ '1', '0', '1', '0', '1', '1' ],
        [ '1', '1', '1', '0', '0', 'x' ],
        [ '1', '1', '1', '0', '1', '1' ],
        [ '1', '1', '1', '1', '1', '1' ] ]
 
MAZE_SIZE = 6

다음과 같이 주어진다. 해당 문제를 풀기 위해선 DFS에 대해 알아야 한다.

깊이 우선 탐색(DFS)

  • 가던 길이 막히면 가장 최근에 있었던 갈림길로 되돌아가서 선택하지 않았던 길을 선택한다.
  • 갈림길을 만나면 스택에 저장한다
  • 되돌아 오면 스택에 저장된 다른 길을 꺼낸다.
  • 마지막에 저장한 갈림길로 먼저 돌아가야 하므로 LIFO 가 맞다.
    1. 인근 노드를 큰 번호부터 push 한다.
  1. 방문한 노드는 pop 출력한다
python
단계  pop   push        스택(왼쪽이 바닥)
시작   -     1           [1]
1      1    3, 2        [3, 2]
2      2    5, 4        [3, 5, 4]
3      4    8           [3, 5, 8]
4      8    7, 6, 5     [3, 5, 7, 6, 5]
5      5    (없음)       [3, 5, 7, 6]
6      6    3           [3, 5, 7, 3]
7      3    7           [3, 5, 7, 7]
8      7    (없음)       [3, 5, 7]

-> 3, 5, 7이 중복으로 스택에 쌓이는 구간이 있다.
-> 이미 ""방문했는지" 를 확인하는 로직이 따로 필요하다.

탐색 알고리즘

  • 모든 칸의 위치를 (행, 열) 로 표시한다.

Step 1. 시작 위치를 스택에 쌓는다.
Step 2. 스택이 비어있지 않으면 하나 꺼내 현재 위치로 삼고 방문 표시를 한다. 비어 있으면 출구가 없으니 종료
Step 3. 현재 위치가 출구이면 성공. 종료
Step 4. 아니면 이웃을 상,하,좌,우 순서로 보고 방문 안 했고 갈 수 있으면 push 한 뒤 Step 2로 이동.

스택 변화

구현

갈 수 있는 길인지 체크하는 함수

python
def isValidPos(x, y):
    if x < 0 or y < 0 or x >= MAX_SIZE or y >= MAX_SIZE:
        return False
    else:
        return map[x][y] == '0' or map[x][y] == 'x'
  • 범위 검사를 먼저 수행한다
  • 갈 수 있는 칸: 0(길) or x(출구)
  • 못 가는 칸: 1(벽) 과 마침표(지나온 길)

DFS 함수

python
def DFS():
    stack = Stack()
    stack.push((1, 0))        # 시작 위치 (1, 0)
    print('DFS: ')
    
    while not stack.isEmpty():
        here = stack.pop()
        print(here, end = "->")
        (x, y) = here
        
        if map[x][y] == 'x':  # 현재 위치가 출구면 종료
            return True
            
        else:
            map[x][y] = '.'   # 현재 위치를 지나왔다고 표시
            if isValidPos(x-1, y): stack.push((x-1, y)) # 상
            if isValidPos(x+1, y): stack.push((x+1, y)) # 하
            if isValidPos(x, y-1): stack.push((x, y-1)) # 좌
            if isValidPos(x, y+1): stack.push((x, y+1)) # 우
        
        print("현재 스택:", stack)        # 결과(후위표기식 리스트) 반환
  • 해당 함수에서 stack을 queue로 바꾸고 pop을 deque로 바꾸면 BFS가 된다

테스트 프로그램

python
map = [ [ '1','1','1','1','1','1' ],
        [ '0','0','0','0','0','1' ],
        [ '1','0','1','0','1','1' ],
        [ '1','1','1','0','0','x' ],
        [ '1','1','1','0','1','1' ],
        [ '1','1','1','1','1','1' ] ]
MAX_SIZE = 6
 
result = DFS()
 
if result : print(' --> 미로탐색 성공')
else : print(' --> 미로탐색 실패')
 
# DFS :
# (1, 0)->현재 스택 : [(1, 1)]
# (1, 1)->현재 스택 : [(1, 2), (2, 1)]
# (1, 2)->현재 스택 : [(1, 3), (2, 1)]
# (1, 3)->현재 스택 : [(1, 4), (2, 3), (2, 1)]
# (1, 4)->현재 스택 : [(2, 3), (2, 1)]
# (2, 3)->현재 스택 : [(3, 3), (2, 1)]
# (3, 3)->현재 스택 : [(3, 4), (4, 3), (2, 1)]
# (3, 4)->현재 스택 : [(3, 5), (4, 3), (2, 1)]
# (3, 5)->-->미로탐색 성공!
초록
초록

앱과 웹을 만들고, 직접 운영하며 기록합니다.

댓글

giscus로 동작하며 GitHub Discussions에 저장됩니다.

관련 글

자료구조자료구조python

연결된 구조(LinkedList)

2026.11.17·7분 읽기·조회 0
자료구조python자료구조

큐(queue) - ADT, BFS

2026.10.16·4분 읽기·조회 0
자료구조python자료구조

리스트(List) : ADT, Array, Linked-List

2026.10.13·5분 읽기·조회 0

목차

StackStack ADT스택의 용도스택의 구현배열 구조함수 버전클래스 버전응용: 괄호 검사괄호 검사 알고리즘구현테스트 프로그램소스파일에서 괄호검사응용 : 수식의 계산후위표기 수식 계산 구현중위 -> 후위 변환 알고리즘변환 알고리즘 구현응용 : 미로 탐색깊이 우선 탐색(DFS)탐색 알고리즘구현테스트 프로그램