[Java] 기초 - Queue, Stack, Deque

이지연·2025년 12월 15일

백엔드(Java, 알고리즘, spring)

목록 보기

12/89

개요

아래의 내용은 java_grammer 레파지토리 C01Basic 디렉터리에 저장되어있는 내용을 정리하였다.

C13QueueStackDeque.java

Queue

Queue는 선입선출(FIFO) 구조로, 가장 먼저 들어간 데이터가 먼저 나간다.
주요 구현체: LinkedList(일반 큐), ArrayBlockingQueue(길이제한), PriorityQueue(우선순위)

Queue<Integer> myQue = new LinkedList<>();
myQue.add(10);    // 뒤에 추가
myQue.add(20);
myQue.add(30);
System.out.println("Queue Before: " + myQue);  // [10, 20, 30]

int value1 = myQue.poll();  // 앞에서 꺼냄 (10)
System.out.println("poll: " + value1);
System.out.println("Queue After poll: " + myQue);  // [20, 30]

int value2 = myQue.peek();  // 앞에서 확인만 (20, 삭제X)
System.out.println("peek: " + value2);

주요 메서드 비교

메서드	기능	삭제 여부	예외 처리
`add()`	뒤에 추가	-	용량 초과 시 예외
`offer()`	뒤에 추가	-	용량 초과 시 무시
`poll()`	앞에서 꺼냄	O	비어있으면 null
`peek()`	앞에서 확인	X	비어있으면 null

// 프린터 큐 예시
Queue<String> printerQueue = new LinkedList<>();
printerQueue.add("문서1"); printerQueue.add("문서2"); 
printerQueue.add("문서3");
while (!printerQueue.isEmpty()) {
    System.out.println("프린트: " + printerQueue.poll());
}

LinkedList vs ArrayList 성능

중간 삽입 테스트 (10만개 데이터 0번 인덱스에 삽입):

// LinkedList: O(1) per 삽입 → 총 O(N)
LinkedList<Integer> llist = new LinkedList<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    llist.add(0, i);  // 맨 앞 삽입
}
System.out.println("LinkedList: " + (System.currentTimeMillis() - start1));

// ArrayList: O(N) per 삽입 → 총 O(N²)
ArrayList<Integer> alist = new ArrayList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    alist.add(0, i);  // 맨 앞 삽입 (재배치 발생)
}
System.out.println("ArrayList: " + (System.currentTimeMillis() - start2));
// 결과: LinkedList(~16ms) << ArrayList(~362ms)

ArrayBlockingQueue (길이제한 큐)

고정 용량 큐로, 초과 시 예외/무시 처리 선택 가능

Queue<String> blockingQueue = new ArrayBlockingQueue<>(3);
blockingQueue.offer("문서1");  // 무시하지 않고 추가
blockingQueue.offer("문서2");
blockingQueue.offer("문서3");
blockingQueue.offer("문서4");  // 3개까지만 저장, 4번 무시
System.out.println("BlockingQueue: " + blockingQueue);  // [문서1, 문서2, 문서3]

PriorityQueue (우선순위 큐)

힙 구조로 poll 시 항상 최소/최대값 보장. 실시간 정렬 유지에 최적

// 최소힙 (작은 값 먼저)
Queue<Integer> pq = new PriorityQueue<>();
pq.add(30); pq.add(20); pq.add(10); pq.add(40);
System.out.println("pq: " + pq);  // [10, 20, 30, 40] (힙 구조)
while (!pq.isEmpty()) {
    System.out.println("poll: " + pq.poll());  // 10, 20, 30, 40 순
}

// 최대힙 (큰 값 먼저)
Queue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
pq2.add(30); pq2.add(20); pq2.add(10);
while (!pq2.isEmpty()) {
    System.out.println("max poll: " + pq2.poll());  // 30, 20, 10 순
}

복잡도: add/poll/peek 모두 O(log N). 실시간 최소값 추출에 특화

Stack

Stack은 후입선출(LIFO) 구조로, 마지막에 들어간 데이터가 먼저 나온다.
"바로 직전 값 확인" 문제가 많아 재귀/괄호 짝짓기 등에 자주 사용된다.

Stack<Integer> myStack = new Stack<>();
myStack.push(10);  // 스택 위에 추가
myStack.push(20);
myStack.push(30);
System.out.println(myStack.pop());  // 30 (마지막 들어간 것 먼저)
System.out.println(myStack);        // [10, 20]

주요 메서드:
| 메서드 | 기능 | 삭제 여부 |
|--------|------|-----------|
| push() | 위에 추가 | - |
| pop() | 위에서 꺼냄 | O |
| peek() | 위 확인 | X |

Deque (양방향 큐)

Deque(Double Ended Queue)는 양쪽 끝에서 추가/삭제가 가능한 고성능 구조다.
큐+스택 기능 모두 지원하며 성능 우수.

Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(10);   // 오른쪽 추가
dq.addLast(20);
dq.addFirst(30);  // 왼쪽 추가
System.out.println(dq);  // [30, 10, 20]

System.out.println(dq.pollLast());  // 20 (오른쪽 꺼냄)
System.out.println(dq.pollFirst()); // 30 (왼쪽 꺼냄)
System.out.println(dq.peekFirst()); // 10 (왼쪽 확인만)

Deque 주요 메서드

위치	추가	꺼냄	확인
왼쪽(앞)	`addFirst()`	`pollFirst()`	`peekFirst()`
오른쪽(뒤)	`addLast()`	`pollLast()`	`peekLast()`

// 활용 예시: 양방향 큐로 스택/큐 모두 구현 가능
Deque<Integer> stack = new ArrayDeque<>();  // 스택처럼
stack.addLast(1); stack.addLast(2); stack.pop();  // 2 꺼냄

Deque<Integer> queue = new ArrayDeque<>();  // 큐처럼  
queue.addLast(1); queue.addLast(2); queue.pollFirst();  // 1 꺼냄