2-3. 자료구조: 스택과 큐

1. 스택 (Stack)

스택과 큐는 컴퓨터 과학에서 가장 기본적인 자료구조 중 하나로, 데이터를 효율적으로 관리하고 조직하는 데 필수적인 도구입니다. 이들은 데이터를 저장하고 접근하는 방식을 제한함으로써 특정 문제들을 해결하는 데 특화된 기능을 제공합니다. 특히, 스택은 LIFO (Last-In, First-Out), 즉 "후입선출" 원칙을 따릅니다. 이는 가장 나중에 스택에 들어온 요소가 가장 먼저 제거된다는 의미입니다. 마치 책을 쌓아 놓은 더미와 같아서, 마지막에 쌓은 책을 먼저 꺼내야 다른 책들에 접근할 수 있는 것과 유사합니다.

1) 스택의 개념과 특징

스택은 다음과 같은 특징을 가집니다.

• LIFO (Last-In, First-Out): 가장 최근에 추가된 항목이 가장 먼저 제거됩니다.
• 단일 접근 지점: 스택의 모든 연산은 스택의 "top" (꼭대기) 에서만 수행됩니다.
• 동적 크기 조절: 대부분의 스택 구현은 필요에 따라 크기를 동적으로 조절할 수 있습니다.

2) 스택의 연산

스택에서 수행되는 주요 연산은 다음과 같습니다.

• push(element): 스택의 top에 새로운 element를 추가합니다.
• pop(): 스택의 top에 있는 element를 제거하고 반환합니다.
• peek() 또는 top(): 스택의 top에 있는 element를 제거하지 않고 반환합니다.
• isEmpty(): 스택이 비어있는지 확인합니다.
• size(): 스택에 있는 요소의 수를 반환합니다.

3) 스택의 구현

스택은 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다.

• 배열 기반 스택: 배열의 끝을 top으로 간주하고, push와 pop 연산을 배열의 끝에서 수행합니다. 배열의 크기가 고정되어 있으면, 스택이 가득 찼을 때 push 연산을 수행하려고 하면 오버플로우가 발생할 수 있습니다.
• 연결 리스트 기반 스택: 연결 리스트의 head를 top으로 간주하고, 새로운 노드를 head에 추가하거나 head 노드를 제거하여 push와 pop 연산을 수행합니다. 연결 리스트는 동적으로 크기를 조절할 수 있으므로, 배열 기반 스택보다 유연합니다.

2. 큐 (Queue)

큐는 스택과 반대로 FIFO (First-In, First-Out), 즉 "선입선출" 원칙을 따르는 자료구조입니다. 먼저 큐에 들어온 요소가 먼저 제거됩니다. 이것은 일상생활에서 줄을 서는 것과 유사합니다. 먼저 온 사람이 먼저 서비스를 받는 것과 같습니다.

1) 큐의 개념과 특징

큐는 다음과 같은 특징을 가집니다.

• FIFO (First-In, First-Out): 가장 먼저 추가된 항목이 가장 먼저 제거됩니다.
• 두 개의 접근 지점: 큐는 데이터를 추가하는 enqueue 연산은 "rear" (뒤쪽)에서, 데이터를 제거하는 dequeue 연산은 "front" (앞쪽)에서 수행됩니다.
• 동적 크기 조절: 대부분의 큐 구현은 필요에 따라 크기를 동적으로 조절할 수 있습니다.

2) 큐의 연산

큐에서 수행되는 주요 연산은 다음과 같습니다.

• enqueue(element): 큐의 rear에 새로운 element를 추가합니다.
• dequeue(): 큐의 front에 있는 element를 제거하고 반환합니다.
• peek() 또는 front(): 큐의 front에 있는 element를 제거하지 않고 반환합니다.
• isEmpty(): 큐가 비어있는지 확인합니다.
• size(): 큐에 있는 요소의 수를 반환합니다.

3) 큐의 구현

큐는 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다.

• 배열 기반 큐: 배열의 시작을 front, 배열의 끝을 rear로 간주합니다. 배열 기반 큐는 원형 큐(Circular Queue)로 구현하여 공간 효율성을 높일 수 있습니다. 원형 큐는 배열의 끝에 도달했을 때, 배열의 처음으로 돌아가서 데이터를 저장할 수 있도록 합니다.
• 연결 리스트 기반 큐: 연결 리스트의 head를 front, tail을 rear로 간주합니다. enqueue 연산은 tail에 새로운 노드를 추가하고, dequeue 연산은 head 노드를 제거합니다.

3. 스택과 큐의 활용

스택과 큐는 다양한 알고리즘과 애플리케이션에서 핵심적인 역할을 합니다.

1) 스택의 활용

• 함수 호출: 프로그래밍 언어에서 함수 호출 시, 호출 스택(Call Stack)을 사용하여 함수 정보를 저장하고 관리합니다. 함수가 호출되면, 해당 함수의 정보(매개변수, 지역 변수 등)가 스택에 push되고, 함수가 종료되면 pop되어 스택에서 제거됩니다.
• 수식 계산 (후위 표기법): 후위 표기법 (postfix notation)으로 표현된 수식을 계산할 때 스택을 사용합니다. 연산자를 만나면 스택에서 두 개의 피연산자를 pop하여 연산을 수행하고, 결과를 다시 스택에 push합니다.
• 괄호 짝 맞추기: 괄호의 짝이 맞는지 확인하는 데 스택을 사용할 수 있습니다. 여는 괄호를 만나면 스택에 push하고, 닫는 괄호를 만나면 스택에서 pop하여 짝을 확인합니다.
• DFS (Depth-First Search): 깊이 우선 탐색 알고리즘에서 스택을 사용하여 방문해야 할 노드를 관리합니다.

2) 큐의 활용

• BFS (Breadth-First Search): 너비 우선 탐색 알고리즘에서 큐를 사용하여 방문해야 할 노드를 관리합니다.
• 작업 스케줄링: 운영체제에서 프로세스 스케줄링을 위해 큐를 사용할 수 있습니다.
• 버퍼 (Buffer): 데이터를 임시로 저장하는 버퍼를 구현하는 데 큐를 사용할 수 있습니다. 예를 들어, 프린터 큐는 인쇄 작업을 순서대로 처리하기 위해 큐를 사용합니다.
• 시뮬레이션: 이벤트 기반 시뮬레이션에서 이벤트를 시간 순서대로 처리하기 위해 큐를 사용할 수 있습니다.

4. DFS (Depth-First Search)와 BFS (Breadth-First Search)

DFS와 BFS는 그래프 또는 트리 구조를 탐색하는 기본적인 알고리즘입니다.

1) DFS (Depth-First Search)

DFS는 스택을 사용하여 구현할 수 있습니다. DFS는 그래프의 한 노드에서 시작하여, 가능한 깊이까지 탐색한 후, 더 이상 탐색할 노드가 없으면 백트래킹(backtracking)하여 다른 경로를 탐색합니다.

• 알고리즘:
  1. 시작 노드를 방문하고 스택에 push합니다.
  2. 스택이 비어있지 않은 동안 다음을 반복합니다.
     • 스택에서 노드를 pop합니다.
     • pop된 노드를 방문합니다.
     • pop된 노드의 인접 노드 중 방문하지 않은 노드를 스택에 push합니다.

• 특징:

  • 깊이 우선 탐색.
  • 스택 사용.
  • 재귀 호출 또는 반복문을 사용하여 구현 가능.
  • 그래프의 모든 노드를 방문하지 않고 특정 조건을 만족하는 노드를 찾을 때 유용합니다. (예: 미로 찾기)

2) BFS (Breadth-First Search)

BFS는 큐를 사용하여 구현할 수 있습니다. BFS는 시작 노드에서 시작하여, 인접한 노드를 먼저 탐색한 후, 다음 레벨의 노드를 탐색합니다.

• 알고리즘:
  1. 시작 노드를 방문하고 큐에 enqueue합니다.
  2. 큐가 비어있지 않은 동안 다음을 반복합니다.
     • 큐에서 노드를 dequeue합니다.
     • dequeue된 노드를 방문합니다.
     • dequeue된 노드의 인접 노드 중 방문하지 않은 노드를 큐에 enqueue합니다.

• 특징:

  • 너비 우선 탐색.
  • 큐 사용.
  • 그래프의 최단 경로를 찾는 데 유용합니다.
  • 그래프의 모든 노드를 방문해야 할 때 유용합니다.

5. 스택과 큐의 시간 복잡도

스택과 큐의 기본 연산은 대부분 O(1)의 시간 복잡도를 가집니다. 즉, 연산의 수행 시간은 입력 크기에 영향을 받지 않고 일정합니다.

• 스택:

  • push(): O(1)
  • pop(): O(1)
  • peek(): O(1)
  • isEmpty(): O(1)
  • size(): O(1)
  • 큐:
  • enqueue(): O(1)
  • dequeue(): O(1)
  • peek(): O(1)
  • isEmpty(): O(1)
  • size(): O(1)

그러나, 배열 기반 스택이나 큐에서 배열의 크기를 동적으로 조절하는 경우, 크기 조절 연산 (예: 배열을 확장하는 경우)은 O(n)의 시간 복잡도를 가질 수 있습니다.

6. 스택과 큐의 실용적인 고려 사항

스택과 큐를 사용할 때 고려해야 할 몇 가지 사항이 있습니다.

• 메모리 사용량: 스택과 큐는 데이터를 저장하기 위해 메모리를 사용합니다. 스택의 경우, 너무 많은 데이터를 push하면 스택 오버플로우가 발생할 수 있습니다. 큐의 경우, 큐가 무한정 커질 수 있으므로 메모리 관리가 필요합니다.
• 구현 선택: 배열 기반 구현과 연결 리스트 기반 구현 중 어느 것을 선택할지는 사용 사례와 요구 사항에 따라 다릅니다. 배열 기반 구현은 메모리 접근이 빠르지만, 크기가 고정되어 있거나 크기 조절 시 오버헤드가 발생할 수 있습니다. 연결 리스트 기반 구현은 동적 크기 조절이 용이하지만, 메모리 할당 및 해제 오버헤드가 발생할 수 있습니다.
• 오류 처리: 스택과 큐의 연산 중 오류가 발생할 수 있는 경우를 고려하여 오류 처리 코드를 작성해야 합니다. 예를 들어, pop() 연산 시 스택이 비어있는 경우, dequeue() 연산 시 큐가 비어있는 경우 등을 처리해야 합니다.

7. 결론

스택과 큐는 컴퓨터 과학에서 중요한 역할을 하는 자료구조입니다. 이들의 특징과 활용 사례를 이해함으로써, 다양한 문제들을 효율적으로 해결할 수 있습니다. DFS와 BFS와 같은 알고리즘을 구현하는 데 있어서도 스택과 큐는 필수적인 도구입니다. 상황에 맞는 자료구조를 선택하고, 효율적으로 사용하는 능력을 키우는 것이 중요합니다.