[Java vs Python] 스택/큐 구현 (Deque 기준)

코딩 테스트에서 스택과 큐는 자바는 ArrayDeque, 파이썬은 collections.deque 하나로 모두 해결할 수 있다.
헷갈리는 건 딱 두 가지다. 꺼내는 방향과 비어 있을 때의 동작

---

0. 선언

// Java
import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> queue = new ArrayDeque<>();   // Queue<Integer> queue = new ArrayDeque<>(); 도 가능

# Python
from collections import deque

stack = deque()          # 스택은 그냥 list를 써도 된다: stack = []
queue = deque([1, 2, 3]) # 리스트/튜플 등 iterable로 바로 초기화 가능

선언 시 체크포인트

• Deque는 인터페이스라서 new Deque<>()는 불가능하다. 구현체 ArrayDeque 또는 LinkedList를 쓴다.
• 코테에서는 ArrayDeque 를 쓰자. LinkedList보다 빠르고 메모리 효율이 좋다. 레거시 Stack 클래스도 쓸 이유가 없다.
• ArrayDeque에는 null을 넣을 수 없다 (NullPointerException).
• 파이썬 deque는 타입을 명시하지 않으므로 숫자·문자열·튜플 등을 섞어 넣을 수 있다.
• 파이썬에서 큐를 list로 만들고 pop(0)을 쓰면 O(N) 이다. 큐는 반드시 deque의 popleft()(O(1))를 쓴다.

---

1. 스택 (Stack, LIFO: 후입선출)

자바는 맨 앞(왼쪽), 파이썬은 맨 뒤(오른쪽) 이 입구이자 출구

기능	자바 (Deque)	파이썬 (deque)	조작 위치
넣기	dq.push(x)	dq.append(x)	자바: 맨 앞 / 파이썬: 맨 뒤
꺼내기	dq.pop()	dq.pop()	자바: 맨 앞 / 파이썬: 맨 뒤
최상단 확인	dq.peek() / dq.peekFirst()	dq[-1]	자바: 맨 앞 / 파이썬: 맨 뒤
비었는지 확인	dq.isEmpty()	not dq	-
크기	dq.size()	len(dq)	-

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);   // [3, 2, 1]
stack.peek();  // 3
stack.pop();   // 3

stack = deque()
stack.append(1); stack.append(2); stack.append(3)  # [1, 2, 3]
stack[-1]      # 3
stack.pop()    # 3

두 코드 모두 마지막에 넣은 3이 먼저 나온다. 내부 저장 순서만 반대일 뿐 동작은 같다.

---

2. 큐 (Queue, FIFO: 선입선출)

두 언어 모두 맨 뒤로 넣고, 맨 앞에서 꺼낸다.

기능	자바 (Deque)	파이썬 (deque)	조작 위치
넣기	dq.offer(x) / dq.add(x)	dq.append(x)	두 언어 모두 맨 뒤
꺼내기	dq.poll() / dq.pollFirst()	dq.popleft()	두 언어 모두 맨 앞
맨 앞 확인	dq.peek() / dq.peekFirst()	dq[0]	두 언어 모두 맨 앞
비었는지 확인	dq.isEmpty()	not dq	-
크기	dq.size()	len(dq)	-

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2); queue.offer(3);  // [1, 2, 3]
queue.peek();  // 1
queue.poll();  // 1

queue = deque()
queue.append(1); queue.append(2); queue.append(3)  # [1, 2, 3]
queue[0]         # 1
queue.popleft()  # 1

---

3. 비어 있을 때 동작 (에러 처리)

가장 많이 실수하는 부분이다.

상황	자바	파이썬
꺼내기	poll() → null 반환 pop(), remove() → NoSuchElementException	pop(), popleft() → IndexError
확인	peek() → null 반환 element(), getFirst() → 예외	dq[0], dq[-1] → IndexError

• 자바: poll() / peek() 계열은 null을 돌려주므로 비교적 안전하다. 단, 스택의 pop()은 예외를 던진다. 꺼내기 전에 isEmpty()로 확인하는 습관을 들이자.
• 파이썬: 비어 있으면 무조건 예외가 난다. 실행 전에 if dq: 로 확인한다.

while (!stack.isEmpty()) {
    int top = stack.pop();
}

while dq:
    top = dq.pop()

---

4. 한눈에 보는 전체 치트시트

용도	동작	자바 (ArrayDeque)	파이썬 (deque)
스택	넣기	push(x)	append(x)
스택	꺼내기	pop()	pop()
스택	확인	peek()	dq[-1]
큐	넣기	offer(x)	append(x)
큐	꺼내기	poll()	popleft()
큐	확인	peek()	dq[0]
덱	앞에 넣기	offerFirst(x)	appendleft(x)
덱	뒤에서 꺼내기	pollLast()	pop()
덱	맨 뒤 확인	peekLast()	dq[-1]
공통	비었는지	isEmpty()	not dq
공통	크기	size()	len(dq)

---

💡 이것만 기억하자

1. pop()의 방향이 다르다.
   자바 pop()은 맨 앞(왼쪽), 파이썬 pop()은 맨 뒤(오른쪽) 에서 꺼낸다.
2. 큐는 둘 다 뒤로 넣고 앞에서 꺼낸다.
   자바 offer / poll, 파이썬 append / popleft.
3. 비어 있을 때가 다르다.
   자바 poll() / peek()은 null, 파이썬은 IndexError. 자바 pop()도 예외가 나니 둘 다 꺼내기 전에 비었는지 확인하자.