Python으로 Stack 구현하기

Journey log·2022년 11월 17일
0

Python으로 객체지향 프로그래밍(oop)를 공부하고 있다. 오늘은 간단하게 자료구조 중 하나인 Stack 구현하면서 typing이나 상속 개념을 정리해보겠다. (이 글은 "타입 파이썬! 올바른 class 사용법과 객체지향 프로그래밍- 인프런" 강의를 참조하여 작성했습니다.)

1. Stack

Stack이란 쌓아 올린 형태의 자료구조를 말한다. Python에서는 연결리스트를 직접 구현할 필요없이 리스트 자료형의 append와 pop 매서드로 Stack을 사용할 수 있다. 박스를 쌓고 꺼내는 것처럼, 스택 자료구조는 가장 마지막에 들어간 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조이다.

데이터를 모두 꺼내서 더이상 pop할 수 없으면 스택이 Empty하다, 라고 표현하고 반대로 꽉 차서 더이상 스택에 push를 할 수 없는 상황은 stack overflow가 발생했다고 한다.

박스처럼 생긴 데이터 단위는 노드(Node)라고 한다. 그리고 앞으로 구현할 연결리스트(Linked List)는 노드로 이루어져있다.

노드는 item, pointer 총 2가지의 속성을 가지고 있는데, pointer가 노드와 노드를 "연결"해주는 역할을 한다. 위의 그림을 보면 Node1의 pointer가 Node2를, Node2의 poiner가 Node3를 가리키는 것을 볼 수 있다. Node라는 클래스를 정의하여 이를 구현하면,

2. Node 구현

from typing import Optional


class Node:
    def __init__(self, item, pointer: Optional["Node"] = None):
        self.item = item
        self.pointer = pointer


if __name__ == "__main__":
    # 노드 생성
    node1 = Node(item=11)
    node2 = Node(item=22)
    node3 = Node(item=33)

    # 노드 연결
    node1.pointer = node2
    node2.pointer = node3

생성자 Constructor (__init__ 함수)

  • 인스턴스가 생성된 순간 즉시 실행된다. 인스턴스가 생성되는 순간이 메모리에 올라오는 순간.
  • self는 인스턴스가 생성되었을 때, 그 인스턴스를 지칭한다.
  • item과 pointer 두가지 속성이 있는데
    - item은 노드가 담고 있는 데이터를
    - pointer는 다음 노드를 저장하거나, 아무것도 가리키지 않으면 None을 저장한다.
    • pointer의 디폴트 값은 None이다.
    • pointer의 타입은 Optional("Node"). "Node"이거나 None 이거나.
      - "Node" : 클래스를 typing하는 도중, 자기 자신을 타이핑해야한다면 큰 따옴표를 쓴다.

노드 생성, 연결

  • 총 3개의 인스턴스가 생성됨. (node1, node2, node3) 각각의 인스턴스는 서로 독립적이다.
  • node1은 node2에 연결되어 있다. 그래서 node1의 pointer에 node2를 저장한다. node3은 맨 마지막 노드이므로 pointer 값은 None이다.

typing

int_var: int = 88
str_var: str = 88 # 오류 안 남
  • Python에서 typing은 타입 힌트일뿐, 타입 체크를 하진 않는다.
  • 예를 들어, pointer를 Optional("Node")을 사용하여 타이핑했는데, 예상하지 않은 타입을 쓰더라도 실행 시 오류가 나지 않는다. (node1.pointer = 3 를 실행해도 에러가 안 뜬다.)
  • 타입 체크를 하려면
    - isinstance(88, int) 함수를 써도 되고, mypy나 pyright 라이브러리를 설치해도 타입 체크 가능


3. 연결 리스트 LinkedList 구현

구현 내용

  • head 속성 : 가장 첫 번째 노드를 head라고 하고, 노드가 없다면 None을 저장.
  • length : int 타입. 현재 노드(데이터)의 개수
  • print 했을 때 ","로 구분하여 item 출력
class LinkedList:
    def __init__(self):
        self.head: Optional[Node] = None

    @property
    def length(self) -> int:
        if self.head is None:
            return 0
        cur_node = self.head
        count: int = 1
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
            count += 1
        return count

    def __str__(self) -> str:
        # read
        result: str = ""
        if self.head is None:
            return result
        cur_node = self.head
        result += f"{cur_node.item}"  
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
            result += f", {cur_node.item}"
        return result

생성자 Constructor (__init__ 함수)

  • 첫 번째 노드인 head를 정의한다.
  • 타입은 "Node"이거나, None 이므로 Optional("Node")
  • 디폴트값은 None으로 저장

length

  • 매서드로 구현해도 되고 @property 데코레이터를 붙여서 속성으로 구현해도 됨.
    - @property : 접근(read)은 가능하지만, 업데이트는 불가. (캡슐화)
    • +=1 같은 업데이트하면 set 속성이 없다고 에러남(AttributeError: can't set attribute)
    • 만약 업데이트하려면, @length.setter 데코레이터로 setter 함수 추가해줌.
    • pop, push할 때마다 length를 업데이트하는 방법도 있겠지만 예상하지 못한 상황에서 length가 임의로 업데이트될 가능성이 있으니, length는 접근만 가능하게 하는 것이 나아보임.
  • 첫번째 노드인 self.head 가 없다면 0 출력
  • 첫번째 노드가 있다면 pointer가 None일 때까지 노드를 카운트

__str__

  • Python의 모든 클래스는 Object 클래스의 상속을 받음. (class LinkedList: == class LinkedList(Object):)
  • 이 때 Object 클래스에 이미 내장된 매서드들을 Magic Method라고 함. (dir()로 확인 가능 ex. __class__, __init__, __str__)
  • print문은 객체를 문자열화하는 함수. print를 쓸 때 __str__ 이 실행됨.
  • __str__ 함수를 새로 정의하여 덮어쓰기(Method Overriding) 가능.
  • length와 마찬가지로 첫번째 노드가 있는지 확인하고, 있다면 pointer가 None일 때까지 while 문 돌리는 식으로 구현


4. Stack 구현

구현 내용

  • LinkedList를 상속받는다.
  • push(item) : Stack 자료구조에 item을 받아 Node로 만든 다음 Stack 에 넣는다.
  • pop() : Stack 자료구조에서 마지막 Node를 제거하고, 해당 item을 반환한다. 

class Stack(LinkedList):
    def push(self, item) -> None:
        new_node: Node = Node(item=item)
        if self.head is None:
            # head가 가리키는 게 아무것도 없을 때
            self.head = new_node
            return  
        cur_node = self.head
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
        cur_node.pointer = new_node

    def pop(self):
        if self.head is None:
            raise ValueError("stack is empty")
        else:
            cur_node = self.head
        if cur_node.pointer is None:
            self.head = None
            return cur_node.item
        while cur_node.pointer.pointer is not None:  # pointer의 pointer
            cur_node = cur_node.pointer
        result = cur_node.pointer
        cur_node.pointer = None
        return result.item

push(item)

  • item 인자가 필요하고 반환하는 값은 없다. (None으로 typing)
  • 연결리스트의 가장 마지막 노드에 해당하는 pointer에 new_node를 추가한다.
  • head가 가리키는 게 없다면, 첫번째 노드인 self.head에 new_node를 정의한다.
  • head가 가리키는 노드가 있다면, 가장 마지막 노드를 찾을 때까지 while문으로 탐색한다.
  • 마지막 노드를 찾았다면 cur_node.pointer에 new_node를 연결한다.

pop()

  • 인자가 필요 없고 item 값을 반환한다.
  • 연결리스트의 가장 마지막 노드를 꺼내곰, 직전 노드의 pointer에는 None을 저장한다.
  • head가 가리키는 게 없다면, Stack이 비어있는 상황이므로 ValueError를 일으킨다.
  • head가 가리키는 게 있다면, 가장 마지막 노드를 찾을 때까지 while문으로 탐색한다.
  • cur_node.pointer.pointer가 None인 마지막 노드를 찾아 item을 반환하고, 그 직전 노드인 cur_node.pointer의 pointer는 None으로 저장한다.



5. Generic Type

위에서 item의 타입은 int, str, bool 등 여러가지가 가능하다. item의 타입은 자유롭되, 한 스택 안에 포함된 노드들은 모두 동일한 타입을 가지도록 구현할 순 없을까? 예를 들어 int와 str이 섞여있는 (1, 2, '3', 4) 와 같은 형태는 허용하지 않는 것이다. 이 때, Generic Type을 사용할 수 있다. Generic Programming은 데이터 형식에 의존하지 않고, 일반성을 유지하며 하나의 값이 여러 다른 데이터 타입들을 가질 수 있는 기술이다.

Generic Type은 위의 예시처럼 item의 타입을 고정할 때도 쓸 수 있고, item과 동일한 타입인 또 다른 변수를 정의할 때도 쓸 수 있다. typing과 마찬가지로 타입 체크가 되진 않지만 코드로 협업할 때 타입 힌트로 유용하다는 장점이 있다. 

from typing import Generic, TypeVar

T = TypeVar("T") # Generic Type

위처럼 TypeVar로 타입 변수 T를 만든다. TypeVar("T", int, str)로 타입 후보를 제한해줄 수도 있다. (mypy 0.982 버전에서는 오류가 나서 TypeVar("T")로 수정 했다.)

Node, LinkedList, Stack 클래스에 각각 item을 T로 타이핑한 코드는 다음과 같다. Node의 item을 LinkedList와 Stack에서도 쓰기 때문에 클래스를 정의할 때 아래와 같이 Generic[T]를 넣어줘야한다.

전체코드

from typing import Optional, TypeVar, Generic

T = TypeVar("T")


class Node(Generic[T]):
    def __init__(self, item: T, pointer: Optional["Node"] = None):
        self.item = item
        self.pointer = pointer


class LinkedList(Generic[T]):
    def __init__(self):
        self.head: Optional[Node[T]] = None

    @property
    def length(self) -> int:
        if self.head is None:
            return 0
        cur_node = self.head
        count: int = 1
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
            count += 1
        return count

    def __str__(self) -> str:
        result: str = ""
        if self.head is None:
            return result
        cur_node = self.head
        result += f"{cur_node.item}"
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
            result += f", {cur_node.item}"
        return result


class Stack(Generic[T], LinkedList[T]):
    def push(self, item: T) -> None:
        new_node: Node[T] = Node[T](item=item)
        if self.head is None:
            self.head = new_node
            return  
        cur_node = self.head
        while cur_node.pointer is not None:
            cur_node = cur_node.pointer
        cur_node.pointer = new_node

    def pop(self) -> T:
        if self.head is None:
            raise ValueError("stack is empty")
        else:
            cur_node = self.head
        if cur_node.pointer is None:
            self.head = None
            return cur_node.item
        while cur_node.pointer.pointer is not None:  
            cur_node = cur_node.pointer
        result = cur_node.pointer
        cur_node.pointer = None
        return result.item

length 매서드를 구현할 때 self.head를 고정하지 않고 업데이트하는 바람에 초반에 애를 먹었다. 타이핑하며 구현하는게 아직 익숙하지 않아서 (특히 Generic) 좀 더 연습해야할 것 같다.

profile
Journey log
DEEP DIVER
이전 포스트

글또 7기 회고글

다음 포스트

글또 8기를 시작하며

0개의 댓글