[알고리즘 : 스택과 큐] 데이터 구조의 기본 개념과 활용

코스모에듀벤처

데이터 구조는 프로그래밍에서 중요한 역할을 합니다. 그중에서도 스택(Stack)과 큐(Queue)는 가장 기본적이면서도, 다양한 알고리즘과 시스템에서 핵심적인 역할을 담당하는 자료구조입니다. 이번 글에서는 스택과 큐의 개념, 동작 원리, 그리고 실생활 및 프로그래밍에서의 활용 사례에 대해 알아보겠습니다.

스택(Stack)의 개념과 특징

스택은 LIFO(Last In, First Out) 원칙을 따르는 자료구조입니다. 이는 "가장 마지막에 들어온 데이터가 가장 먼저 나간다"는 의미입니다. 스택을 실생활에 비유하자면 책을 쌓아둔 더미와 같습니다. 새로운 책은 맨 위에 쌓이고, 책을 꺼낼 때도 맨 위에서부터 꺼내게 됩니다.

스택의 주요 연산

1. push: 스택의 맨 위에 데이터를 추가합니다.
2. pop: 스택의 맨 위에서 데이터를 제거하고 그 값을 반환합니다.
3. peek/top: 스택의 맨 위 데이터를 제거하지 않고 확인만 합니다.
4. isEmpty: 스택이 비어있는지 확인합니다.
5. size: 스택에 저장된 데이터의 개수를 반환합니다.

스택의 구현 예시 (Python)

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None
    
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None
    
    def is_empty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

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

큐(Queue)의 개념과 특징

큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조입니다. 이는 "가장 먼저 들어온 데이터가 가장 먼저 나간다"는 의미입니다. 실생활에서 볼 수 있는 줄서기가 큐의 대표적인 예입니다. 먼저 온 사람이 먼저 서비스를 받고 떠나는 것과 같습니다.

큐의 주요 연산

1. enqueue: 큐의 뒤쪽(rear)에 데이터를 추가합니다.
2. dequeue: 큐의 앞쪽(front)에서 데이터를 제거하고 그 값을 반환합니다.
3. peek/front: 큐의 맨 앞 데이터를 확인만 합니다.
4. isEmpty: 큐가 비어있는지 확인합니다.
5. size: 큐에 저장된 데이터의 개수를 반환합니다.

큐의 구현 예시 (Python)

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()
    
    def enqueue(self, item):
        self.queue.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        return None
    
    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        return None
    
    def is_empty(self):
        return len(self.queue) == 0
    
    def size(self):
        return len(self.queue)

# 큐 사용 예시
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 출력: 1
print(queue.peek())     # 출력: 2
print(queue.size())     # 출력: 2

스택과 큐의 주요 차이점

특성 스택 큐

접근 방식	LIFO (Last In First Out)	FIFO (First In First Out)
삽입 위치	맨 위 (Top)	맨 뒤 (Rear)
삭제 위치	맨 위 (Top)	맨 앞 (Front)
실생활 예시	책더미, 접시쌓기	줄서기, 티켓 발권
주요 용도	함수 호출 관리, 실행 취소	작업 스케줄링, 데이터 버퍼

실생활에서의 스택과 큐

스택의 실생활 예시

1. 웹 브라우저의 뒤로 가기 버튼: 방문한 페이지는 스택에 쌓이고, 뒤로 가기를 누르면 가장 최근에 방문한 페이지로 돌아갑니다.
2. 문서 편집기의 실행 취소(Undo) 기능: 변경 사항들이 스택에 저장되어, 실행 취소를 하면 가장 최근의 변경부터 취소됩니다.
3. 함수 호출 관리: 프로그램에서 함수를 호출할 때, 호출된 함수들은 스택에 쌓이고 실행이 완료된 함수부터 스택에서 제거됩니다.
4. 괄호 매칭 검사: 프로그래밍 언어에서 괄호의 짝이 맞는지 확인할 때 스택을 사용합니다.

큐의 실생활 예시

1. 프린터 인쇄 대기열: 인쇄 요청은 큐에 저장되어 먼저 요청된 문서부터 차례대로 인쇄됩니다.
2. 운영체제의 프로세스 스케줄링: CPU는 준비 큐에 있는 프로세스를 순서대로 처리합니다.
3. 메시지 처리 시스템: 메시지는 큐에 도착한 순서대로 처리됩니다.
4. BFS(너비 우선 탐색): 그래프 알고리즘에서 인접 노드를 탐색할 때 큐를 사용합니다.

고급 개념: 특수한 스택과 큐

특수한 스택

1. 최소값 스택(Min Stack): 스택의 최소값을 O(1) 시간에 얻을 수 있는 스택입니다.
2. 괄호 스택(Parenthesis Stack): 괄호의 짝을 맞추는 데 특화된 스택입니다.
3. 후위 표기법(Postfix Notation) 계산기: 후위 표기법으로 된 수식을 계산할 때 사용합니다.

특수한 큐

1. 우선순위 큐(Priority Queue): 일반적인 FIFO 규칙 대신, 각 항목에 우선순위를 할당하여 높은 우선순위의 항목이 먼저 처리됩니다.
2. 원형 큐(Circular Queue): 마지막 위치와 첫 위치가 연결된 형태의 큐로, 메모리를 효율적으로 사용합니다.
3. 양방향 큐(Deque, Double-Ended Queue): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.

스택과 큐를 활용한 알고리즘 문제 해결

스택을 활용한 문제

1. 괄호 짝 맞추기: 여는 괄호는 스택에 푸시하고, 닫는 괄호를 만나면 스택에서 팝하여 짝이 맞는지 확인합니다.
2. 히스토그램에서 가장 큰 직사각형 찾기: 높이를 스택에 저장하여 효율적으로 계산합니다.
3. DFS(깊이 우선 탐색): 그래프를 탐색할 때 스택을 사용하여 구현할 수 있습니다.

큐를 활용한 문제

1. BFS(너비 우선 탐색): 시작점에서 가까운 노드부터 탐색할 때 큐를 사용합니다.
2. 미로 탐색 최단 경로: BFS를 사용하여 출발점에서 도착점까지의 최단 경로를 찾습니다.
3. 작업 스케줄링: 작업들을 큐에 넣고 순서대로 처리합니다.

스택과 큐의 효율적인 사용 팁

1. 적절한 자료구조 선택: 문제 상황에 맞는 자료구조를 선택하는 것이 중요합니다. 가장 최근 데이터를 중심으로 처리하는 경우 스택을, 순서대로 처리해야 하는 경우 큐를 사용합니다.
2. 라이브러리 활용: 대부분의 프로그래밍 언어는 스택과 큐를 위한 내장 라이브러리나 컬렉션을 제공합니다. 이를 활용하면 직접 구현하는 것보다 효율적입니다.
3. 메모리 관리: 스택과 큐의 크기를 적절히 제한하여 메모리 사용을 관리합니다. 특히 재귀 함수에서 스택 오버플로우에 주의해야 합니다.
4. 성능 최적화: 데이터의 양이 많을 경우, 구현 방식에 따라 성능 차이가 발생할 수 있습니다. 연결 리스트 기반과 배열 기반 구현의 장단점을 이해하고 상황에 맞게 선택합니다.

결론

스택과 큐는 컴퓨터 과학에서 가장 기본적이면서도 강력한 자료구조입니다. 이들의 동작 원리와 특성을 잘 이해하면, 다양한 알고리즘 문제를 효율적으로 해결할 수 있고, 복잡한 시스템 설계에도 적용할 수 있습니다. 실생활의 많은 상황들이 스택이나 큐의 원리로 설명될 수 있다는 점도 흥미롭습니다.

각자의 상황과 필요에 맞게 스택과 큐를 적절히 활용한다면, 프로그래밍 효율성을 크게 향상시킬 수 있을 것입니다. 앞으로 알고리즘 공부나 프로그램 개발 시 이 두 자료구조의 특성을 잘 기억해두면 큰 도움이 될 것입니다.

여러분도 일상생활이나 프로그래밍에서 스택과 큐의 원리를 적용할 수 있는 상황을 찾아보세요. 생각보다 많은 곳에서 이 기본적인 자료구조들의 흔적을 발견할 수 있을 것입니다!

2025.04.12 - [파이썬(python)/알고리즘] - [알고리즘 : 수열]알고리즘 속 수열의 세계: 개념부터 실생활 활용까지