Ferrero Rocher 2020. 7. 15. 11:44

스택

  • 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