[Algorithm] 스택(Stack)과 큐(Queue)

1. 스택(Stack)

개념

 - LIFO(Last In First Out, 후입선출) 구조

 - 가장 나중에 들어온 데이터가 가장 먼저 나가는 형태

 - 입구가 출구가 하나인 구조

 

주요 연산

 - push : 데이터를 넣는 연산 (top 위치에 삽입)

 - pop : 데이터를 꺼내는 연산 (top 위치 데이터 삭제 및 반환)

 - peek : 데이터를 꺼내지 않고 확인만 하는 연산

 

활용

 - DFS(깊이 우선 탐색)

 - 백트래킹 (Backtracking)

 - 재귀 함수의 원리와 동일

 

Java 구현

Java에서 스택을 사용할 때 java.util.Stack 클래스는 사용을 지양해야 한다.

 - 이유 : Stack은 초기 Java 버전의 Vector를 상속받아 구현되어 있어, 모든 메서드에 동기화(Synchronized) 키워드가 붙어 있다. 이는 멀티 스레드 환경이 아닐 때 불필요한 오버헤드를 발생시킨다.

 - 대안 : Deque 인터페이스의 구현체인 ArrayDeque를 사용하는 것이 성능면에서 유리하다.

 

예시)

// 비추천 (Legacy)
Stack<Integer> stack = new Stack<>();

// 추천 (Modern Java)
Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);
stack.push(2);
stack.peek(); // 2 출력
stack.pop();  // 2 반환 및 삭제

 

2. 큐(Queue)

개념

 - FIFO (First In First Out, 선입선출) 구조

 - 먼저 들어온 데이터가 먼저 나가는 형태

 - 양쪽이 뚫려있는 구조

 

주요 연산

 - add / offer : 데이터를 넣는 연산 (rear/tail 위치에 삽입). offer는 실패 시 예외 대신 false를 반환하므로 더 안정적

 - remove / poll : 데이터를 꺼내는 연산 (front/head 위치 데이터 삭제 및 변환) poll은 비어 있을 때 null을 반환

 - element / peek : 데이터를 확인만 하는 연산

 

활용

 - BFS (너비 우선 탐색)

 - 캐시(Cache) 구현

 - 프로세스 스케줄링

 

Java 구현(LinkedList vs ArrayDeque)

Queue는 인터페이스이므로 구현체가 필요하다. 보통 LinkedList와 ArrayDeque 중 하나를 선택한다. 

 - LinkedList : 큐의 중간에 데이터를 삽입/삭제할 일이 많다면 유리하다. 하지만 각 요소가 노드 객체로 생성되므로 메모리 오버헤드가 있다.

 - ArrayDeque : 큐의 양 끝에서만 연산이 일어난다면(순수 큐 기능) 메모리 효율과 속도(Cache Locality)면에서 LinkedList 보다 유리하다.

 

예시)

// 일반적인 구현 (LinkedList 사용)
Queue<Integer> queue = new LinkedList<>();

// 성능 중시 (ArrayDeque 사용)
Queue<Integer> queue = new ArrayDeque<>();

queue.offer(1);
queue.offer(2);
queue.peek(); // 1 출력 (먼저 들어간 값)
queue.poll(); // 1 반환 및 삭제

 

3. 우선순위 큐(Priority Queue)

 - 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

 - 힙(Heap) 자료구조를 기반으로 구현

 - Java에서는 PriorityQueue 클래스를 사용하며, 기본적으로 낮은 숫자(Min Heap)가 높은 우선순위를 가진다.(높은 숫자를 우선시 하려면 Collections.reverseOrder() 사용)

 

예시)

// 낮은 숫자가 우선 (Min Heap)
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 높은 숫자가 우선 (Max Heap)
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

정리

스택과 큐는 알고리즘 문제 해결의 도구다. 단순히 메서드만 아는 것보다, 문제의 성격(DFS 또는 BFS)에 따라 적절한 자료구조를 선택하고, 효율적인 구현체(ArrayDeque)를 선택하는 것이 중요하다.