스택(Stack) in Python

목차

머리말

들어가기 전에

선형 자료구조(linear data structure) 중에서 스택(stack)에 대해 알아 보자.

스택(stack)을 사전에서 찾아보면 무더기, 더미라는 뜻의 영단어이다. 아래의 돌탑이 대표적인 스택이다.

 

돌탑은 대표적인 스택이다.

 

스택 Stack

정의

A stack is an ordered list in which insertions and deletions are made at one end, called the top.
스택(stack)은 상단이라 불리는 한쪽 끝에서 삽입과 삭제가 이루어지는 선형적 자료구조이다.

Data Structures & Algorithms - Stacks & Queues

 

특징

스택은 밑에서 점차 위로 쌓아올리는 선형적 자료구조이다. 위의 돌탑에서 알 수 있듯이, 쌓아올리든 제거를 하든 맨위부터 할 수 있는 형태이다.

후입선출(LIFO)

• 앞의 정의에서 "한쪽 끝에서 삽입과 삭제가 이루어지는" 특징을 후입선출(LIFO, Last-in First-out)이라 한다.
• 데이터를 추가하는 것을 Push, 자료를 꺼내는 것을 Pop이라 한다.
• Push/Pop은 모두 가장 최근의 위치에서 각각 삽입/삭제가 이루어진다.

스택의 대표적인 기능인 Push와 Pop

Stack - Wikipedia

 

코드 in Python

파이썬의 기본 자료형인 리스트(list)를 활용하면 간단히 구현할 수 있다.

• 리스트에 자체적인 append(), pop() 함수가 있어서 push와 pop을 바로 구현할 수 있다.
• 스택의 크기를 구하는 size()는 파이썬의 함수 len()을 활용한다.
• 스택의 가장 윗부분을 구하는 top()은 배열의 가장 뒤 인덱스를 반환하도록 [-1]를 이용한다.
• 스택이 비어 있는지 확인하는 is_empty()는 not을 활용하면 쉽게 불 자료형으로 반환할 수 있다.
• 클래스를 쉽게 활용하도록 매직 메서드 __len__과 __str__를 이용한다.

정의

# 스택 클래스 정의
class Stack():
    def __init__(self):
        self.items = [] # 초깃값은 파이썬의 빈 리스트로 할당

    def push(self, item):
        self.items.append(item) # push는 파이썬 리스트의 기본 메서드인 append를 활용하여 추가

    def pop(self):
        self.items.pop() # pop은 파이썬 리스트의 기본 메서드인 pop를 활용하여 삭제

    def size(self):
        return len(self.items) # size는 스택의 크기를 반환

    def top(self):
        if self.is_empty(): # top은 스택에서 가장 오른쪽 인덱스에 위치한 값을 반환
            return "stack is empty."
        return self.items[-1]

    def is_empty(self):
        return not self.items  # 스택에 대한 정보를 not을 활용하여 부울 자료형으로 반환. 비어 있을 경우 True, 그렇지 않으면 False

    def __len__(self):
        return len(self.items) # 매직 메서드를 활용하여 클래스에 'len() 함수' 적용 가능

    def __str__(self):
        return f"{self.items}" # 매직 메서드를 활용하여 결괏값을 문자열 형태로 출력

테스트 코드

# 테스트 코드
if __name__ == "__main__":
    # 1. stack 할당
    print("------ #1. initialize stack ------")
    stack = Stack()
    print(stack)  # []
    print(f"len(stack) : {len(stack)}")  # len(stack) : 0

    # is_empty() and top()
    print(f"is stack empty? : {stack.is_empty()}")  # is stack empty? : True
    # print(f"top : {stack.top()}") # Exception: stack is empty.
    print()

    # 2. push()
    print("------ #2. push stack ------")
    stack.push(1)
    print(f"push 1 : {stack}")  # push 1 : [1]
    stack.push(8)
    print(f"push 8 : {stack}")  # push 8 : [1, 8]
    stack.push(4)
    print(f"push 4 : {stack}")  # push 4 : [1, 8, 4]
    print(f"len(stack) : {len(stack)}")  # len(stack) : 3

    # is_empty() and top()
    print(f"is stack empty? : {stack.is_empty()}")  # is stack empty? : False
    print(f"top : {stack.top()}")  # top : 4
    print()

    # 3. pop()
    print("------ #3. pop stack ------")
    stack.pop()
    print(f"pop : {stack}")  # pop : [1, 8]
    print(f"len(stack) : {len(stack)}")  # len(stack) : 2
    stack.pop()
    print(f"pop : {stack}")  # pop : [1]
    stack.pop()
    print(f"pop : {stack}")  # pop : []
    print(f"is stack empty? : {stack.is_empty()}")  # is stack empty? : True

    # empty인 상태인데 pop할 경우 오류 출력
    # stack.pop()
    # print(f"pop : {stack}")
    # print(f"is stack empty? : {stack.is_empty()}") # Exception: stack is empty.

테스트 결과

------ #1. initialize stack ------
[]
len(stack) : 0
is stack empty? : True

------ #2. push stack ------
push 1 : [1]
push 8 : [1, 8]
push 4 : [1, 8, 4]
len(stack) : 3
is stack empty? : False
top : 4

------ #3. pop stack ------
pop : [1, 8]
len(stack) : 2
pop : [1]
pop : []
is stack empty? : True