📚 스택 (Stack) 파이썬으로 구현하기!

스택에 대해서 알아보고, 파이썬으로 스택을 구현해보기

 

스택이란?

• 후입선출(Last In First Out, LIFO), 나중에 넣은게 가장 먼저 나옴
• 한쪽이 뚫려있는 통을 생각하면 편하다
• 사용처 : 어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우, 의존관계 있는 경우, 재귀함수를 이용해 구현도 가능 DFS
• 예시 : 하드웨어 스택, 콜 스택

 

스택의 추상 자료형 (ADT)

객체 (characters)

• arr : T[], 데이터가 저장되는 배열, 리스트
• top : int, 가장 나중에 저장된 데이터의 위치

 

연산 (operations)

• push() : 위에 새 요소를 넣음
• pop() : 맨 위의 요소를 뺌
• top() : 맨 위의 요소를 출력
• isempty() : 스택이 비어있는지 확인
• isfull() : 스택이 차있는지 확인
• size() : 스택의 요소 갯수를 반환

 

스택의 구현

간단하게 구현

#파이썬 리스트는 기본적으로 stack으로 쓰기 좋다
class Stack:
    def __init__(self): 
        self.arr=[]
        
    # 위의 값을 뽑는다.   
    def pop(self):
        if self.isempty(): return None
        else: return self.arr.pop()
    
    # 값을 하나 넣는다.
    def push(self, element):
        return self.arr.append(element)
    
    # 가장 위의 값을 읽는다.
    def top(self):
        if self.isempty(): return None
        else: return self.arr[-1]
    
    # 비어있는지 확인한다.
    def isempty(self):
        return len(self.arr) == 0
    
    # 스택의 요소 갯수를 반환
    def size(self):
        return len(self.arr)

파이썬의 리스트를 이용하여 간단하게 구현

 

배열로 구현

파이썬에는 배열이 없기 때문에 생략

 

연결 리스트로 구현

작성 예정