📚 스택(Stack)
📚 스택(Stack)이란
한쪽으로만 자료를 넣고 뺄 수 있는 후입선출(LIFO: Last-In First-Out) 구조를 가진 자료구조.
데이터를 차곡차곡 쌓아 올린 형태이며, LIFO 구조이기 때문에 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
📚 스택의 사용 사례
- 웹 브라우저 방문 기록(뒤로 가기)
- 실행 취소(undo)
- 역순 문자열 만들기
- 후위 표기법 계산
📚 스택 기본 연산
- push(): 스택에 원소 추가
- pop(): 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환
- peek(): 스택 가장 위에 있는 원소를 반환(삭제는 하지 않음)
- isEmpty(): 스택이 비어있으면 True, 비어있지 않다면 False를 반환
- size(): 스택의 원소 개수 반환
📚 파이썬으로 스택 구현하기
파이썬은 스택 자료구조는 따로 제공하지 않고, 리스트(list)를 통해 구현할 수 있다.
S.append() 리스트 맨 끝에 원소를 추가한다. 시간복잡도는 O(1)이다.
S.pop(i) 리스트의 i번째 원소를 삭제한다. S.pop(-1)은 맨 앞에 있는 원소를 삭제한다. 시간복잡도는 마찬가지로 O(1)이다.
클래스로 스택 구현
class Stack:
# 리스트를 이용한 스택 구현
def __init__(self):
self.top = []
# 구현 함수
# 스택에 원소 삽입
def push(self, item):
self.top.append(item)
# 스택 가장 위에 있는 원소를 삭제하고 반환
def pop(self):
if not self.isEmpty():
return self.top.pop(-1)
else:
print("Stack underflow")
exit()
# 스택 가장 위에 있는 원소를 반환
def peek(self):
if not self.isEmpty():
return self.top[-1]
else:
print("underflow")
exit()
# 스택이 비어있는 지를 bool 값으로 반환
def isEmpty(self) -> bool:
return len(self.top)==0
# 스택의 크기를 int 값으로 반환
def size(self) -> int:
return len(self.top)참고 사이트
https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack
