10. 스택

---

 

 

1. 스택 (Stack)

스택은 데이터를 임시 저장할 때 사용하는 대표적인 자료구조이다.

'마른 풀을 쌓은 더미' 또는 '겹겹이 쌓아놓은 책'의 모습을 연상하면 된다.

후입 선출(LIFO: Last In First Out) 방식에 따라 데이터를 입출력한다.

• 푸시(Push): 스택에 데이터를 넣음
• 팝(Pop): 스택에서 데이터를 꺼냄
• 꼭대기(Top): 스택에 데이터를 푸시하고 팝 하는 윗부분
• 바닥(Bottom): 스택의 맨 아랫부분

 

---

 

2. FixedStack 클래스 구현하기

이제 스택 자료구조를 직접 코드로 구현해보자.

여기서는 크기가 고정된 스택 클래스를 구현한다.

from typing import Any

class FixedStack :
    class Empty(Exception) :
        pass
        
    class Full(Exception) :
        pass

    def __init__(self, capacity: int = 256) -> None :
        self.stk = [None] * capacity
        self.capacity = capacity
        self.ptr = 0

    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 :
        if (self.is_full()) :
            raise FixedSack.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]

    def peek(self) -> Any :
        if (self.is_empty()) :
            raise FixedStack.Empty
            
        return self.stk[self.ptr-1]
        
    def clear(self) -> None :
        self.ptr = 0

    def find(self, value: Any) -> Any :
        for i in range(self.ptr-1, -1, -1) :
            if (self.stk[i] == value) :
                return i
            
        return -1

    def count(self, value: Any) -> bool :
        c = 0
        
        for i in range(self.ptr) :
            if (self.stk[i] == value) :
                c += 1
            
        return c
    
    def __contains__(self, value: Any) -> bool :
        return self.count(value)
        
    def dump(self) -> None :
        if (self.is_empty()) :
            print('Stack is Empty')
        else :
            print(self.stk[:self.ptr])

 

---

 

---

수고하셨습니다!

---