스택(stack) 자료구조란?
스택은 후입선출(LIFO, Last-In-First-Out) 원칙에 따라 데이터를 쌓고, 가장 최근에 쌓인 데이터가 가장 먼저 처리되는 자료구조입니다. 주로 함수 호출과 관련된 작업, 괄호 검사, 뒤로 가기 등의 기능을 구현할 때 유용하게 사용됩니다.
스택은 기본적으로 두 가지 주요 동작을 수행합니다:
- push: 스택에 데이터를 쌓는 동작입니다. 가장 최근에 쌓인 데이터가 스택의 가장 위에 위치합니다.
- pop: 스택에서 가장 위에 있는 데이터를 가져오고 제거하는 동작입니다.
파이썬으로 스택 구현하기
파이썬에서 스택을 구현하는 방법은 간단합니다. 리스트(List)를 사용하여 스택을 구현할 수 있습니다. 파이썬 리스트는 동적 배열로 크기가 자동으로 조정되므로 스택으로 사용하기에 적합합니다.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def size(self):
return len(self.items)
스택 활용
1. 괄호 검사
프로그래머스나 백준에 가면 유사 문제가 다양하니, 풀어보시는 것을 추천합니다!
def is_balanced(expression):
stack = Stack()
opening_brackets = '([{'
closing_brackets = ')]}'
for char in expression:
if char in opening_brackets:
stack.push(char)
elif char in closing_brackets:
if stack.is_empty() or closing_brackets.index(char) != opening_brackets.index(stack.pop()):
return False
return stack.is_empty()
print(is_balanced("()")) # True
print(is_balanced("{[()]}")) # True
print(is_balanced("{[(])}")) # False
2. 함수 호출과 백트래킹
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
print(factorial(5)) # 출력: 120
