Stack
Stack<T>는 후입선출LIFO, Last In First Out 방식으로 데이터를 관리하는 제네릭 컬렉션입니다. 가장 마지막에 추가된 요소가 가장 먼저 제거되는 특성 덕분에 재귀적 호출, 백트래킹, 알고리즘 구현 등의 특정 시나리오에서 유용하게 사용됩니다.
Stack의 기본 사용법
Stack<T>를 사용하는 방법은 매우 간단하며, 아래의 코드 예제를 통해 이해할 수 있습니다:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.Pop()); // 3
Console.WriteLine(stack.Peek()); // 2
Console.WriteLine(stack.Pop()); // 2
}
}- Push: 데이터를 스택의 맨 위에 추가합니다.
- Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
- Peek: 스택의 맨 위에 있는 데이터를 제거하지 않고 반환합니다.
위 코드에서
Push(1),Push(2),Push(3)순으로 데이터를 스택에 추가한 뒤,Pop()을 통해 가장 마지막에 추가된 값부터 제거하는 방식으로 동작합니다.
Stack의 장점과 단점
장점
- 간결한 구조:
Stack<T>는 매우 간단한 후입선출 구조로, 구현 및 사용이 직관적입니다. - 재귀적 문제 해결: 재귀 호출을 스택으로 변환함으로써 재귀를 비재귀적으로 구현할 수 있습니다. 예를 들어 트리 탐색, 깊이 우선 탐색DFS 등에 유용합니다.
- 백트래킹 알고리즘에 최적: 되돌아가기backtracking가 필요한 경우, 스택은 적합한 데이터 구조입니다.
단점
- 랜덤 접근 불가:
Stack<T>는 맨 위에 있는 요소만 접근할 수 있기 때문에, 특정 위치의 요소에 직접 접근할 수 없습니다. - 메모리 사용: 많은 데이터를 추가하고 제거할 때 내부 배열이 동적으로 확장되고 축소되므로 메모리 관리가 중요합니다.
Stack의 주요 메서드와 속성
생성자와 초기화
기본 생성자
빈 스택을 생성합니다.
Stack<int> stack = new Stack<int>();초기 용량 지정 생성자
초기 용량을 지정하여 스택을 생성합니다.
Stack<int> stack = new Stack<int>(capacity: 10);- 초기 용량 설정을 통한 최적화를 참조하세요.
컬렉션 초기화 생성자
다른 컬렉션을 사용하여 스택을 초기화합니다.
int[] numbers = { 1, 2, 3 };
Stack<int> stack = new Stack<int>(numbers);요소 추가 및 제거
Push
스택의 맨 위에 데이터를 추가합니다.
stack.Push(4);Pop
스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
int top = stack.Pop();- 스택이 비어 있는 경우
InvalidOperationException이 발생합니다.
요소 탐색
Peek
스택의 맨 위에 있는 데이터를 제거하지 않고 반환합니다.
int top = stack.Peek();- 스택이 비어 있는 경우
InvalidOperationException이 발생합니다.
기타 유용한 메서드와 속성
Count
스택에 있는 요소의 개수를 반환합니다.
int count = stack.Count;Contains
스택에 특정 요소가 있는지 확인합니다.
bool contains = stack.Contains(3);- 요소를 찾기 위해 스택 전체를 순차적으로 탐색하므로 O(n)의 시간 복잡도를 가집니다.
Clear
스택의 모든 요소를 제거합니다.
stack.Clear();ToArray
스택의 요소를 배열로 복사합니다.
var array = stack.ToArray();Stack의 활용 사례
재귀적 알고리즘 구현
Stack<T>는 재귀적 알고리즘을 비재귀적으로 구현할 때 유용합니다. 예를 들어, 깊이 우선 탐색DFS을 스택을 사용하여 구현할 수 있습니다.
using System;
using System.Collections.Generic;
class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
}
}
class Program
{
static void Main()
{
TreeNode root = new TreeNode(1)
{
Left = new TreeNode(2)
{
Left = new TreeNode(4),
Right = new TreeNode(5)
},
Right = new TreeNode(3)
};
DFS(root);
}
static void DFS(TreeNode root)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0)
{
TreeNode current = stack.Pop();
Console.WriteLine(current.Value);
if (current.Right != null)
stack.Push(current.Right);
if (current.Left != null)
stack.Push(current.Left);
}
}
}- 이 예제에서는 이진 트리를 깊이 우선으로 순회하기 위해 스택을 사용합니다. 재귀 호출 없이도 DFS를 구현할 수 있습니다.
백트래킹 문제 해결
Stack<T>는 백트래킹 문제 해결에 매우 적합합니다. 미로 탐색, 퍼즐 문제 등에서는 경로를 추적하고 되돌아가야 할 때 스택을 사용하여 경로를 저장하고 관리할 수 있습니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
char[,] maze =
{
{ 'S', '0', '1', '0' },
{ '1', '0', '1', '0' },
{ '0', '0', '0', 'E' },
{ '1', '1', '0', '1' }
};
SolveMaze(maze);
}
static void SolveMaze(char[,] maze)
{
Stack<(int row, int col)> stack = new Stack<(int, int)>();
stack.Push((0, 0));
while (stack.Count > 0)
{
var (row, col) = stack.Pop();
if (maze[row, col] == 'E')
{
Console.WriteLine("출구를 찾았습니다!");
return;
}
maze[row, col] = 'V'; // 방문 표시
// 상, 하, 좌, 우 탐색
if (row > 0 && maze[row - 1, col] == '0') stack.Push((row - 1, col));
if (row < maze.GetLength(0) - 1 && maze[row + 1, col] == '0') stack.Push((row + 1, col));
if (col > 0 && maze[row, col - 1] == '0') stack.Push((row, col - 1));
if (col < maze.GetLength(1) - 1 && maze[row, col + 1] == '0') stack.Push((row, col + 1));
}
Console.WriteLine("출구를 찾을 수 없습니다.");
}
}- 스택을 사용하여 현재 경로를 추적하고, 되돌아가기를 구현합니다.
문자열 처리
스택은 문자열의 괄호 짝 검사, 문자열 역순 변환 등에 유용하게 사용됩니다. 다음은 괄호 짝 검사 예제입니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string expression = "(1 + [2 - {3}])";
Console.WriteLine(IsBalanced(expression) ? "올바른 괄호입니다." : "잘못된 괄호입니다.");
}
static bool IsBalanced(string expression)
{
Stack<char> stack = new Stack<char>();
foreach (char ch in expression)
{
if (ch == '(' || ch == '[' || ch == '{')
{
stack.Push(ch);
}
else if (ch == ')' || ch == ']' || ch == '}')
{
if (stack.Count == 0) return false;
char open = stack.Pop();
if (!IsMatchingPair(open, ch)) return false;
}
}
return stack.Count == 0;
}
static bool IsMatchingPair(char open, char close)
{
return (open == '(' && close == ')') ||
(open == '[' && close == ']') ||
(open == '{' && close == '}');
}
}- 여는 괄호를 스택에 저장하고, 닫는 괄호가 나올 때 짝이 맞는지 확인하여 올바른 괄호인지 검사합니다.
후위 표기법 계산기
후위 표기법RPN, Reverse Polish Notation은 연산자가 피연산자 뒤에 위치하는 수학 표기법으로, 수식을 간단히 평가하기 위해 주로 사용됩니다. 예를 들어, 3 + 4라는 식을 후위 표기법으로 나타내면 3 4 +가 됩니다. 스택을 활용하여 후위 표기법을 계산하는 것은 매우 효율적이며, 연산자의 우선순위 및 괄호의 필요 없이도 올바른 계산을 수행할 수 있습니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string expression = "3 4 + 2 * 7 /"; // 후위 표기법 표현식
Console.WriteLine(CalculateRPN(expression)); // 결과: 2
}
static int CalculateRPN(string expression)
{
Stack<int> stack = new Stack<int>();
string[] tokens = expression.Split(' ');
foreach (string token in tokens)
{
if (int.TryParse(token, out int number))
{
stack.Push(number);
}
else
{
int operand2 = stack.Pop();
int operand1 = stack.Pop();
switch (token)
{
case "+":
stack.Push(operand1 + operand2);
break;
case "-":
stack.Push(operand1 - operand2);
break;
case "*":
stack.Push(operand1 * operand2);
break;
case "/":
stack.Push(operand1 / operand2);
break;
default:
throw new InvalidOperationException("지원되지 않는 연산자입니다.");
}
}
}
return stack.Pop();
}
}이 예제에서는 후위 표기법으로 작성된 수식을 스택을 사용하여 처리합니다. 숫자는 스택에 푸시하고, 연산자가 나오면 스택에서 두 개의 피연산자를 팝한 후 연산을 수행합니다. 이 방식은 계산 과정에서 매우 직관적이며 효율적입니다.
스택 프레임과 함수 호출 관리
스택은 컴퓨터 프로그램에서 함수 호출과 관련된 스택 프레임Stack Frame을 관리하는 중요한 역할을 합니다. 각 함수 호출 시 스택 프레임이 생성되며, 스택 프레임은 함수의 로컬 변수, 매개변수, 복귀 주소 등을 저장합니다.
스택 프레임의 동작 방식
- 함수 호출 시: 새로운 함수가 호출되면, 스택의 맨 위에 해당 함수의 스택 프레임이 추가됩니다. 여기에는 함수의 실행에 필요한 모든 정보가 포함되어 있습니다.
- 함수 종료 시: 함수가 종료되면 해당 스택 프레임이 스택에서 제거되며, 이전 함수로 복귀합니다. 이와 같은 구조 덕분에 함수 호출이 끝날 때마다 로컬 변수가 자동으로 정리되고, 함수 간의 호출 순서가 유지됩니다. 이러한 스택 프레임의 자동 관리 덕분에 프로그램의 메모리 사용이 효율적이지만, 지나치게 깊은 재귀 호출이 발생할 경우 스택 오버플로우Stack Overflow가 발생할 수 있습니다. 이를 방지하기 위해 재귀를 반복문으로 대체하는 등의 방법이 활용됩니다. 예를 들어, 재귀 호출이 많은 팩토리얼 함수는 스택 프레임을 많이 사용합니다:
static int Factorial(int n)
{
if (n == 1) return 1;
return n * Factorial(n - 1);
}이 함수가 호출될 때마다 새로운 스택 프레임이 추가되므로, 큰 값의 n에 대해서는 StackOverflowException이 발생할 수 있습니다. 이를 반복문을 사용해 비재귀적으로 구현하면 스택 사용을 줄일 수 있습니다:
static int FactorialIterative(int n)
{
Stack<int> stack = new Stack<int>();
int result = 1;
while (n > 1)
{
stack.Push(n);
n--;
}
while (stack.Count > 0)
{
result *= stack.Pop();
}
return result;
}- 재귀 호출을 스택을 사용하여 비재귀적으로 구현하여 스택 오버플로우를 방지합니다.
커스텀 스택 구현
기본 Stack<T>로 충족되지 않는 기능이 필요할 때 커스텀 스택을 구현할 수 있습니다. Stack<T>를 상속받아 필요한 기능을 추가하거나, 인터페이스를 구현하여 새로운 스택을 만들 수 있으며, 특정 시나리오에 맞게 성능을 최적화할 수 있습니다.
다음은 제한된 용량의 스택 구현 예시입니다.
using System;
using System.Collections.Generic;
public class LimitedStack<T>
{
private readonly int _maxSize;
private readonly Stack<T> _stack;
public LimitedStack(int maxSize)
{
_maxSize = maxSize;
_stack = new Stack<T>();
}
public void Push(T item)
{
if (_stack.Count >= _maxSize)
{
throw new InvalidOperationException("스택이 가득 찼습니다.");
}
_stack.Push(item);
}
public T Pop() => _stack.Pop();
public T Peek() => _stack.Peek();
public int Count => _stack.Count;
}
class Program
{
static void Main()
{
LimitedStack<int> stack = new LimitedStack<int>(maxSize: 2);
stack.Push(1);
stack.Push(2);
// stack.Push(3); // 예외 발생
Console.WriteLine(stack.Pop()); // 2
Console.WriteLine(stack.Pop()); // 1
}
}
Buy me a coffee