[Python] 파이썬 연결 리스트를 이용한 스택 ADT 구현하기

연결 리스트를 이용한 스택 ADT 구현

코드

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

헷갈린 부분

처음에 Stack 클래스가 만들어지면 생성자가 last를 None로 초기화하므로 처음 호출되는 push 함수는 Node(item, self.last)에서 self.last에 None이 들어간다. 그리고 self.last에 생성된 Node 객체를 가리키게 한다

다음 push 함수에서 Node(item, self.last)의 self.last가 이전의 push 함수의 Node 객체이고, 현재의 push 함수의 Node 객체에서의 next가 전 push 함수에서 생성됐던 Node 객체를 가리키게 된다. 마지막으로 self.last를 다시 지금 만들어진 Node 객체로 바꿔준다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]