[자료구조 이론] Stack에 대하여

스택(Stack이란?)

 

스택은 데이터를 임시저장할때 사용하는 자료구조이다. 기본적으로 후입선출(LIFO,Last In First Out)방식이다.

스택의 동작은 두가지가 있다

• 푸시(Push) : 데이터를 넣는 작업이다.
• 팝(Pop) : 데이터를 꺼내는 작업이다.

그리고 푸시, 팝을 하는 윗부분을 top, 아랫부분을 bottom이라고 한다.

스택 구현하기

스택을 구현해 보자. 우선 기본적으로 Fixed-Stack으로 구현해 보자. 스택을 구현하는데 있어 기본적으로 아래 세가지가 필요로 하다

1. 스택배열 : stk - 데이터를 저장하는 본체이다
2. 스택크기 : capactiy - 스택의 최대 크기를 나타내는 정수이다
3. 스택포인터 : ptr - 스택에 쌓여있는 데이터 개수를 나타내는 정수값이다. 비어있으면 0, 차있으면 capacity와 동일한 값이된다.

from typing import Any

class FixedStack(object):

    def __init__(self, capacity: int = 256) -> None:
        self.stk = [None] * capacity # stack 
        self.capacity = capacity # stack capacity
        self.ptr = 0 # stack pointer
    
    class Full(Exception):
        def __init__(self) -> None:
            self.msg = "Stack is Full"
        
        def __str__(self) -> str:
            return self.msg

    class Empty(Exception):
        def __init__(self) -> None:
            self.msg = "Stack is Empty"
        
        def __str__(self) -> str:
            return self.msg

    # return stack data count
    def __len__(self) -> int:
        return self.ptr
    
    # return if stack is empty 
    def isEmpty(self) -> bool:
        return self.ptr <= 0
    
    #return if stack is full
    def isFull(self) -> bool:
        return self.ptr >= self.capacity
    
    #Push value into stack
    def push(self,value) -> None:
        if self.isFull():
            raise FixedStack.Full
        else:
            self.stk[self.ptr] = value
            self.ptr += 1
    
    #Pop value from stack
    def pop(self) -> Any:
        if self.isEmpty():
            raise FixedStack.Empty
        else:
            self.ptr-=1
            return self.stk[self.ptr]
    
    #Peek top value of stack
    def peek(self) -> Any:
        if self.isEmpty():
            raise FixedStack.Empty
        else:
            return self.stk[self.ptr - 1]
    
    #clear stack
    def clear(self) -> None:
        self.ptr = 0
    
    #find value from stack : start from top
    def find(self,value: Any) -> Any:
        for i in range(self.ptr - 1, -1, -1):
            if self.stk[i] == value:
                return i
        return -1
    
    #Count value 
    def count(self, value: Any) -> bool:
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c

    #See if stack contains value from parameter
    def __contains__(self,value: Any) -> bool:
        return self.count(value)
    
    #print all of elements in stack
    def dump(self) -> None:
        if self.isEmpty():
            raise FixedStack.Empty
        else:
            print(self.stk[:self.ptr])

if __name__ == "__main__":
    stk = FixedStack()
    for i in range(10):
        stk.push(i)
    print(len(stk))
    print(11 in stk)
    print(stk.pop())
    print(stk.peek())
    print(stk.dump())
    print(stk.clear())
    print(stk.dump()) # 예외처리

Double Underscore함수 알아보기

__len __함수와 __contains __ 함수와 같이 언더스코어 2개가 붙은 함수는 특별한 의미가 있는 함수이다.이렇게 언더스코어 2개가 붙은 함수를 주로 매직메소드라고 부른다

• __len __ : 클래스에 이 메소드를 정의하면 클래스형 인스턴스를 __len __에 전달할 수 있다. 예를들어 len(obj)과 같이 말이다
• __contains __ : 클래스에 이 메소드를 정의하면, 클래스형 인스턴스에 대해 멤버십 판단 연산자인 in을 적용할 수 있다.

Collections.deque로 구현해보기

파이썬에는 리스트, 집합, 딕셔너리, 튜플등 자료구조도 있지만, collections모듈에서 namedtuple, deque, chainmap, counter,ordereddict등 다양한 컨테이너를 제공한다. 이중 deque모듈을 사용하면 스택을 간단히 구혀할 수 있다. 기본적으로 deque는 양쪽에서 원소 추가 삭제를 하는 deque를 모티브한 컨테이너이다.

일반적인 list로 구현을 하지 않고, deque를 사용하는 이유는 push,pop연산이 빈번한 알고리즘에 있어서 리스트에 비해 월등한 속도를 제공하기 때문이다.(하지만 사실상 스택에서는 큰 시간복잡도 차이를 보이지 않는다. 이 collections.deque를 사용하기 적절한 곳은 Queue를 구현할때 가장 좋다.) 다만 collections.deque는 내부적으로 linked list자료구조로 이루어져있다. 그렇기 때문에, 중간에 데이터를 넣거나 하는 동작에 있어서는 매우 비효율적인 선택지가 되니, 주의하자.

기본적으로스택 구현시 필요로 하는 주요 속성들을 알아보자

• maxlen : 속성, deque의 최대 크기를 나타내는 속성, 읽기만 가능하며, 크기제한이 없으며 없으면 None이다
• append(x) : deque의 오른쪽에 원소 추가
• appendleft(x) : deque의 왼쪽에 원소 추가
• clear() : deque의 모든 원소 삭제, 크기를 0으로한다
• copy() : deque의 얕은복사
• count(x) : deque안에 있는 x원소 개수
• insert(i,x) : x를 i위치에 삽입한다. maxlen을 초과한 경우
• pop() : 오른쪽에 있는 원소 1개 삭제, 그 원소 반환한다. 원소가 하나도 없는 경우 IndexError반환
• popleft() : 왼쪽에 있는 원소 1개 삭제, 원소가 없는경우에는 IndexError를 반환
• remove(value) : value의 첫번째항목을 삭제한다. 원소가 없는경우 ValueError반환

from collections import deque
from typing import Any

class Stack(object):
    def __init__(self,maxlen: int = 256) -> None:
        self.capacity = maxlen
        self.stk = deque([],self.capacity)

    def __len__(self) -> int:
        return len(self.stk)
    
    def isEmpty(self) -> bool:
        # list는 빈 리스트인 경우 false를 반환한다.
        return not self.stk
    
    def isFull(self) -> bool:
        return len(self.stk) == self.capacity
    
    def push(self, value: Any) -> None:
        self.stk.append(value)
    
    def pop(self) -> Any:
        return self.stk.pop()
    
    def peek(self) -> Any:
        return self.stk[-1]
    
    def clear(self) -> None:
        self.stk.clear()
    
    def find(self,value: Any) -> Any:
        try:
            return self.stk.index(value)
        except ValueError:
            return -1
    
    def count(self,value) -> int:
        return self.stk.count(value)

    def __contains__(self,value: Any) -> bool:
        return self.count(value)
    
    def dump(self) -> int:
        print(list(self.stk))

if __name__ == "__main__":
    s = Stack()
    for i in range(10):
        s.push(i)
    s.dump()
    print(s.pop())
    print(s.pop())
    print(s.peek())
    print(len(s))
    print(3 in s)
    print(s.find(3))