[자료구조] Stack의 자료구조 파이썬으로 구현하기

Stack

스택은 마지막에 삽입한 데이터를 가장 먼저 사용합니다.
나중에 들어간 데이터가 젤 먼저 나오는 방식입니다
들어오고 나오는 방식 거꾸로 됩니다.

 

# 김수지
class Stack: #스택 클래스를 정의한다.
    def __init__(self):
        self.data = [] # 데이터를 리스트로 정의해준다.
        
    def push(self, value):
        self.data.append(value) # append() 맨 마지막에 값을 추가한다.
        
    def pop(self):
        #return self.data
        last_value = self.data.pop() # pop()은 리스트의 맨 마지막 요소를 리턴하고 그 요소는 삭제
        return last_value
stack1 = Stack()
stack2 = Stack()

stack1.push(1)
print(stack1.data)

stack2.push(2)
stack1.push(3)
print(stack1.data)

init 함수

데이터를 리스트로 정의합니다.

push 함수

맨 마지막에 값을 추가합니다.

pop 함수

맨 마지막의 마지막 리스트를 리턴합니다.

즉, 맨 마지막에 줄 선사람이 먼저 서비스를 받게 되는 방식입니다.

 

시간복잡도

• 삭제 삽입 : O(1) : 삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문

스택의 공간복잡도 _O(n) 데이터갯수만큼