[Python 알고리즘] 스택(Stack)

안녕하세요!

언젠간 하겠지~하던 알고리즘 이제 시작했습니다

요즘 부트캠프도 하고 개인 앱 제작도 마무리 단계이고 배워야 할 것들은 계속 보이고 바쁜 하루네요

 

스택은 한쪽은 열려있고 한쪽은 막혀있는 구조로

데이터를 추가/삭제 할 때 후입선출(Last-In First-Out) 한다는 특징이 있습니다

 

스위프트에서도 여러 함수가 동작할 때 스택 형식으로 메모리에 쌓여서 동작한다던지

네비게이션 컨트롤러에서 화면 전환으로 Push 할 때에도

스택 형식으로 쌓이고 돌아올 때 Pop 한다는 내용이 기억나네요

 

아래는 파이썬 문법으로 구현한 스택(Stack) 자료형 입니다

# 배열 스택(리스트 만들기)
class ArrayStack:
    # 초기화
    def __init__(self, capacity):
        # 배열의 크기를 정할 변수
        self.capacity = capacity
        # 배열의 크기 설정
        self.array = [None] * capacity
        # 배열의 최상단()
        self.top = -1

    # 비어있는지 확인
    def isEmpty(self):
        return self.top == -1
    
    # 가득 차있는지 확인
    def isFull(self):
        return self.top == self.capacity - 1
    
    # 최상단에 값 추가
    def push(self, item):
        # 가득 차있지 않다면
        if not self.isFull():
            self.top += 1
            self.array[self.top] = item
        else: pass

    # 최상단에 값 제거 + 리턴
    def pop(self):
        # 비어있는지 않다면
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top + 1]
        else: pass

    # 최상단 값 리턴 (제거 x)
    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else: pass

    # 몇개의 값이 들어있는지 리턴
    def size(self): return self.top + 1

 

파이썬 문법이 익숙치 않아 왜 이렇게 self가 많은지 아직 어색하지만 내용은 다 이해가 갑니다!

혹시 top이 왜 -1인지 헷갈리시는 분들이 계신다면 배열은 0부터 시작한다는 점을 기억하시고

아래처럼 그림을 그려보시면 바로 이해가 갈거에요

 

6개의 데이터가 들어있다면 Top은 배열의 (6-1)번째,

그러니까 array[5] == 6번째 인거죠.