스택

• 파이썬은 기본적으로 스택 자료구조를 제공하지 않지만, 리스트를 이용해 스택을 구현할 수 있다.
• 스택은 LIFO(Last In, First Out) 방식으로 동작하며, 마지막에 추가된 항목이 가장 먼저 제거되는 구조
• 파이썬 리스트의 몇 가지 메서드를 사용하면 스택의 기본 연산을 구현할 수 있다.

 

1.스택 연산

• push: 스택에 데이터를 추가하는 연산

stack = []
stack.append(10)  # 스택에 10 추가
stack.append(20)  # 스택에 20 추가
print(stack)  # 출력: [10, 20]

 

• pop: 스택에서 가장 마지막에 추가된 데이터를 제거하고 반환하는 연산

popped_element = stack.pop()  # 스택에서 가장 위에 있는 20을 제거하고 반환
print(popped_element)  # 출력: 20
print(stack)  # 출력: [10]

 

• isFull: 스택이 가득 찼는지 확인하는 연산 (파이썬 리스트는 동적으로 크기가 늘어나므로 따로 구현하지 않음)

max_size = 10
def isFull(stack):
    return len(stack) == max_size

print(isEmpty(stack))  # 출력: False (스택에 10이 있음)

 

• isEmpty: 스택이 비어 있는지 확인하는 연산

def isEmpty(stack):
    return len(stack) == 0

print(isEmpty(stack))  # 출력: False (스택에 10이 있음)

 

• top (peek): 스택의 가장 위에 있는 데이터를 반환하되, 제거하지 않음

def top(stack):
    if isEmpty(stack):
        return None
    return stack[-1]

print(top(stack))  # 출력: 10 (스택의 맨 위 요소)

코테에서 괄호 문제 나오면 스택 생각!

짝을 짓는다 나오면 스택 생각!

이들 모두 가장 최근에 탐색한 데이터를 비교하는 원리 -> 스택

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

이 문제에서 이 부분 생각하는게 힘들었다.

회전시킨 배열을 생각해보자

  n = len(s)
  for i in range(n):
    stack = [ ]
    for j in range(n):
      c = s[(i + j) % n]

 

스택문제에서 많이 실수하는 부분: 스택이 비었는지 체크해야 한다.