스택(Stack): 효율적인 후입선출 데이터 관리

 

스택(Stack)은 후입선출(LIFO, Last-In-First-Out) 방식으로 데이터를 관리하는 자료구조입니다. 마지막에 삽입된 데이터가 가장 먼저 삭제되는 특성을 가지고 있으며, 간단한 구조임에도 불구하고 다양한 문제를 효율적으로 해결할 수 있습니다.

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

 

스택은 프로그래밍 언어의 함수 호출 관리, 역순 데이터 처리, 브라우저의 뒤로 가기 기능 등 실무에서 매우 다양한 곳에 활용됩니다. 이 글에서는 스택의 기본 개념부터 실제 구현, 응용 예제까지 폭넓게 다루어 보겠습니다.

 

---

 

스택의 개념

 

스택은 한 쪽 끝에서만 데이터의 삽입(push)과 삭제(pop)가 이루어지는 선형 자료구조입니다. 이로 인해 데이터의 접근이 제한적이지만, 특정 상황에서는 매우 효율적으로 동작합니다.

 

기본 연산

• Push: 스택의 가장 위에 데이터를 추가합니다.
• Pop: 스택의 가장 위에 있는 데이터를 제거하고 반환합니다.
• Peek: 스택의 가장 위에 있는 데이터를 확인합니다.
• isEmpty: 스택이 비어있는지 확인합니다.
• size: 스택에 저장된 데이터의 개수를 반환합니다.

 

스택의 특징

• 시간 복잡도:
  • Push, Pop, Peek: O(1)
• 공간 복잡도: O(n), n은 스택에 저장된 데이터의 개수

 

---

 

스택의 실제 사용 사례

 

함수 호출 관리

프로그래밍 언어는 함수 호출 시 콜 스택(Call Stack)을 사용하여 현재 실행 중인 함수의 상태를 저장합니다. 함수가 호출될 때마다 스택에 새로운 프레임이 추가되고, 함수가 종료되면 해당 프레임이 제거됩니다.

 

 

역순 데이터 처리

스택은 데이터를 역순으로 처리하는 데 유용합니다. 예를 들어, 문자열을 뒤집거나, 깊이 우선 탐색(DFS) 알고리즘에서 사용됩니다.

 

 

브라우저의 뒤로 가기 기능

웹 브라우저는 사용자가 방문한 페이지의 기록을 스택에 저장합니다. '뒤로 가기' 버튼을 누르면 스택에서 가장 최근에 방문한 페이지를 제거하고 이전 페이지로 이동합니다.

 

수식 계산

 

수식의 괄호 검증 및 후위 표기법(Postfix) 계산 등에서 스택이 사용됩니다. 이는 복잡한 수식을 간단하게 처리할 수 있게 해 줍니다.

 

 

---

 

스택 구현하기

 

스택은 여러 프로그래밍 언어에서 쉽게 구현할 수 있습니다. 아래는 Python과 JavaScript로 구현한 스택 클래스의 예제입니다.

 

Python으로 스택 구현하기

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

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

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

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

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

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

# 스택 사용 예시
if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print(stack.pop())  # 출력: 3
    print(stack.peek()) # 출력: 2
    print(stack.size()) # 출력: 2

 

JavaScript으로 스택 구현하기

 

class Stack {
    constructor() {
        this.items = [];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    push(item) {
        this.items.push(item);
    }

    pop() {
        if (!this.isEmpty()) {
            return this.items.pop();
        } else {
            throw new Error("pop from empty stack");
        }
    }

    peek() {
        if (!this.isEmpty()) {
            return this.items[this.items.length - 1];
        } else {
            throw new Error("peek from empty stack");
        }
    }

    size() {
        return this.items.length;
    }
}

// 스택 사용 예시
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());  // 출력: 3
console.log(stack.peek()); // 출력: 2
console.log(stack.size()); // 출력: 2

---

스택의 응용 

 

괄호 검사기

스택을 사용하여 문자열 내의 괄호가 올바르게 닫혔는지 검사할 수 있습니다. 예를 들어, {[()()]}는 올바른 괄호이지만, {[(])}는 올바르지 않습니다.

def is_balanced(expression):
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    for char in expression:
        if char in pairs.values():
            stack.push(char)
        elif char in pairs.keys():
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    return stack.is_empty()

# 사용 예시
expr1 = "{[()()]}"
expr2 = "{[(])}"
print(is_balanced(expr1))  # 출력: True
print(is_balanced(expr2))  # 출력: False

 

후위 표기법 계산기

 

후위 표기법(Postfix Notation)은 연산자가 피연산자 뒤에 오는 표기법으로, 스택을 이용하여 간단히 계산할 수 있습니다.

def evaluate_postfix(expression):
    stack = Stack()
    for char in expression:
        if char.isdigit():
            stack.push(int(char))
        else:
            right = stack.pop()
            left = stack.pop()
            if char == '+':
                stack.push(left + right)
            elif char == '-':
                stack.push(left - right)
            elif char == '*':
                stack.push(left * right)
            elif char == '/':
                stack.push(left / right)
    return stack.pop()

# 사용 예시
expr = "231*+9-"
print(evaluate_postfix(expr))  # 출력: -4

 

 

---

 

스택의 장단점

 

장점

• 구현이 간단하다: 스택은 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있습니다.
• 특정 문제에 최적화: 후입선출 방식이 필요한 문제에 적합합니다.
• 메모리 효율성: 필요할 때만 데이터를 저장하고 제거하기 때문에 메모리 사용이 효율적입니다.

 

단점

• 임의 접근이 불가능하다: 스택의 특정 위치에 있는 데이터에 직접 접근할 수 없습니다.
• 제한된 사용처: 모든 문제에 적용할 수 있는 것은 아니며, 후입선출 방식이 적합한 경우에만 유용합니다.

 

 

최적의 사용 상황

• 역순 처리: 데이터의 역순 처리가 필요할 때 스택을 사용하면 효율적입니다.
• 함수 호출 관리: 프로그래밍 언어의 내부에서 함수 호출을 관리할 때 스택을 활용합니다.
• 알고리즘 구현: 깊이 우선 탐색(DFS)과 같은 알고리즘에서 스택을 사용합니다.

 

성능 최적화

• 적절한 자료구조 선택: 스택을 구현할 때 배열이나 연결 리스트 중 상황에 맞는 자료구조를 선택하여 성능을 최적화할 수 있습니다.
• 메모리 관리: 불필요한 데이터가 스택에 쌓이지 않도록 관리하여 메모리 사용을 최적화합니다.

 

디버깅

• 콜 스택 분석: 디버깅 시 콜 스택을 분석하여 함수 호출의 흐름을 추적할 수 있습니다.
• 스택 오버플로우 방지: 재귀 호출 시 스택의 깊이를 관리하여 스택 오버플로우를 방지합니다.

 

---

 

스택(Stack)은 단순하면서도 강력한 자료구조로, 다양한 실무 문제를 효과적으로 해결할 수 있습니다. 이번 포스트에서는 스택의 기본 개념부터 구현, 응용 예제까지 폭넓게 다루었으며, 다음 포스트에서는 큐(Queue)와 우선순위 큐(Priority Queue)에 대해 심도 있게 알아보겠습니다!