스택(Stack): 후입선출(LIFO) 구조의 개념과 활용

🔹 스택이란?

1. 스택(Stack)의 정의

스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙을 따르는 선형 데이터 구조로, 마지막에 추가된 요소가 가장 먼저 제거되는 구조입니다. 스택은 메모리 관리, 함수 호출, 괄호 검사, 되돌리기(Undo) 기능 등 다양한 컴퓨터 과학 분야에서 활용됩니다.

✅ 스택의 주요 특징:

• 후입선출(LIFO) 방식으로 작동
• 삽입(push)과 삭제(pop) 연산만 수행 가능
• 항상 가장 최근에 추가된 요소를 제거
• O(1)의 시간 복잡도로 연산 수행 가능

📌 스택은 후입선출 구조를 활용하는 알고리즘과 시스템에서 필수적인 데이터 구조입니다.

---

🔹 스택의 주요 연산

1. 삽입(Push) - O(1)

✅ 새로운 요소를 스택의 맨 위에 추가하는 연산

✔️ Push 연산 예제 (Python):

stack = []
stack.append(10)  # 10 추가
stack.append(20)  # 20 추가
print(stack)  # 출력: [10, 20]

📌 스택의 삽입 연산은 O(1) 시간 복잡도를 가집니다.

2. 삭제(Pop) - O(1)

✅ 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산

✔️ Pop 연산 예제 (Python):

stack = [10, 20, 30]
print(stack.pop())  # 출력: 30
print(stack)  # 출력: [10, 20]

📌 가장 최근에 추가된 요소를 제거하는 것이 스택의 핵심 개념입니다.

3. 조회(Peek) - O(1)

✅ 스택의 맨 위에 있는 요소를 제거하지 않고 조회하는 연산

✔️ Peek 연산 예제 (Python):

stack = [10, 20, 30]
print(stack[-1])  # 출력: 30 (가장 위의 요소)

📌 스택의 맨 위 요소를 확인할 수 있지만, 제거되지는 않습니다.

4. 스택이 비어있는지 확인(Is Empty) - O(1)

✅ 스택이 비어있는지 확인하는 연산

✔️ Is Empty 연산 예제 (Python):

stack = []
print(len(stack) == 0)  # 출력: True

📌 비어있는지 확인하는 것은 프로그램의 오류 방지에 유용합니다.

---

🔹 스택의 구현 방법

1. 리스트(List)를 이용한 스택 구현 (Python)

✅ Python의 리스트를 활용한 기본적인 스택 구현

✔️ 리스트 기반 스택 예제:

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

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return "Stack is empty"

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

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

s = Stack()
s.push(10)
s.push(20)
print(s.pop())  # 출력: 20
print(s.peek())  # 출력: 10

📌 Python의 리스트는 동적 배열이므로 스택으로 쉽게 활용할 수 있습니다.

2. 연결 리스트(Linked List)를 이용한 스택 구현

✅ 연결 리스트를 활용한 스택 구현은 메모리를 효율적으로 사용할 수 있음

✔️ 연결 리스트 기반 스택 예제:

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

class LinkedListStack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return "Stack is empty"
        popped_data = self.top.data
        self.top = self.top.next
        return popped_data

    def peek(self):
        return self.top.data if self.top else "Stack is empty"

    def is_empty(self):
        return self.top is None

s = LinkedListStack()
s.push(10)
s.push(20)
print(s.pop())  # 출력: 20
print(s.peek())  # 출력: 10

📌 연결 리스트를 사용하면 스택의 크기가 동적으로 조정됩니다.

---

🔹 스택의 활용 사례

1. 괄호 검사(Parenthesis Matching)

✅ 코드에서 괄호가 올바르게 닫혔는지 확인하는 데 사용

✔️ 괄호 검사 예제:

def is_balanced(expression):
    stack = []
    for char in expression:
        if char in "({[":
            stack.append(char)
        elif char in ")}]":
            if not stack:
                return False
            top = stack.pop()
            if (top == "(" and char != ")") or (top == "{" and char != "}") or (top == "[" and char != "]"):
                return False
    return len(stack) == 0

print(is_balanced("{[()]}"))  # 출력: True
print(is_balanced("{[(])}"))  # 출력: False

📌 스택을 사용하면 괄호의 짝을 쉽게 검사할 수 있습니다.

2. 함수 호출 스택(Call Stack)

✅ 재귀 함수 호출이 이루어지는 방식

✔️ 재귀 함수 호출 예제:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 출력: 120

📌 재귀 함수는 내부적으로 스택을 사용하여 호출을 관리합니다.

---

📌 결론

✅ 스택(Stack)은 후입선출(LIFO) 원칙을 따르는 선형 데이터 구조입니다.
✅ 삽입(push)과 삭제(pop)은 O(1)의 시간 복잡도를 가집니다.
✅ 괄호 검사, 함수 호출 스택, 되돌리기(Undo) 기능 등 다양한 분야에서 활용됩니다.
✅ 배열 또는 연결 리스트를 이용하여 스택을 구현할 수 있습니다.