스택(Stack)

스택 자료 구조 (Stack Data Structure)

스택은 컴퓨터 과학에서 가장 기본적이고 중요한 자료 구조 중 하나이다. 스택은 데이터를 LIFO(Last In, First Out) 방식으로 저장하고 관리한다. 이는 마지막에 삽입된 데이터가 가장 먼저 제거된다는 것을 의미한다. 스택은 일상 생활에서도 쉽게 찾을 수 있다. 예를 들어, 접시를 쌓을 때 가장 위에 있는 접시가 가장 먼저 사용되는 방식이 스택과 동일하다.

스택의 주요 연산

1. Push: 스택의 맨 위에 새로운 요소를 추가한다.
2. Pop: 스택의 맨 위에 있는 요소를 제거하고 반환한다.
3. Peek/Top: 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
4. isEmpty: 스택이 비어 있는지 확인한다.
5. Size: 스택의 크기를 반환한다.

스택의 동작

• Push 연산: 새로운 요소를 스택의 맨 위에 추가한다. 만약 스택이 배열로 구현되어 있고 이미 가득 차 있는 경우, 오버플로우(Overflow)가 발생할 수 있다.
• Pop 연산: 스택의 맨 위에 있는 요소를 제거하고 반환한다. 만약 스택이 비어 있는 경우, 언더플로우(Underflow)가 발생할 수 있다.
• Peek 연산: 스택의 맨 위에 있는 요소를 확인한다. 요소를 제거하지 않기 때문에 스택의 상태는 변하지 않는다.
• isEmpty 연산: 스택이 비어 있는지 확인한다. 스택이 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환한다.
• Size 연산: 스택의 크기를 반환한다. 즉, 스택에 있는 요소의 개수를 반환한다.

스택의 사용 예

1. 재귀 알고리즘: 재귀 호출을 사용하는 많은 알고리즘에서 내부적으로 스택을 사용하여 함수 호출을 관리한다.
2. 문자열 역순 변환: 문자열의 문자들을 역순으로 변환할 때 스택을 사용할 수 있다.
3. 괄호 검사: 수학식이나 코드에서 괄호의 짝을 검사할 때 스택을 사용할 수 있다.
4. 그래프 알고리즘: DFS(Depth-First Search)와 같은 그래프 탐색 알고리즘에서 스택을 사용할 수 있다.
5. 수식 평가: 후위 표기법(Reverse Polish Notation, RPN)을 사용하여 수식을 평가할 때 스택을 사용할 수 있다.

배열 기반 스택

• 장점: 구현이 간단하고, 인덱스를 통해 요소에 빠르게 접근할 수 있다.
• 단점: 크기가 고정되어 있어, 크기를 초과하면 오버플로우가 발생할 수 있다.

스택의 시각적 예시

Stack (Top at right):

Push 1:
| 1 |

Push 2:
| 2 |
| 1 |

Push 3:
| 3 |
| 2 |
| 1 |

Pop:
| 2 |
| 1 | (returns 3)

Peek:
| 2 | (returns 2)
| 1 |

Is Empty:
| 2 | (returns False)
| 1 |

스택의 응용

1. 역폴란드 표기법 계산기: 후위 표기법을 사용하여 수식을 계산할 때 스택을 사용하여 연산자를 관리한다.
2. 웹 브라우저의 뒤로가기 기능: 방문한 페이지를 스택에 저장하고, "뒤로" 버튼을 누르면 스택에서 페이지를 팝하여 이전 페이지로 이동한다.
3. 재귀적 문제를 반복적으로 해결: 재귀 호출을 반복문으로 대체할 때 스택을 사용하여 함수 호출을 관리한다.

스택은 이처럼 다양한 분야에서 사용되는 중요한 자료 구조이다. 스택의 개념과 주요 연산을 이해하고 구현해보면, 여러 문제를 효과적으로 해결할 수 있는 기초를 다질 수 있다.

구현 코드

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

    def push(self, value: int):
        self._values.append(value)

    def pop(self) -> int:
        if not self.isEmpty():
            return self._values.pop()
        else:
            return None

    def top(self) -> int:
        if not self.isEmpty():
            return self._values[-1]
        else:
            return None

    def isEmpty(self) -> bool:
        if len(self._values) == 0:
            return True
        else:
            return False

    def size(self) -> int:
        return len(self._values)

    def __str__(self) -> str:
        return f"Stack: {self._values}"

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)  # Stack: [1, 2, 3]
print(stack.pop())  # 3
print(stack.top())  # 2
print(stack.isEmpty())  # False
print(stack.size())  # 2

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms