스택이란?
- 스택은 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
- 입구와 출구가 동일한 형태인 선형구조
스택 ADT
- 데이터: 선입후출(FILO)의 접근 방법을 유지하는 항목들의 모음
- 연산
- Stack(): 비어 있는 새로운 스택을 만듦
- isEmpty(): 스택이 비어있는지를 검사
- push(e): 항목 e를 스택의 맨 위에 추가
- pop(): 스택의 맨 위에 있는 항목을 꺼내 반환
- peek(): 스택의 맨 위에 있는 항목을 삭제하지 않고 반환
- size(): 스택의 모든 항목들의 개수를 반환
- clear(): 스택을 공백상태로 만듦
스택의 구현 방법
- 배열 구조를 이용
- 파이썬에서 리스트를 사용 → 중간에 있는 항목을 꺼내지 않고 한쪽으로만 삽입, 삭제
- 항목의 삽입/삭제 위치 → 후단(항목들의 이동없이 바로 추가하면 되기 때문, O(1))
스택의 시간 복잡도
- push(e) 연산: O(1)
- pop() 연산: O(1)
스택 구현
class Stack:
def __init__(self): # 생성자
self.top = [] # 멤버 변수 선언 및 초기화
def isEmpty(self): # 공백상태면 True, 아니면 False 반환
return self.size() == 0
def size(self): # 스택의 크기 반환
return len(self.top)
def clear(self): # 스택을 공백상태로 초기화
self.top = []
def push(self, item): # 맨 위에 item을 추가
self.top.append(item)
def pop(self): # 맨 위의 항목을 꺼내 반환
if not self.isEmpty():
return self.top.pop(-1)
def peek(self): # 맨 위의 항목을 삭제하지 않고 반환
if not self.isEmpty():
return self.top[-1]
def __str__(self): # 맨 위의 항목부터 출력
return str(self.top[::-1])
