스택과 큐에 대해서 설명해 주세요.

데이터의 삽입과 삭제 순서를 제한하는 선형 자료구조로, 스택은 LIFO, 큐는 FIFO 방식으로 동작합니다.

스택 (Stack)

LIFO(Last In First Out) - 마지막에 넣은 것을 먼저 꺼냅니다.

push(1) → push(2) → push(3)

     [3]  ← top
     [2]
     [1]
     ---

pop() → 3 반환

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1);      // 삽입 - O(1)
stack.push(2);
stack.push(3);
stack.pop();        // 삭제 - O(1), 반환값: 3
stack.peek();       // 조회 - O(1), 삭제 없이 top 확인

큐 (Queue)

FIFO(First In First Out) - 먼저 넣은 것을 먼저 꺼냅니다.

enqueue(1) → enqueue(2) → enqueue(3)

front → [1] [2] [3] ← rear

dequeue() → 1 반환

Queue<Integer> queue = new LinkedList<>();

queue.offer(1);     // 삽입 - O(1)
queue.offer(2);
queue.offer(3);
queue.poll();       // 삭제 - O(1), 반환값: 1
queue.peek();       // 조회 - O(1), 삭제 없이 front 확인

시간복잡도

연산스택큐
삽입O(1)O(1)
삭제O(1)O(1)
조회 (top/front)O(1)O(1)
중간 접근O(n)O(n)

스택 vs 큐

항목스택큐
방식LIFOFIFO
삽입/삭제 위치한쪽 끝(top)양쪽 끝(rear/front)
주요 활용재귀, 뒤로가기, DFSBFS, 작업 대기열

활용 예시

// 스택 활용 - 괄호 유효성 검사
Deque<Character> stack = new ArrayDeque<>();
for (char c : "({[]})".toCharArray()) {
    if (c == '(' || c == '{' || c == '[') stack.push(c);
    else stack.pop(); // 짝이 맞으면 pop
}

// 큐 활용 - BFS 탐색
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int next : graph.get(node)) queue.offer(next);
}

Java에서는 Stack 클래스보다 ArrayDeque 사용을 공식 권장합니다. ArrayDeque는 스택과 큐 모두 구현 가능하며 성능도 더 우수합니다.

CSLOG에서 보기