Stack

Stack

스택은 Last-in,First-out(LIFO) 원리에 따라 삽입과 제거되는 객체들의 모임입니다. 스택은 pushing과 poppping 기능적 연산을 통헤 삽입과 제거를 합니다.

실제 사용되는 사례

인터넷 웹브라우저는 가장 최근에 방문한 주소를 저장합니다. 유저가 새로운 사이트에 방문할 때마다, 스택에 주소가 "PUSHED" 됩니다. 브라우저는 유저가 "back" 버튼을 누를때 가장 최근 방문한 주소가 "POP" 됩니다.

Stack 추상적 데이터 타입

스택은 모든 자료구조에서 가장 단순하지만 중요합니다. 스택은 추상 자료타입(ADT)입니다.

추상적 자료 타입(Abstract _Data Type)이란?

추상적 자료형은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명시에 놓은 것입니다.

stack.push(e):       stack 인스턴스의 top에 e를 추가합니다.
stack.pop():          stack 인스턴스의 top 요소를 삭제 하고 반환합니다. 만약 스택이 비었을 경우 에러가 발생합니다.
stack.top():           스택의 top 요소를 제거하지않고 반환합니다.
stack.is_empty():  스택이 비었다면 True 그렇지 않으면 False를 반환합니다.
len(stack):            스택내에 요소들의 개수를 반환합니다.

Simple Array-Based Stack implementation

파이선 자료형인 list에 요소를 저장하면서 스택을 구현합니다. 리스트 클래스는 이미 마지막에 요소를 삽입하는 append 메서드가 있고 마지막 요소를 제거하는 pop 메서드가 있습니다. 따라서 쉽게 스택을 구현할 수 있습니다.

"""파이썬의 리스트 클래스를 사용하여 LIFO 스택 구현"""

class ArrayStack:
    def __init__(self):
        """ 빈 스택을 생성합니다. """
        self._data=[]

    def __len__(self):
        """ 스택내에 요소의 개수를 반환합니다. """
        return len(self._data)

    def is_empty(self):
        """ 스택이 비었을 경우 True를 반환합니다. """
        return len(self._data) == 0

    def push(self, e):
        """ 스택의 top에 e 요소를 추가합니다. """
        self._data.append(e)
    def top(self):
        """
        스택의 가장 위의 요소를 제거하지않고 반환합니다.
        스택이 비었는데 메서드를 호출할 경우 에러가 발생하도록 구현합니다.
        """

        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data[-1]

    def pop(self):
        """
        스택의 가장 위의 요소를 제거하고 제거된 요소를 반환합니다.
        스택이 비었는데 메서드를 호출할 경우 에러가 발생하도록 구현합니다.
        """

        if self.is_empty():
            raise Empty('Stack is empty')
        return self._data.pop()