Stack 스택 자료구조

해당 게시물은 신찬수 교수님의 자료구조 강의를 듣고 이해한 내용을 바탕으로 작성하였습니다. 문제가 발생한다면 바로 삭제하겠습니다. 링크

Stack 자료구조

어떤 자료구조도 마찬가지지만 값을 삽입 삭제 탐색의 세 가지 기능은 항상 제공할 수 있도록 만들어야 함.

삽입 연산

push연산의 경우는 파이썬 리스트의 append() 사용. 이 경우 상수 시간 O(1)을 가짐

삭제 연산

pop 연산의 경우 파이썬 리스트의 pop() 사용하며 상수 시간 O(1)을 가짐

탐색 연산

top 연산 : 스택의 가장 위에 있는 값을 알고 싶을 때 사용 이 경우 파이썬과 C언어의 큰 차이점 중 하나인 리스트의 마이너스 - 인덱스를 사용함. 따라서 상수 시간 O(1)을 가짐

추가 구현한 코드

스택이 아예 비어있는지를 try except 구문을 이용하여 확인하지만 기본적으로 not 연산자로 리스트가 비었는지 여부를 판단할 수 있기 때문에 isEmpty() 메소드를 추가 작성

구현 코드

class Stack:
	def __init__(self):
		self.items = []  # 데이터 저장을 위한 리스트 준비
	
	def push(self, val):
		self.items.append(val)
	
	def pop(self):
		try:	# pop할 아이템이 없는지 확인하고 예외처리
			return self.items.pop()
		except IndexError:
			print("Stack is empty")
	
	def top(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")

	def isEmpty(self):
		return not self.items
	
	def __len__(self): # len() 호출하면 stack의 item 수 반환
		return len(self.items)