자료구조(파이썬) - 스택 (Stack)

교육 정보

• 교육 명: 경기미래기술학교 AI 교육
• 교육 기간: 2023.05.08 ~ 2023.10.31
• 오늘의 커리큘럼:
  파이썬 자료구조
  (7/31 ~ 8/18)
• 강사: 이현주, 이애리 강사님
• 강의 계획:
  1. 자료구조

자료구조

스택 (Stack)

• LIFO(Last in First Out) 방식의 자료구조
• 파이썬에서는 deque로 구현 가능

from collections import deque 

stack = deque() 
# stack을 deque가 아닌 list로 해도 똑같이 사용가능 (함수도 똑같음), 시간 복잡도도 O(1)

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

print(stack)

print(stack.pop())
print(stack.pop())
print(stack.pop())

print(stack)

#
# 결과

deque([1, 2, 3, 4, 5])
5
4
3
deque([1, 2])

• stack을 사용한 괄호 닫힘 확인 알고리즘

from collections import deque

def parentheses_checker(string):
    print(f"테스트하는 문자열: {string}")
    stack = deque() # 사용할 스택 정의
    stack_list = list(string)
    

    for idx, char in enumerate(stack_list): # stack
      # print(char, idx)
      if char == "(":
        stack.append(idx)
        # print(stack, len(stack))
      elif char == ')':
        if len(stack) != 0:
          stack.pop()
        else:
          print(f'문자열 {idx} 번째 위치에 있는 닫는 괄호에 맞는 열리는 괄호가 없습니다')
    if len(stack) != 0:
      for idx in stack:
        print(f'문자열 {idx} 번째 위치에 있는 닫는 괄호에 맞는 열리는 괄호가 없습니다')
        
parentheses_checker('((3+8)-(7*2)/3))')
   
#
# 결과

테스트하는 문자열: ((3+8)-(7*2)/3))
문자열 15 번째 위치에 있는 닫는 괄호에 맞는 열리는 괄호가 없습니다