자료구조 - 스택(stack) 공부하기

자료구조 - 스택(stack) 공부하기

구조 알기

스택은 일종의 자료구조로, 데이터에 대한 접근을 제한적으로 허용합니다. 이 구조의 핵심은 '후입선출(LIFO, Last In First Out)' 원칙을 따르는 것입니다. 이 원칙은 가장 마지막에 쌓은 데이터를 가장 먼저 꺼낼 수 있다는 것을 의미합니다. 스택은 마치 책을 바닥에서부터 쌓고, 책을 꺼낼 때는 가장 위에 있는 것부터 꺼내야 하는 것과 유사합니다.

 

스택과 대조되는 자료구조로 큐(Queue)가 있습니다. 큐는 '선입선출(FIFO, First In First Out)' 정책을 따르며, 이는 줄을 서서 차례대로 처리되는 것과 비슷합니다. 즉, 큐는 처음에 들어온 데이터가 가장 먼저 나가는 구조입니다.

 

관련 용어 알기

작업명	설명	반환 값
Push	스택 맨 위에 새로운 데이터를 삽입합니다.	삽입된 데이터
Pop	스택 맨 위에 있는 데이터를 제거하고 그 값을 반환합니다.	제거되고 반환된 데이터
Peek/Top	스택 맨 위의 데이터를 조회합니다. 데이터는 제거되지 않습니다.	스택 맨 위의 데이터
IsEmpty	스택이 비어 있는지 확인합니다. 스택에 데이터가 없으면 true, 있으면 false를 반환합니다.	스택이 비어 있으면 true, 데이터가 있으면 false

 

활용 예시

웹 브라우저 방문 기록의 뒤로 가기 기능

 

장단점

구조가 단순해서 구현은 쉽지만, 스택을 쌓기위한 공간을 미리 확보해야하는 단점도 있음

(파이썬에서 재귀함수를 호출하면 위와 같은 단점을 고려하여 호출 수를 1000번으로 고정해 두었습니다. 만약 호출 수 제약을 변경하고 싶다면 아래 링크를 참고 하세요)

파이썬에서 재귀 함수의 호출 제한 이해하기

 

 

파이썬으로 구현하기

파이썬에서 스택 자료구조를 이해하고 활용하는 방법은 다양하지만, 기본적으로 리스트를 사용해 push와 pop 메서드를 구현할 수 있습니다. 리스트의 append 메서드는 스택의 push 기능을 수행하며, pop 메서드는 스택에서 가장 최근에 추가된 요소를 제거하는 기능을 그대로 제공합니다. 여기서 push는 요소를 스택에 추가하는 동작을, pop은 추가된 요소를 스택에서 제거하는 동작을 의미합니다. 파이썬의 리스트는 동적 배열로 구현되어 있어 스택의 기능을 효율적으로 지원합니다. 하지만 스택의 작동 원리를 보다 깊이 이해하기 위해서는 직접 이 메서드들을 구현해 보는 것이 좋습니다. 아래에 간단한 스택 구현 예제를 제시합니다.

 

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

    def push(self, item):
        """스택의 맨 끝에 요소를 추가합니다."""
        self.items.append(item)

    def pop(self):
        """스택의 맨 끝에서 요소를 제거하고 그 요소를 반환합니다."""
        list_data = self.items[-1]
        del self.items[-1]
        return list_data
        
 # 스택 인스턴스 생성
my_stack = Stack()

# 스택에 요소 추가
my_stack.push('apple')
my_stack.push('banana')
my_stack.push('cherry')


# 요소 제거 및 반환
popped_item = my_stack.pop()

# 함수적용 내용 확인
print("제거된 요소: ", popped_item)
print("리스트 내용 확인: ", my_stack.items)