스택 구현

스택

스택 설명

구현

스택은 자료를 push, pop 하는 자료구조이기 때문에 수정이 자주 일어난다고 판단하여 링크드리스트를 활용한 방식으로 구현해 보았다.

노드

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

스택 구현에 사용할 노드이다.
노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있다.

push

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head

스택에 값을 push 하는 메서드이다.
구현 방식은

1. value를 사용해 새로운 값을 담은 Node를 생성한다.
2. 생성한 노드의 다음 노드를 현재 head로 지정한다.
3. 생성한 노드를 head로 변경한다.

위와 같은 방법을 사용해 이후 pop, peak 메서드를 구현할 때 head에서 바로 값을 가져올 수 있도록 하였고 링크드리스트 방식으로 구현하여 이후 pop 동작시 이점을 가져갈 수 있도록 했다.

pop

    def pop(self):
        if self.is_empty():
            return "stack is empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head

스택의 head 값을 추출하는 메서드이다.

1. if문을 사용해 스택이 비어있는지 확인한다.
2. 현재 head를 다른 변수에 저장한다.
3. head를 현재 head의 다음 노드로 변경한다. (linked list의 특징으로 인하여 자연적으로 삭제)
4. 2에서 저장한 변수를 리턴한다.

1번의 is_empty 메서드는 스택이 비어있는지 확인하는 것으로 스택이 비어있으면 return이 불가능하기 때문에 스택이 비어있다는 정보를 리턴하도록 했다.
링크드리스트의 특징을 활용해 head를 변경하여 기존 head 노드의 데이터를 링크드리스트에서 제거하고 리턴하도록 구현했다.

peak

    def peak(self):
        if self.is_empty():
            return "stack is empty"
        return self.head.data

스택의 head의 데이터를 조회하는 메서드이다.

1. if문을 사용해 스택이 비어있는지 확인한다.
2. head 노드의 데이터를 리턴한다.

pop과 마찬가지로 스택이 비어있는 경우는 return이 불가능하므로 처리했으며 pop의 로직에서 현재 head 노드를 삭제하는 로직만 제외하면 가능했기 때문에 간단히 구현할 수 있었다.

is_empty

    def is_empty(self):
        return self.head is None

스택이 비어있는지 확인하는 메서드이다.

표현 그대로 스택에 값이 존재하는지 boolean 값을 리턴하는 로직이며 pop, peak 메서드에서 이를 필요로 하여 구현했다.