[Data Structure] Linear - (5) Stack

---

---

스택(Stack)

 후입선출(Last-in First-Out, LIFO)특징을 가진 자료구조다. 즉, 가장 최근에 들어온 자료가 가장 먼저 나가도록 되어 있다.

스택 구조

---

커스텀 스택구현

 파이썬으로 스택을 구현하기 위해선 우선 두 가지 고려할 점이 있다.

 

1. List?
   1. 일반적인 경우 그냥 파이썬 리스트로 스택을 사용해도 된다.
   2. 하지만 값이 계속해서 삽입되는 경우 파이썬 리스트는 동적 배열이므로 공간을 자동적으로 확장하면서 O(n)의 시간이 걸릴 때가 가끔 있다. 참고
   3. 공간이 작을 땐 문제가 안되겠지만 무지막지하게 큰 경우 시간이 오래 걸릴 수도 있다.
2. Singly Linked List?
   1. 어차피 후입선출, 즉 맨끝에서만 자료가 삽입되고 나갈 수 있도록 구현하면 된다
   2. 각 자료들이 레퍼런스로만 연결되어 있기 때문에 공간의 확장이 필요없다.

 

결론: 싱글리 링크드 리스트로 커스텀 스택을 구현

 

 

from typing import Optional, Iterable


class Node:
    """싱글리 링크드 리스트 노드"""

    def __init__(self, data) -> None:
        self.data = data
        self.next = None

    def __repr__(self) -> str:
        return str(self.data)


class CustomStack:
    """커스텀 스택 클래스"""

    def __init__(self, arr: Optional[Iterable] = None) -> None:
        self.top = None

        # arr가 있을 경우
        if arr:
            for i in arr:
                self.push(i)

    def push(self, __x) -> None:
        """추가 메소드"""

        new_node = Node(__x)

        if self.top:
            new_node.next = self.top

        self.top = new_node

    def pop(self):
        """삭제 메소드"""

        if not self.size:
            raise IndexError("스택이 비어 있습니다.")

        __x = self.top.data
        self.top = self.top.next
        return __x

    def __repr__(self) -> str:
        list_for_return = []

        iterator = self.top

        while iterator:
            list_for_return.append(str(iterator.data))
            iterator = iterator.next

        return "stack([" + ", ".join(list_for_return) + "])"

 

---

코드 리뷰

 

노드 클래스

 

class Node:
    """싱글리 링크드 리스트 노드"""

    def __init__(self, data) -> None:
        self.data = data
        self.next = None

    def __repr__(self) -> str:
        return str(self.data)

 

 기본적인 싱글리 링크드 리스트 노드를 만들어 주었다. 

 

 

커스텀 스택 클래스

 

class CustomStack:
    """커스텀 스택 클래스"""

    def __init__(self, arr: Optional[Iterable] = None) -> None:
        self.top = None

        # arr가 있을 경우
        if arr:
            for i in arr:
                self.push(i)

 

 커스텀 스택은 최상단 노드의 위치를 레퍼런스하는 top 속성을 가진다. 자료들이 들어올 때는 top이 해당 자료를 가리키고, 자료들이 나갈 때는 top이 가리키고 있는 자료의 next가 다시 top이 되면 스택을 구현할 수 있다.

 

 또한 CustomStack 인스턴스를 생성할 때 파라미터로 이터러블한 값을 넘겨줬을 때도 스택이 올바르게 작동할 수 있도록 if arr ~ for i in arr 문을 만들어 주었다.

 

 

 

Push 메소드

 

def push(self, __x) -> None:
    """추가 메소드"""

    new_node = Node(__x)

    if self.top:
        new_node.next = self.top

    self.top = new_node

 

 두가지 상태를 고려해야 한다. (1) 스택이 비어있을 경우 (2) 스택이 비어 있지 않은 경우.

스택이 비어 있을 경우 새로운 노드를 top이 가리키도록만 하면 된다. 하지만 스택이 비어 있지 않은 경우에는 새로운 노드가 이전에 top이 가리키고 있었던 노드를 가리키도록 해, pop시에 다시 이전 노드를 찾을 수 있도록 해야 한다.

 

 

 

Pop 메소드

 

def pop(self):
    """삭제 메소드"""

    if not self.size:
        raise IndexError("스택이 비어 있습니다.")

    __x = self.top.data
    self.top = self.top.next
    return __x

 

 Pop을 할 때는 top이 다시 이전 노드를 가리키도록 하면서 최상단 노드를 리턴하도록 한다.

 

 

---

테스트

 

custom_stack = CustomStack([1, 2, 3, 4, 5])

print(custom_stack)

custom_stack.push(100)

print(custom_stack)

custom_stack.pop()
custom_stack.pop()
custom_stack.pop()

print(custom_stack)

stack([5, 4, 3, 2, 1])
stack([100, 5, 4, 3, 2, 1])
stack([3, 2, 1])

 

 다음과 같이 CustomStack 인스턴스를 생성하면서 [1, 2, 3, 4, 5]를 넘겨주면 다음과 같이 왼쪽으로 자라나는 형태로 스택이 만들어진다. 이는 CustomStack의 __repr__ 매직 메소드에서 self.top에서부터 iterator를 이용해 next를 찾아나가는 형태이기 때문이다.

 

push와 pop 메소드가 둘다 올바르게 작동하는 것을 알 수 있다.

 

 

 

커스텀 Stack vs 파이썬 List vs 파이썬 Deque

 

import timeit

setup_custom = """
from __main__ import CustomStack
custom_stack = CustomStack()
"""

setup_python_stack = """
python_stack = list()
"""

setup_python_deque = """
from collections import deque
python_deque = deque()
"""

custom_stack_push = """
for i in range(10000):
    custom_stack.push(i)
"""

python_stack_push = """
for i in range(10000):
    python_stack.append(i)
"""

python_deque_push = """
for i in range(10000):
    python_deque.append(i)
"""

time_custom = timeit.timeit(stmt=custom_stack_push,
                            setup=setup_custom, number=1000)
time_python = timeit.timeit(stmt=python_stack_push,
                            setup=setup_python_stack, number=1000)
time_deque = timeit.timeit(stmt=python_deque_push,
                           setup=setup_python_deque, number=1000)
                           

print(f"Custom Stack append time: {time_custom}")
print(f"Python Stack append time: {time_python}")
print(f"Python Deque append time: {time_deque}")

Custom Stack append time: 2.4409448
Python Stack append time: 0.4501054
Python Deque append time: 0.3462576999999998

 

 C/C++과의 시간 차이는 어쩔 수 없는 것 같다. 시간이 크게 상관 없는 경우에는 파이썬 List를, 더 빨라야 하는 경우에는 Deque를 이용해서 스택을 쓰도록 하자.