스택
- last-in, first-out 제일 나중에 들어간 값이 제일 먼저 나온다.
- list의 pop과 append로 스택의 pop과 push를 구현할 수 있다. 시간 복잡도는 O(1)
- 참조 지역성(한번 참조된 곳은 다시 참조될 확률이 높다)을 활용할 수 있다.
- 데이터를 탐색하기가 어렵다.
- 콜스택(재귀 함수), 문자열 역순 출력, 연산자 후위표기법 등에 사용 스택이 많이 사용된다.
리스트 구현
stack = []
stack.append(1)
# 1추가
stack.append(2)
# 2추가
stack.pop()
# 리스트 제일 끝에 있는 값 반환 후 삭제
# 2 반환 후 삭제
print(stack)
# stack = [1]
클래스로 구현
class Stack:
def __init__(self):
self.stack = []
def push(self, data):
self.stack.append(data)
def pop(self):
if self.is_empty():
return -1
return self.stack.pop()
def peek(self):
return self.stack[-1]
def is_empty(self):
if len(self.stack) == 0:
return True
return False