[자료구조] Stack

• Linked List를 이용해서 stack 구현

class Node:
    def __init__(self, data, next: "Node" = None): 
        self.data = data
        self.next = next

string "Node"로 type hint를 사용한 이유는? https://wschoi.tistory.com/36 참고

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

stack = Stack()

• self.last 속성을 이용해 stack의 push, pop () 메소드 구현

 

 

Push 메소드

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

    def push(self, data):
        new_node = Node(data) # here
        new_node.next = self.last
        self.last = new_node

stack = Stack()
stack.push(1)

new_node = Node(1)

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last # here
        self.last = new_node

stack = Stack()
stack.push(1)

new_node.next = self.last

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node # here

stack = Stack()
stack.push(1)

self.last = new_node

• last 포인터가 새로운 node를 가리킴

push() 메소드를 한번 더 호출하면?

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

    def push(self, data):
        new_node = Node(data) # here
        new_node.next = self.last
        self.last = new_node

stack = Stack()
stack.push(1)
stack.push(2) # push 한번 더 호출

new_node = Node(2)

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last # here
        self.last = new_node

stack = Stack()
stack.push(1)
stack.push(2)

new_node.next = self.last

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node # here

stack = Stack()
stack.push(1)
stack.push(2)

self.last = new_node

• last 포인터를 새로 추가된 노드를 가리키도록 업데이트

 

Pop 메소드

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node

    def pop(self):
        data = self.last.data # here
        self.last = self.last.next
        return data

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # here

data = self.last.data

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.last
        self.last = new_node

    def pop(self):
        data = self.last.data
        self.last = self.last.next # here
        return data

stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 2

self.last = self.last.next

• last 포인터를 업데이트
• 마지막으로 data를 반환