[자료 구조] Stack

Stack

---

• LIFO(Last In First Out)  : 값을 저장할 때는 가장 최근에 저장된 값 다음에 저장되며, 값이 나갈 때는 가장 최근에 저장된 값이 먼저 나간다
• 데이터는 리스트에 저장 (append, pop 함수가 제공되므로)
•  연산은 push, pop, top, isEmpty, size(len) 등 5 가지 연산 제공

 

▶ Stack class 생성

class Stack:
	def __init__(self):  # 생성자 함수
		self.items = []  # 데이터 저장을 위한 리스트 준비
        
	def push(self, val):  #삽입
		self.items.append(val)
        
	def pop(self):  #삭제
		try: # pop할 아이템이 있으면
			return self.items.pop()  # pop 수행 
		except IndexError: # pop할 아이템이 없으면 indexError 발생
			print("Stack is empty")
            
	def top(self): #stack의 가장 상위에 있는 값 반환
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
            
	def __len__(self): # len()로 호출하면 stack의 item 수 반환
		return len(self.items)
        
	def isEmpty(self):  # stack에 값이 없으면 True, 있으면 False 반환
		return len(self) == 0

 

▶ Stack 객체 생성

S = Stack()  # 객체 생성

S.push(1) # 값 삽입
S.push(3)
S.push(-1)

print(S.pop()) # 값 삭제 -1  
print(S.top()) # 최상위 값 확인 3  
print(len(S)) # stack의 길이 2
print(S.isEmpty()) # stack이 비었는지 유무 False

 

▶ 수행시간

 

O(1) 상수시간  : push(), pop(), top(), len(), isEmpty()