python/ python에서 stack 다루기

 

Stack 간단히 알아보기

시간 상 가장 최근에 추가한 데이터가 가장 먼저 나오는 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조!

 

push: 스택에 데이터를 추가

pop: 스택에서 데이터를 추출

 

---

파이썬으로 Stack 사용해보기

 

Stack 선언

stack = []

 

파이썬의 기본 리스트 자료형은 Dynamic Array로 구현되어 있으므로 Stack처럼 사용할 수 있다. 기본 리스트 자료형 사용법과 같이 리스트를 선언하고, Stack으로 사용하면 된다!

 

---

 

Stack에 데이터를 추가하기

stack.append(2023) # stack에 2023을 추가한다

 

파이썬의 리스트 자료형은 append() 연산 시 자동으로 데이터를 리스트의 마지막 요소에 삽입해준다. 

 

---

Stack에서 데이터에 접근하기

last_element = stack[-1]

 

리스트의 마지막 인덱스에 접근해 마지막 요소에 접근한다.

 

 

---

 

Stack에서 데이터를 삭제하기

stack.pop() # 스택에서 마지막 요소를 제거하고 반환한다
last_element = stack.pop() # 스택에 저장되어 있던 마지막 요소가 제거되고 last_element에 할당된다

 

파이썬 리스트 자료형의 pop() 연산으로 스택의 마지막 요소를 제거하고, 요소를 반환하는 동작을 수행한다.

 

 

---

Stack 대표 유형 풀어보기

 

Valid Parentheses - LeetCode

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for ss in s:
            if ss == '(':
                stack.append(')')
            elif ss == '{':
                stack.append('}')
            elif ss == '[':
                stack.append(']')
            else:
                if not stack or stack.pop() != ss:
                    return False
                
        return not stack

 

1. 스택을 사용하는 가장 대표적인 문제로, 주어진 문자열이 유효한 괄호의 조합으로 이루어졌는지 확인한다.

 

2. 여는 괄호가 들어올 때는 스택에 해당 괄호와 짝을 이루는 닫는 괄호를 삽입해주고, 닫는 괄호가 들어올 때 스택이 비어있거나, 스택의 요소가 들어온 괄호와 일치하지 않는다면 유효하지 않은 문자열으로 판단해 False를 반환한다.

 

3. 문자열을 전부 순회한 후 스택이 비어있지 않다면 짝을 이루지 못한 괄호가 하나 이상 존재하는 것이므로 역시 False를 반환하고, 스택이 비어있을 때만 유효한 괄호로 이루어진 문자열이라고 판단한다.

 

---

+) Java에서 스택 사용하기

2022.05.27 - [data structure + algorithm] - java/ 자료구조 : 스택Stack과 큐Queue