[Java] 스택과 큐를 쓰면 안되는 이유

코딩에 대해 배웠다면 무조건 들어본 스택과 큐!

하지만 이젠 스택과 큐를 쓰면 안됩니다! 

왜?

 

 

---

Stack vs ArrayDeque

 

Stack 클래스의 강점 (하지만 치명적인 단점)

- 스레드 안전성: 자바 1.0 극초창기에 만들어진 구식(Vector 상속) 클래스! 동기화 처리로 멀티스레드 환경에서 유용함

(스레드 동기화란? 여러 개의 스레드가 하나의 데이터(객체)에 동시에 접근할 때, 데이터가 꼬이지 않도록 한 번에 한 스레드만 접근할 수 있게 잠금을 거는 장치)

 

하지만 코딩테스트에선 단일스레드 환경!

나만 왔다갔다하기에 동기회 처리가 불필요한 오버헤드가 발생하고 속도를 낮추는 요인!

 

코테뿐만 아니라 스택을 안 쓰는 이유

자물쇠를 열고 닫는 과정 자체가 너무 무거움!

->  게다가 자바 공식 문서에서도 LIFO 자료구조가 필요하다면 Stack 대신 Deque 인터페이스를 사용하라고 권장함

요새 멀티스레드 환경에서는 ConcurrentLinkedDeque 같은 더 세련된 클래스를 사용함!

 

ArrayDeque 승리!

---

Queue vs ArrayDeque

이건 대결이라고 보기 어렵습니다.

왜냐하면 Queue는 ArrayDeque의 부모이기 때문이죠!

자식 이기는 부모 없습니다.

 

큐(Queue)와 덱(ArrayDeque)의 관계

자바에서 Queue는 Stack처럼 스스로 객체를 만들 수 있는 독자적인 클래스가 아니고 메서드의 형태만 정의된 인터페이스(설계도)입니다. 따라서 new Queue()처럼 직접 생성할 수 없고, 이 설계도를 바탕으로 구현된 실제 클래스를 선택해서 써야 함.

 

그래서 Queue vs ArrayDeque보다는 구현체인 LinkedList vs ArrayDeque로 자식끼리 대결해야 합니다!

LinkedList vs ArrayDeque

비교 대상	LinkedList (Queue 구현)	ArrayDeque (Queue 구현)
내부 구조	노드들이 포인터로 연결됨	연속된 배열 공간 사용
메모리	노드 객체 생성 비용이 큼	배열만 관리하므로 효율적
속도	상대적으로 느림	압도적으로 빠름

따라서, ArrayDeque는 내부적으로 배열을 사용하기 때문에 노드를 매번 생성해야 하는 LinkedList보다 메모리 소모가 적고 데이터 접근 속도가 훨씬 빠름!

 

ArrayDeque 승리!

---

그럼 승리한 ArrayDeque를 사용해야겠죠?

ArrayDeque 사용방법

Deque<Integer> stack = new ArrayDeque<>();
// 주로 사용하는 함수: push(), pop(), peek()

Queue<Integer> queue = new ArrayDeque<>();
// 주로 사용하는 함수: offer(), poll(), peek()

이때, 부모(Queue)타입으로 선언하고 자식(ArrayDeque)을 넣는 이유!

• 교체 용이성: 만약 나중에 ArrayDeque 말고 다른 큐로 바꾸고 싶을 때, 왼쪽의 타입을 Queue로 해두면 오른쪽의 new 뒷부분만 살짝 바꾸면 됩니다.
• 기능 제한(안전장치): ArrayDeque는 덱(Deque)이라서 앞뒤로 다 넣고 뺄 수 있지만 타입을 Queue로 선언하면 오직 큐의 기본 기능(한쪽으로 넣고 한쪽으로 빼기)만 사용할 수 있게 제한됩니다.

 

ArrayDeque의 강점

- 최고의 단일 스레드 성능: 무거운 동기화(자물쇠) 족쇄를 완전히 풀어버린 최신 자료구조입니다.

순수하게 메모리 배열 위에서 데이터를 넣고 빼는 속도가 매우 빠르고, 게다가 스택과 큐 역할을 모두 수행할 수 있는 유연성을 가졌음

 

---

결론

자바에서 스택이나 큐 구조가 필요할 땐, 멀티스레드 환경이 아니라면 무조건 ArrayDeque를 쓰는 게 현대 자바의 정석!!!