[자료구조] 스택(stack)

스택(Stack)

LIFO(Last in First Out)

나중에 들어간 데이터가 가장 먼저 나오는 입구와 출구가 같은 형태

맨 뒤 삽입 + 맨 뒤 접근 및 삭제 기능이 필요하다.

따라서 큐와 마찬가지로 더블리 링크드 리스트를 이용하는 것이 효율적이다.

from collections import deque

stack = []

# 스택 맨 끝에 데이터 추가
stack.append("A")
stack.append("B")

# 맨 끝 데이터 접근
print(stack[-1])

# 맨 끝 데이터 삭제
print(stack.pop())

print(stack) # 스택 출력

>>>  B
>>>  B
>>>  ['A']

Stack은 동적 배열과 더블리 링크드 리스트 둘 다로 구현할 수 있다.

• 스택 추상자료형 구현 바로가기

	동적배열	링크드 리스트
맨 뒤 삭제	분할 상환 O(1)	O(1)
맨 뒤 삽입	분할 상환 O(1)	O(1)
맨 앞 접근	O(1)	O(1)