[Python] 스택(Stack) 구현

1. 개발 환경 : Python 3.8.10, WSL2, VSCODE

 

 

2. 스택(Stack) 이란?

스택은 데이터가 쌓여져 있는 자료 구조를 의미합니다. 쌓여진 물건을 꺼낼 때 맨 위의 물건부터 꺼내게 됩니다.

마찬가지로 스택에서는 가장 마지막에 입력된 데이터가 먼저 출력되는 LIFO(Last In First Out) 정책을 따릅니다.

데이터를 제한적으로 접근할 수 있습니다.

 

스택 구조 (출처: http://blog.naver.com/coolten/140057845842)

 

2.1. 스택의 장점

• 구조가 단순하고, 구현이 쉽습니다.
• 데이터 저장/읽기 속도가 빠릅니다.

2.2. 스택의 단점

• 데이터 최대 갯수를 미리 정해야합니다.
• 파이썬의 경우는 재귀함수 1000번까지만 호출 가능합니다.
• 예상 최대 갯수만큼 공간을 확보하여야 하므로 저장공간의 낭비가 발생됩니다.

 

 

3. python으로 스택 클래스 구현하기

• push : 데이터 입력
• pop : 데이터 출력
• is_empty : 스택이 비어있는지 유무 판단
• is_full : 스택이 가득차있는지 유무 판단
• 가득차거나 비어있는 스택이 push, pop 명령을 받았을 때 예외처리 (class Empty, class Full)

from typing import Any, Sequence

class FixedStack:
    class Empty(Exception):
        pass
    
    class Full(Exception):
        pass
        
    def __init__(self, capacity:int = 256) -> None:	# 스택 용량 256으로 설정
        """초기화"""
        self.stk = [None] * capacity # 스택 본체
        self.capacity = capacity
        self.ptr = 0	# index number
        
    def __len__(self) -> int:
        """스택에 쌓여있는 데이터 개수를 반환"""
        return self.ptr
    
    def is_empty(self) -> bool:
        """스택이 비어있는가?"""
        return self.ptr <= 0
    
    def is_full(self) -> bool:
        """스택이 가득차있는가?"""
        return self.ptr >= self.capacity

    def push(self, value:Any) -> None:
        """스택에 value를 푸시"""
        if self.is_full():
            raise FixedStack.Full
        self.stk[self.ptr] = value
        self.ptr += 1
    
    def pop(self) -> Any:
        """스택에서 데이터를 팝"""
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]


if __name__ == '__main__':
    stack = FixedStack()
    print(f'스택이 비어있나요? {stack.is_empty()}')
    for i in range(256):
        stack.push(i)
    
    print(f'스택이 가득차있나요? {stack.is_full()}')
    
    for _ in range(5):
        print(stack.pop())
    
    print(f'스택의 길이는 몇인가요? {stack.__len__()}')

 

결과

스택이 비어있나요? True
스택이 가득차있나요? True
255
254
253
252
251
스택의 길이는 몇인가요? 251

 

[출처] : https://www.youtube.com/watch?v=n0wWDd64WwA&t=7936s​