[알고리즘] Stack

1. Stack이란?

스택은 '쌓는다'라는 이름의 어원처럼 먼저 입력한 데이터를 제일 나중에 꺼내는 FILO(Last In, First Out)의 구조를 가진 자료구조를 의미합니다. 일상 생활에서도 많이 확인할 수도 있는 형태인데, 차례대로 쌓인 접시라던지 혹은 곽티슈에 담긴 휴지라던지 확인할 수 있습니다. 혹은 프로그램 내부에서도 이런 구조를 확인할 수 있는데 함수를 호출하게 되면 프로그램을 호출된 순서에 따라서 차곡차곡 저장하고, 함수가 종료될때마다 가장 나중에 호출된 함수부터 차례대로 해제됩니다.

위 구조로 잘 이해가 가지 않는다면 아래와 같은 그림을 이해하면 더 쉽게 이해할 수 있습니다.. 예를 들어 어떤 데이터를 1, 2, 3 순서대로 넣었다면 가장 나중에 넣었던 3부터 차례대로 2, 1 순서로 꺼냅니다.

2. Stack의 연산

스택의 주된 연산은 크게 다음과 같습니다.

• Push : 데이터를 스택의 맨 위에 삽입합니다.
• Pop : 최근에 푸시한 데이터를 빼내고, 그 값을 반환합니다.
• Peek(or Top) : 스택의 맨 위의 데이터를 제거하지 않고 확인만 합니다.
• isEmpty() : 스택에 데이터가 들어있지 않은지 확인합니다.
• isFull() : 스택에 들어있는 데이터 개수가 최대치인지 확인합니다.

일반적인 스택의 구조는 아래와 같이 구성되어 있고 위에서 설명한 연산 중 Push와 Pop에 대해서 설명하면 다음과 같습니다.

• 데이터 3을 추가하기 위해 push(3)을 호출합니다.
  • 먼저 isFull()을 수행해 스택 내부에 공간이 있는지 확인합니다.
  • 공간이 있다면 top을 1 증가 후, top이 가리키는 위치에 3을 추가합니다.
• 데이터를 삭제하기 위해 pop()을 호출합니다.
  • 먼저 isEmpty()를 수행해 내부적으로 데이터가 없는지 확인합니다.
  • 데이터가 있다면 top을 1만큼 감소시킨 후 top이 가리켰었던 값을 반환합니다.

여기서 top은 가장 최근에 추가한 데이터의 위치를 참조하는 변수로 이해하면 될 것 같습니다.

파이썬에서는 stack의 경우 별도로 구현하지 않고 동적 배열인 list를 활용하지만, 다른 언어에서도 활용할 수 있기 때문에 기본적인 로직은 코드로 구현해보았습니다.

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

 

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Peek:", stack.peek())  # 출력: Peek: 3
print("Pop:", stack.pop())    # 출력: Pop: 3
print("Peek after pop:", stack.peek())  # 출력: Peek after pop: 2
print("Size:", stack.size())  # 출력: Size: 2

---

자료구조 중에서는 가장 쉬운 형태이지만 문제를 보고 떠올리는게 굉장히 어려운 자료구조입니다. 하지만 적응하고 나면 활용도가 많고, DFS에서도 응용가능하니 차근차근 문제를 기반으로 이해합시다.