숏컷 코드
csharp
var stack = new Stack<int>();
stack.Push(1);
int top = stack.Pop();
var queue = new Queue<int>();
queue.Enqueue(1);
int front = queue.Dequeue();| 구조 | 규칙 | 넣기 | 빼기 | 대표 용도 |
|---|---|---|---|---|
| Stack | LIFO | Push | Pop | 되돌리기, 괄호, DFS |
| Queue | FIFO | Enqueue | Dequeue | 순서 처리, BFS |
구조
스택은 마지막에 넣은 값이 먼저 나옵니다. 그래서 아직 닫히지 않은 상태를 쌓아두거나, 깊이 들어갔다가 되돌아오는 문제에 잘 맞습니다.
csharp
bool IsValid(string s)
{
var stack = new Stack<char>();
foreach (char ch in s)
{
if (ch == '(') stack.Push(ch);
else if (ch == ')')
{
if (stack.Count == 0) return false;
stack.Pop();
}
}
return stack.Count == 0;
}큐는 먼저 들어온 값이 먼저 나옵니다. 같은 거리의 후보를 먼저 처리해야 하는 BFS에서 자연스럽습니다.
csharp
var q = new Queue<int>();
q.Enqueue(start);
visited[start] = true;
while (q.Count > 0)
{
int current = q.Dequeue();
foreach (int next in graph[current])
{
if (visited[next]) continue;
visited[next] = true;
q.Enqueue(next);
}
}언제 쓰나
| 문제 신호 | 자료구조 |
|---|---|
| 가장 최근 상태를 먼저 처리 | 스택 |
| 괄호, 태그, 경로 되돌리기 | 스택 |
| 재귀를 반복문으로 바꾸기 | 스택 |
| 먼저 들어온 순서대로 처리 | 큐 |
| 간선 비용이 같은 최단 거리 | 큐 기반 BFS |
| 단계별 전파, 확산 | 큐 |
스택과 큐는 자료구조 자체보다 처리 순서를 강제하는 도구입니다. 문제에서 “최근 것부터”, “먼저 온 것부터”, “한 단계씩 퍼짐” 같은 표현을 찾으면 후보가 됩니다.
주의할 점
Pop, Peek, Dequeue는 비어 있는 상태에서 호출하면 예외가 납니다. 코테에서는 항상 Count > 0을 먼저 확인하는 습관이 필요합니다.
BFS에서는 큐에 넣을 때 방문 처리하는 편이 중복 enqueue를 막기 쉽습니다. 꺼낼 때 방문 처리하면 같은 정점이 여러 번 큐에 들어가 시간과 메모리를 낭비할 수 있습니다.
참고 링크
2 sources