[WEEK02] 스택/큐, 데크

스택 (Stack)

• 스택은 후입선출(LIFO, Last In First Out) 구조를 가지는 자료구조다.
• 즉, 가장 마지막에 추가된 요소가 가장 먼저 제거된다.
• 스택의 추가와 삭제는 한쪽 끝(마지막 인덱스 쪽)에서만 발생한다.

주요 연산

• push(데이터 삽입): 스택의 맨 위에 데이터를 추가
• pop(데이터 제거): 스택의 맨 위에 있는 데이터를 제거하고 반환
• peek(데이터 조회): 스택의 맨 위에 있는 데이터를 확인 (제거하지 않음)
• is_empty(비어있는지 확인): 스택이 비어있는지 여부를 반환

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)

파이썬의 리스트는 기본적으로 pop() 메서드를 제공해주기 때문에 리스트를 스택으로 사용하는 것도 가능하다. 또한, 리스트를 사용하면 일일이 스택의 길이를 지정해주지 않아도 된다는 장점이 있다.

---

큐 (Queue)

• 큐는 선입선출(FIFO, First In First Out) 구조를 가지는 자료구조다.
• 즉, 먼저 추가된 요소가 먼저 제거된다.
• 큐의 추가는 뒤쪽, 큐의 제거는 앞쪽에서 발생한다.

주요 연산

• enqueue(데이터 삽입): 큐의 뒤쪽(rear)에 데이터를 추가
• dequeue(데이터 제거): 큐의 앞(front)에 있는 데이터를 제거하고 반환
• peek(데이터 조회): 큐의 앞(front)에 있는 데이터를 확인 (제거하지 않음)
• is_empty(비어있는지 확인): 큐가 비어있는지 여부를 반환

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)

파이썬의 리스트는 popleft() 메서드가 없기 때문에 deque()를 사용해서 구현해야 한다.

---

데크 (deque)

• 데크(Deque, Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐의 일반화된 형태이다.
• 스택과 큐를 합친 형태라고 생각하면 이해하기 편하다.
• 리스트보다 빠른 시간 복잡도를 제공하여 큐와 스택을 효율적으로 구현할 수 있다.
• 파이썬에서는 collections 모듈에서 deque를 import해서 스택과 큐를 쉽게 구현할 수 있다. 

주요 연산

• append(데이터 삽입): 오른쪽 끝에 데이터 추가
• appendleft(데이터 삽입): 왼쪽 끝에 데이터 추가
• pop(데이터 제거): 오른쪽 끝의 데이터를 제거하고 반환
• popleft(데이터 제거): 왼쪽 끝의 데이터를 제거하고 반환

여러가지 메서드

• extend(iterable): iterable의 요소들을 오른쪽 끝에 추가
• extendleft(iterable): iterable의 요소들을 왼쪽 끝에 추가 (순서가 반대로 추가됨)

• rotate(n=1): n만큼 오른쪽으로 회전 (n이 음수면 왼쪽 회전)
• reverse(): deque의 요소 순서를 반전 (제자리 변경)

• len(dq): deque의 길이 반환
• clear(): 모든 요소 제거
• copy(): deque의 shallow copy 반환

• index(item, start=0, stop=None): item이 처음으로 나타나는 인덱스 반환
• insert(index, item): 특정 인덱스에 요소 삽입
• remove(item): item을 찾아 처음 등장하는 요소 제거

• deque(iterable, maxlen=N): 최대 길이가 N인 deque 생성 (초과 시 자동 삭제)

from collections import deque

# deque 생성
dq = deque([1, 2, 3])
dq.append(4)       # [1, 2, 3, 4]
dq.appendleft(0)   # [0, 1, 2, 3, 4]
dq.pop()           # [0, 1, 2, 3]
dq.popleft()       # [1, 2, 3]

dq.extend([5, 6])  # [1, 2, 3, 5, 6]
dq.extendleft([-1, -2])  # [-2, -1, 1, 2, 3, 5, 6]

dq.rotate(2)       # [5, 6, -2, -1, 1, 2, 3]
dq.reverse()       # [3, 2, 1, -1, -2, 6, 5]

dq.remove(1)       # [3, 2, -1, -2, 6, 5]