[크래프톤 정글 ] 스택과 큐

Algorithm

[크래프톤 정글 ] 스택과 큐

하루이2222 2024. 9. 20. 11:30

스택(Stack)과 큐(Queue)는 데이터 구조의 기본적인 개념으로, 데이터의 순서와 접근 방식에 중점을 둔 자료구조이다. 이 두 자료구조는 많은 알고리즘과 소프트웨어 시스템에서 중요한 역할을 한다.

스택 (Stack)

스택은 LIFO (Last In, First Out) 구조를 따르는 자료구조다. 즉, 마지막에 삽입된 데이터가 가장 먼저 제거된다. 스택은 물리적으로 한 쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 구조를 가진다.

주요 연산:

push(data): 스택의 꼭대기에 데이터를 삽입한다.
pop(): 스택의 꼭대기에서 데이터를 제거하고 반환한다.
peek(): 스택의 꼭대기에 있는 데이터를 제거하지 않고 반환한다.
isEmpty(): 스택이 비어 있는지 확인한다.
size(): 스택에 있는 요소의 수를 반환한다.

스택의 내부 동작:

스택은 보통 배열이나 연결 리스트로 구현된다. 배열을 사용하는 경우, 배열의 크기를 초과하는 데이터를 push할 때 스택 오버플로우(overflow)가 발생할 수 있다. 연결 리스트를 사용할 때는 동적 메모리 할당으로 인해 오버플로우의 위험이 줄어든다.

스택의 응용:

함수 호출: 함수가 호출될 때마다 호출된 함수의 주소, 지역 변수, 매개변수 등을 스택에 저장하고, 함수 호출이 끝나면 스택에서 이들을 제거한다.
수식 계산: 후위 표기법(Reverse Polish Notation, RPN) 계산에서 사용된다.
백트래킹: 예를 들어 미로 탐색에서 되돌아가는 경로를 저장하기 위해 스택이 사용된다.

예제 코드 (Python으로 구현):

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.stack.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# 사용 예시
s = Stack()
s.push(10)
s.push(20)
print(s.peek())  # 20 출력
print(s.pop())   # 20 출력
print(s.size())  # 1 출력

큐 (Queue)

큐는 FIFO (First In, First Out) 구조를 따르는 자료구조다. 즉, 먼저 삽입된 데이터가 가장 먼저 제거된다. 큐는 두 개의 끝을 가지며, 한쪽 끝(front)에서는 데이터를 제거하고, 다른 쪽 끝(rear)에서는 데이터를 삽입한다.

주요 연산:

enqueue(data): 큐의 끝에 데이터를 삽입한다.
dequeue(): 큐의 앞에서 데이터를 제거하고 반환한다.
peek(): 큐의 앞에 있는 데이터를 제거하지 않고 반환한다.
isEmpty(): 큐가 비어 있는지 확인한다.
size(): 큐에 있는 요소의 수를 반환한다.

큐의 내부 동작:

큐는 배열, 연결 리스트, 또는 원형 큐로 구현될 수 있다. 배열로 구현된 큐는 크기 제한이 있을 수 있고, 데이터를 제거할 때 매번 배열의 요소를 앞으로 이동시켜야 하는 비효율성이 있다. 연결 리스트를 사용하는 경우, 삽입과 제거가 더 효율적으로 이루어진다.

큐의 응용:

작업 스케줄링: 작업을 순차적으로 처리할 때 큐를 사용한다.
버퍼 관리: 데이터 스트림을 일시적으로 저장하고 순차적으로 처리할 때 큐가 사용된다.
탐색 알고리즘: 너비 우선 탐색(BFS)에서 큐를 사용하여 노드를 탐색 순서대로 저장하고 처리한다.

예제 코드 (Python):

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.queue.pop(0)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# 사용 예시
q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.peek())  # 10 출력
print(q.dequeue())  # 10 출력
print(q.size())  # 1 출력

스택과 큐의 차이점 정리:

동작 방식: 스택은 LIFO, 큐는 FIFO를 따른다.
접근 방식: 스택은 마지막으로 삽입된 요소에 접근하며, 큐는 처음 삽입된 요소에 접근한다.
구현 방식: 스택은 보통 배열이나 연결 리스트로 구현되며, 큐는 배열, 연결 리스트, 또는 원형 큐로 구현된다.

스택과 큐의 공통점:

모두 선형 자료구조로, 삽입과 제거 연산이 주로 이루어진다.
추상적 자료형(Abstract Data Type, ADT)으로, 인터페이스만 정의되고 내부 구현은 다양할 수 있다.

Deque

Deque(덱, Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조다. 이름에서 알 수 있듯이, Deque는 Double-Ended Queue의 약자로, 큐(Queue)와 비슷하지만 더 유연하다. Deque는 스택과 큐의 기능을 모두 포함하고 있어 다양한 상황에서 사용할 수 있다.

Deque의 특징

양방향 삽입/삭제: Deque는 앞(front)과 뒤(rear)에서 모두 요소를 삽입하거나 삭제할 수 있다.
유연성: 스택처럼 동작할 수도 있고 큐처럼 동작할 수도 있다.
동적 크기: 대부분의 구현에서 크기가 동적으로 확장될 수 있다.

주요 연산

append(item): Deque의 뒤쪽(rear)에 요소를 삽입한다.
appendleft(item): Deque의 앞쪽(front)에 요소를 삽입한다.
pop(): Deque의 뒤쪽(rear)에서 요소를 제거하고 반환한다.
popleft(): Deque의 앞쪽(front)에서 요소를 제거하고 반환한다.
peek(): Deque의 앞(front)이나 뒤(rear)의 요소를 제거하지 않고 반환할 수 있다.
isEmpty(): Deque가 비어 있는지 확인한다.
size(): Deque에 있는 요소의 수를 반환한다.

Deque의 구현

Deque는 연결 리스트나 동적 배열로 구현할 수 있다. Python에서는 collections 모듈의 deque 클래스를 사용하여 Deque를 쉽게 사용할 수 있다. 이 deque는 양방향으로 빠른 삽입과 삭제를 지원하는 구조로, 리스트(list)보다 효율적이다.

Deque의 응용

양방향 탐색 알고리즘: Deque는 BFS에서 양쪽 방향으로 탐색할 때 유용하다.
슬라이딩 윈도우: 데이터 스트림에서 슬라이딩 윈도우를 처리할 때 Deque를 사용하여 효율적으로 최대값이나 최소값을 계산할 수 있다.
캐시 구현: 최근 사용한 항목을 앞쪽에 두고 덜 사용한 항목을 뒤쪽으로 밀어내는 LRU (Least Recently Used) 캐시를 구현할 때 유용하다.

예제 코드 (Python):

from collections import deque

# Deque 초기화
d = deque()

# 뒤쪽에 요소 추가
d.append(10)
d.append(20)

# 앞쪽에 요소 추가
d.appendleft(5)

# 뒤쪽에서 요소 제거
print(d.pop())  # 20 출력

# 앞쪽에서 요소 제거
print(d.popleft())  # 5 출력

# Deque의 현재 상태
print(d)  # deque([10])

# 크기 확인
print(d.size())  # 1 출력 (deque 클래스의 기본 제공 메서드에는 size가 없으므로, len(d)를 사용할 수 있음)

# Deque이 비어 있는지 확인
print(len(d) == 0)  # False 출력

Deque의 장점

유연성: 스택과 큐의 기능을 모두 제공한다.
효율성: Python의 deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입 및 삭제를 수행할 수 있다.
다양한 용도: 큐, 스택, 그리고 기타 고급 자료구조 및 알고리즘을 구현할 때 유용하다.

Deque와 다른 자료구조의 비교

큐(Queue)와 Deque: 큐는 한쪽 끝에서만 삽입하고 다른 한쪽 끝에서만 삭제할 수 있지만, Deque는 양쪽 끝에서 삽입과 삭제가 가능하다.
스택(Stack)과 Deque: 스택은 한쪽 끝에서만 삽입과 삭제가 가능하지만, Deque는 양쪽 끝에서 삽입과 삭제가 가능하다.
리스트(List)와 Deque: 리스트는 양쪽 끝에서 삽입과 삭제가 가능하지만, 중간에서의 삽입과 삭제가 가능하며 Deque보다 이러한 작업에서 비효율적일 수 있다. Deque는 이와 비교하여 양 끝에서의 삽입과 삭제가 더 효율적이다.