[자료구조] 4.스택

스택의 개념과 동작 원리

스택(Stack)은 후입선출(Last-In-First-Out, LIFO) 원칙을 따르는 자료구조입니다. 즉, 가장 최근에 추가된 항목이 가장 먼저 삭제됩니다. 스택은 push(삽입), pop(삭제), top(가장 위의 항목 확인), empty(스택이 비어 있는지 확인) 등의 연산을 지원합니다. 데이터는 스택의 가장 상단에 위치하며, 스택의 맨 위를 top이라고 부릅니다. push 연산을 통해 데이터를 스택에 추가하면 top이 그 데이터를 가리키도록 바뀌며, pop 연산을 통해 top에 위치한 데이터를 삭제할 수 있습니다.

스택은 다양한 응용 분야에서 사용됩니다. 예를 들어, 함수의 호출과 반환, 괄호 짝 검사, 뒤집기(reverse) 등에 활용됩니다. 파이썬에서 스택을 구현하는 방법에는 리스트(List)를 이용하는 방법과 연결 리스트(Linked List)를 이용하는 방법이 있습니다. 리스트를 이용하는 방법은 간단하고 구현이 쉬우며, 파이썬의 기본 자료구조인 리스트를 이용하여 쉽게 구현할 수 있습니다. 연결 리스트를 이용하는 방법은 구현이 복잡하지만, 스택의 크기가 가변적일 경우에는 유용합니다.

스택에서 핵심적인 연산인 push와 pop 연산의 시간 복잡도는 O(1)입니다. 그러나 스택에서 탐색 연산은 최악의 경우 O(n)의 시간 복잡도를 가집니다. 따라서, 스택은 탐색이 필요하지 않을 때, 즉 LIFO 원칙을 따르는 경우에 사용하는 것이 적합합니다. 스택은 함수의 호출과 반환, 괄호 짝 검사 등에서 활용됩니다. 스택에서 탐색 연산은 최악의 경우 O(n)의 시간 복잡도를 가지므로, 스택은 탐색이 필요하지 않은 경우에 적합합니다.

배열 구조(파이썬 리스트)를 이용한 스택의 구현 방법

스택의 구현(함수 버전)

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 = []

스택의 구현(클래스 버전)

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): self.top = []
    def push(self,item):
        self.top.append(item)
        
    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)
        
    def peek(self):
        if not self.isEmpty():
            return self.top[-1]

괄호 검사, 수식의 계산, 미로 탐색 등에 스택을 활용하여 문제 해결

스택(Stack)은 다양한 응용 분야에서 사용됩니다. 여기서는 괄호 검사, 수식의 계산, 미로 탐색 등의 예시에 대해 설명하겠습니다.

괄호 검사(Parenthesis Matching)
- 괄호 검사는 스택을 이용하여 구현할 수 있습니다. 여는 괄호가 나타나면 스택에 push하고, 닫는 괄호가 나타나면 스택에서 pop하여 검사합니다. 만약 스택이 비어있거나, 괄호의 짝이 맞지 않는 경우 괄호가 올바르게 닫히지 않았다는 것을 알 수 있습니다.

def check_parenthesis(expr):
    stack = []
    for c in expr:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if not stack:
                return False
            stack.pop()
    return not bool(stack)

수식의 계산(Expression Evaluation)
- 중위 표기법으로 표현된 수식을 후위 표기법으로 변환한 후, 스택을 이용하여 계산할 수 있습니다. 숫자를 스택에 push하고, 연산자가 나타나면 스택에서 숫자를 pop하여 계산하고 다시 스택에 push합니다.

def eval_postfix(expr):
    stack = []
    for token in expr:
        if token.isdigit():
            stack.append(int(token))
        else:
            right_operand = stack.pop()
            left_operand = stack.pop()
            if token == '+':
                result = left_operand + right_operand
            elif token == '-':
                result = left_operand - right_operand
            elif token == '*':
                result = left_operand * right_operand
            elif token == '/':
                result = left_operand / right_operand
            stack.append(result)
    return stack.pop()

미로 탐색(Maze Solving)
- 미로 탐색은 DFS(깊이 우선 탐색) 알고리즘을 이용하여 스택으로 구현할 수 있습니다. 현재 위치에서 이동 가능한 방향을 스택에 push하고, 이동한 위치를 스택에 push합니다. 이동한 위치가 목적지와 일치하는 경우 탐색을 종료합니다.

def solve_maze(maze, start, end):
    stack = [(start[0], start[1])]
    visited = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == end:
            return True
        if (x, y) in visited:
            continue
        visited.add((x, y))
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] != 'X':
                stack.append((nx, ny))
    return False

위 코드에서는 DFS 알고리즘을 스택으로 구현하였습니다. 스택에서 현재 위치를 pop하여 이동 가능한 방향을 스택에 push합니다. 이동한 위치가 목적지와 일치하는 경우 탐색을 종료합니다. 이동 가능한 방향은 상, 하, 좌, 우로 이동하는 것을 고려하여 4개의 방향을 검사합니다. 이미 방문한 위치는 visited 집합에 추가하여 중복 방문을 방지합니다.

위와 같이 괄호 검사, 수식의 계산, 미로 탐색 등에서 스택을 활용할 수 있습니다. 스택은 LIFO(후입선출) 구조를 가지고 있기 때문에, 가장 최근에 추가된 항목을 먼저 처리해야 하는 경우에 유용합니다.