[자료구조] 스택 (Stack)

본 포스트는 필자가 학습하고 작성한 글이기 때문에 틀린 내용이 있을 수 있습니다.

 

스택 (Stack) 개요

 데이터를 저장하는 기본적인 자료 구조 중 하나로, 선입후출(LIFO: Last In, First Out)의 특성을 가진다.

즉, 마지막에 추가된 항목이 가장 먼저 제거된다.

장점

• 구현이 간단하다.
• 데이터의 추가와 삭제의 시간 복잡도가 O(1)이다.

단점

• 스택의 크기가 고정된 경우, 스택 오버플로우(스택이 가득 참)나 스택 언더플로우(스택이 비어 있음)가 발생할 수 있다.
• 스택의 중간 데이터에 접근하기 어렵다.

주요 연산

• push : 스택의 맨 위에 새로운 항목을 추가합니다.
• pop : 스택의 맨 위 항목을 제거하고 반환합니다.
• peek or top : 스택의 맨 위 항목을 확인하되 제거하진 않습니다.
• is_empty : 스택이 비어있으면 True, 아니라면 False를 반환합니다.
• get_size : 스택의 크기(항목의 수)를 반환합니다.

시간 복잡도

• push : O(1)
• pop : O(1)
• peek : O(1)

공간 복잡도

• 모든 경우 : O(n)

---

구현

스택의 구현은 Array(python에서의 list)나 Linked List로 할 수 있다.

 

리스트 기반 스택

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """top에 item 추가"""
        self.items.append(item)

    def pop(self):
        """top item을 제거하고 리턴"""
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        """top item을 제거하지 않고 리턴"""
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        """stack이 비어있는지 확인"""
        return len(self.items) == 0

    def get_size(self):
        """스택의 길이를 리턴"""
        return len(self.items)

 

연결 리스트 기반 스택

class StackNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class StackUsingLinkedList:
    def __init__(self):
        self.top = None
        self.no = None

    def push(self, data):
        """top에 item 추가"""
        new_node = StackNode(data)
        if self.top is None:
            self.top = new_node
            return
        new_node.next = self.top
        self.top = new_node
        self.no += 1

    def pop(self):
        """top item을 제거하고 리턴"""
        if self.is_empty():
            return None
        popped_node = self.top
        self.top = self.top.next
        popped_node.next = None
        self.no -= 1
        return popped_node.data

    def peek(self):
        """top item을 제거하지 않고 리턴"""
        if self.is_empty():
            return None
        return self.top.data

    def is_empty(self):
        """stack이 비어있는지 확인"""
        return self.top is None

    def get_size(self):
        """스택의 길이를 리턴"""
        return self.no