스택과 큐 - 스택

스택(Stack)

---

스택은 데이터를 저장하는 방식 중 하나이다. LIFO(Last in First out)방식을 채용하고 있으며, 스택 포인터를 주로 사용한다. 영어로 써서 뭔가 있어보이지 사실 쉽게 말하면 맨 위에 있는 것 부터 꺼내는 것이나 마찬가지다.

어떤 한 상자에 물건들이 가득 찼다고 하자. 종류와 관계없이 가장 단순하면서도 빠르게 뭔가를 꺼낼려 하면 어떻게 하면 되는가? 당연히 맨 위에 있는 것 부터 꺼내면 된다. 스택도 이와 같은 방식이다. 따라서 다른 배열 방식보다 비교적 단순한 방식이다.

스택은 스택 포인터가 있다. 쉽게 말하면 물건이 담긴 상자를 보는 “우리의 눈”이라고 생각하면 된다. 맨 위에서 상자에 물건을 넣으면 그 아래에 있는 물건은 자연스레 보이지 않고 방금 넣은 물건만 볼 수 있다.

데이터를 추가하면 포인터 역시 이에 따라 움직이며 방금 넣은 데이터를 가리킨다. 스택은 특이하게 add 대신 push 메서드를 사용하는데, 우리가 상자 맨 위에 물건을 살포시 놓는 것과 비슷한 개념이다. 이 경우, 데이터는 스택의 맨 위에 위치한다.

def push(self, value : Any) -> None:
    if self.is_full():
        raise FixedStack.Full
    self.stk[self.ptr] = value
    self.ptr+=1

데이터를 검색할 때는 포인터가 위아래로 움직이며 데이터를 검색한다.

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

또한, 원소를 내보낼 때는 pop()을 통해 데이터를 마치 상자에서 꺼내듯, 맨 위에 있는 데이터를 “꺼낸다.” 상자에 꺼낼 원소가 없으면 스택이 비었다고 오류를 출력한다.

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

위에서 말했듯 스택은 우리가 맨 위에서 물건이 담긴 상자를 보는 것(peek)과 같다고 했다. 마찬가지로 스택 역시 맨 위에서 볼 수 있는데, 이 경우 스택은 맨 위에 있는 원소를 return한다.

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