Stack

• stack(스택)은 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리구조

Stack의 특징

• LIFO(Last In First Out): 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 구조
• FILO(First In Last Out): 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 구조
• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• Python에서는 재귀함수 또는 List로 구현
• 시간복잡도: O(1)
• e.g. 책상 위에 차곡차곡 쌓이는 책, 싱크대 위에 쌓이는 접시

Stack의 주요 기능

• Push: Data의 입력
• Pop: Data의 출력
  (다만 pop은 읽어들임과 동시에 stack에서 삭제한다)

Stack의 장점

• 구조가 단순해서, 구현이 쉽다
• 데이저 저장/읽기 속도가 빠르다

Stack의 단점

• 데이터 최대 갯수를 미리 정해야 한다
  (파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능)
• 저장 공간의 낭비가 발생할 수 있음
  (미리 최대 갯수 만큼 저장 공간을 확보해야 함)

When to use Stack

• 프로그램에서 함수 호출 기록을 stack으로 저장한다.
• web browser 내역 혹은 내역인데 최신 내역이 먼저 나와야 하는 경우

---

Stack 구현 with Python

재귀함수를 이용한 Stack 예제

# 재귀 함수
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data) 
        
# 재귀 함수 실행
recursive(4)
4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4

list를 사용한 stack 예제

구현 method

• isEmpty: 스택이 비어 있는지 확인
• push: 스택 맨 끝(맨 위)에 항목을 삽입
• pop: 스택 맨 끝 항목을 반환하는 동시에 스택에서 제거
• peek: 스택 맨 끝 항목을 조회
• size: 스택 크기를 조회

class Stack():
    def __init__(self):  # 생성자 초기화
        self.data = list()  # 스택의 구조를 빈 리스트로 초기화

    def isEmpty(self):  # 스택에 데이터 있는지 확인 func
        if len(self.data) == 0:  # 스택에 데이터가 없다면
            return True  # True 리턴
        else:
            return False  # (스택 데이터가 있다면) False 리턴

    def push(self, value):  # 데이터 삽입 func
        self.data.append(value)  # 스택에 데이터값을 넣음

    def pop(self):  # 데이터 삭제 func
        if len(self.data) == 0:  # 스택에 데이터가 없다면
            print('Stack is Empty', -1)  # 스택이 비었음, -1 리턴
        else:  # 스택에 데이터가 있다면
            data = self.data[-1]  # 마지막 데이터를 삭제될 data 변수에 저장
            del self.data[-1]  # 마지막 데이터 삭제
            return data  # 삭제될 data 변수 리턴

    def peek(self):  # 스택의 마지막 데이터 확인 func
        if self.data:  # 스택에 데이터가 있다면,
            return self.data[-1]  # 스택의 마지막 데이터 리턴
        else:  # 스택에 데이터가 없다면
            print('Stack is Empty', -1)  # 스택이 비었음, -1 리턴

    def size(self):  # 데이터 갯수 확인 func
        return len(self.data)  # 스택의 데이터 길이 리턴

    def __repr__(self):  # 생성자 문자열 리턴 초기화
        return repr(self.data)  # 리턴하는 데이터는 문자열로 리턴

# 초기 test code
if __name__ == "__main__":
    stack = Stack()
    print('Stack is Empty?:', stack.isEmpty())
    print('Insert in Stack 0 to 10')
    for i in range(11):
        stack.push(i)
    print('Stack :', stack)
    print('Stack peek:', stack.peek())
    for _ in range(5):
        print('Stack pop:', stack.pop())
    print('Stack :', stack)