스택 ( Stack )

안녕하세요. hp 입니다 :)

오늘은 스택 자료구조에 대해서 공부해도록 하겠습니다.

📚 개념

스택은 데이터의 삽입과 삭제가 데이터의 한쪽 끝에서만 일어나는 자료구조입니다.
가장 마지막에 삽입된 데이터가 가장 먼저 사용되거나 삭제됩니다.
이를 후입선출 ( LIFO ) 라고 합니다.

스택은 삽입과 삭제에 O(1)의 시간복잡도를 가지고 있다.

단 , 탐색은 O(N)의 시간복잡도를 가진다.

💡 스택 함수

• push
  스택에 원소를 추가한다.

• pop
  스택 가장 위에 있는 원소를 삭제하고 반환

• empty
  스택에 원소가 비어있는지 확인

예시
push(1) -> push(2) -> push(3) -> pop() -> pop() -> pop()

이를 파이썬에서는 리스트를 이용해서 아주 간단하게 표현할 수 있습니다.

바로 append()와 pop()을 이용해서 사용할 수 있습니다.

리스트에서 append는 가장 오른쪽에 원소를 삽입하고 pop에 경우에는 가장 오른쪽에 원소를 삭제시킵니다. ( stack에 작동방식과 같다. )

stack = []

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

print(stack) # [1,2,3] 

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

print(stack) # []

🎯 백준을 통한 문제 풀이

백준 10828번 스택 문제
백준 9012번 괄호 문제
백준 1874번 스택 수열 문제

📌 참고

문제를 풀다보면 시간복잡도의 중요성을 알게된다. 그럴때마다 내가 사용하는 연산자의 시간복잡도를 알아두는것은 많은 도움이 된다.

파이썬 자료형 별 시간복잡도