스택(Stack)의 개념 및 구현

자료구조 스택(Stack) 이해하기

스택(Stack)은 컴퓨터 과학에서 중요한 자료구조 중 하나입니다.
스택은 여러 가지 상황에서 유용하게 사용되며, 특히 재귀 알고리즘이나 연산자 우선순위 처리, 컴파일러에서 함수 호출 관리 등에 많이 활용됩니다. 이 포스팅에서는 스택의 개념, 동작 방식, 그리고 사용 시나리오에 대해 알아보겠습니다.

---

1. 스택이란?

스택(Stack)은 후입선출(Last In First Out, LIFO) 방식으로 동작하는 자료구조입니다. 이는 마지막에 추가된 데이터가 가장 먼저 삭제된다는 의미입니다. 스택은 물리적인 구조로 설명하자면, 접시를 쌓는 것과 비슷합니다. 가장 위에 있는 접시를 먼저 꺼내게 되며, 아래에 있는 접시는 그 다음 순서로 꺼내게 됩니다.

스택의 주요 특징:

• 후입선출(LIFO): 마지막에 들어간 데이터가 먼저 나옴.
• 삽입(Push): 데이터를 스택의 맨 위에 삽입.
• 삭제(Pop): 데이터를 스택의 맨 위에서 삭제.
• 탐색(Peek): 삭제하지 않고 맨 위의 데이터를 확인.

---

2. 스택의 동작 원리

스택은 두 가지 기본 연산으로 동작합니다: Push(삽입)와 Pop(삭제).

Push 연산:

Push 연산은 새로운 데이터를 스택의 맨 위에 추가하는 작업입니다. 데이터를 스택에 차곡차곡 쌓아 올리는 방식으로 이루어집니다.

Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(20);
stack.Push(30);

위의 코드에서는 스택에 차례대로 10, 20, 30이 들어가며, 이 때 30이 가장 위에 있게 됩니다.

Pop 연산:

Pop 연산은 스택의 맨 위에 있는 데이터를 제거하는 작업입니다. 후입선출의 특성상, 가장 마지막에 추가된 30이 먼저 제거됩니다.

int topValue = stack.Pop();  // topValue = 30

Pop 연산 후에는 30이 제거되고, 스택의 맨 위에는 20이 위치하게 됩니다.

Peek 연산:

Peek 연산은 스택에서 데이터를 제거하지 않고, 현재 스택의 맨 위에 있는 데이터를 확인하는 작업입니다.

int topValue = stack.Peek();  // topValue = 20

---

3. 스택의 사용 예시

스택은 후입선출 방식이 필요할 때 매우 유용하게 사용됩니다. 다음은 스택이 자주 사용되는 예시들입니다.

1) 함수 호출 스택

프로그래밍에서 함수 호출 시 함수가 스택 구조로 관리됩니다.
함수가 호출될 때마다 스택에 쌓이고, 함수가 종료될 때마다 스택에서 제거됩니다. 이는 재귀 함수 호출을 처리하는 데 특히 유용합니다.

2) 괄호 검사

스택은 수식이나 코드를 분석할 때 괄호가 제대로 열리고 닫혔는지 검사하는 데 자주 사용됩니다.
열린 괄호는 스택에 삽입되고, 닫힌 괄호가 나타나면 스택에서 열린 괄호를 제거하는 방식으로 검사합니다.

bool IsValid(string s) {
    Stack<char> stack = new Stack<char>();
    foreach (char c in s) {
        if (c == '(') {
            stack.Push(c);
        } else if (c == ')') {
            if (stack.Count == 0 || stack.Pop() != '(') {
                return false;
            }
        }
    }
    return stack.Count == 0;
}

3) 역순 처리

스택은 데이터를 역순으로 처리하는 데 사용될 수 있습니다.
예를 들어 문자열을 역순으로 출력하거나, 수식을 후위 표기법으로 변환하는 등의 작업에서 스택이 유용합니다.

---

4. 스택 구현 방법

C#에서 스택은 Stack<T> 클래스를 사용하여 쉽게 구현할 수 있습니다.
Stack<T>는 제네릭 타입으로, 다양한 데이터 타입을 지원하며, Push, Pop, Peek 등의 기본 연산을 제공합니다.

Stack<int> numberStack = new Stack<int>();

// Push 연산
numberStack.Push(1);
numberStack.Push(2);
numberStack.Push(3);

// Pop 연산
Console.WriteLine(numberStack.Pop());  // 출력: 3

// Peek 연산
Console.WriteLine(numberStack.Peek());  // 출력: 2

이외에도 스택은 배열이나 리스트를 사용하여 직접 구현할 수도 있습니다.

---

5. 스택과 큐의 차이점

스택과 비슷한 자료구조로 큐(Queue)가 있습니다.
스택은 후입선출(LIFO) 방식으로 동작하지만, 큐는 선입선출(First In First Out, FIFO) 방식으로 동작합니다.
즉, 스택에서는 나중에 들어간 데이터가 먼저 나오고, 큐에서는 먼저 들어간 데이터가 먼저 나오는 차이가 있습니다.

---

6. 스택의 장단점

장점:

• 데이터가 쌓이고 제거되는 구조가 명확하고 간단합니다.
• 특정 문제, 특히 재귀나 순서 역전과 관련된 문제에서 매우 효율적입니다.

단점:

• 스택은 후입선출 방식이므로, 데이터의 중간에서 접근하거나 제거하는 것이 불가능합니다.
• 데이터가 많아지면 스택 오버플로(Stack Overflow)가 발생할 수 있습니다.

---

스택은 매우 중요한 자료구조로, 다양한 알고리즘 및 시스템 구현에 사용됩니다.
후입선출 방식의 특징 덕분에 함수 호출, 괄호 검증, 데이터 역순 처리 등 다양한 상황에서 유용하게 활용됩니다.
스택의 기본적인 동작 원리와 사용 방법을 이해하면, 더 복잡한 자료구조와 알고리즘을 다루는 데도 큰 도움이 됩니다.