[Java] Stack과 Queue: 기본 개념, 주요 차이점 및 활용 사례

1. Stack(스택)

1.1. 스택의 기본 개념

스택은 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 자료구조이다.
즉, 마지막에 추가된 데이터가 가장 먼저 제거되는 구조이다.

1.2. 스택의 주요 연산

• Push: 데이터를 스택의 맨 위에 추가하는 연산이다.
• Pop: 스택의 가장 위에서 데이터를 제거하고 반환하는 연산이다.
• Peek(Top): 스택의 가장 위에 있는 데이터를 제거하지 않고 확인하는 연산이다.
• isEmpty: 스택이 비어있는지 확인하는 연산이다.

1.3. 스택의 활용 사례

스택은 여러 상황에서 매우 유용하게 활용된다.
예를 들어, 함수 호출의 관리, 괄호의 짝이 올바른지 검사하는 알고리즘, 그리고 Undo 기능 구현 등에 사용된다.

1.4. 스택의 시각적 다이어그램

스택 구조 (LIFO)
┌─────┐
│  3  │   ← Top (마지막에 추가된 요소)
├─────┤
│  2  │
├─────┤
│  1  │   ← Bottom (가장 먼저 추가된 요소)
└─────┘

위 그림은 스택에 숫자 1, 2, 3을 순서대로 넣은 상태를 나타낸다.
스택의 가장 위에서부터 Pop 연산을 수행하면 3부터 제거된다.

1.5. Stack 주요 메서드

메서드	설명	반환 결과 / 동작	특징 및 주의 사항
push(E item)	스택의 맨 위에 요소를 추가한다.	void (추가 후 특별한 반환 값 없음)	후입선출(LIFO) 구조에 따라 마지막에 추가된 요소가 맨 위가 된다.
pop()	스택의 맨 위 요소를 제거하고 반환한다.	제거된 요소를 반환 (E)	스택이 비어 있으면 EmptyStackException 발생.
peek()	스택의 맨 위 요소를 조회한다 (제거하지 않음).	스택의 최상단 요소 (E) 반환	단순 조회이므로 스택 상태는 변하지 않는다.
isEmpty()	스택이 비어있는지 확인한다.	boolean (true: 비어있음, false: 요소 존재)	스택 사용 전후 상태 확인에 유용하다.
search(Object o)	스택에서 특정 요소의 위치를, Top에서부터 1부터 시작하는 인덱스로 반환한다.	요소가 존재하면 Top부터 몇 번째 위치인지 (정수), 없으면 -1 반환	위치는 Top 기준이며, 내부 구현에 따라 성능 차이가 있을 수 있다.

 

---

2. Queue(큐)

2.1. 큐의 기본 개념

큐는 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 자료구조이다.
즉, 먼저 추가된 데이터가 가장 먼저 제거되는 구조이다.

2.2. 큐의 주요 연산

• add/offer: 데이터를 큐의 뒤쪽(rear)에 추가하는 연산이다.
• remove/poll: 큐의 앞쪽(front)에서 데이터를 제거하고 반환하는 연산이다.
• Peek(Front): 큐의 가장 앞쪽 데이터를 제거하지 않고 확인하는 연산이다.
• isEmpty: 큐가 비어있는지 확인하는 연산이다.

2.3. 큐의 활용 사례

큐는 프로세스 스케줄링, 너비 우선 탐색(BFS) 등 다양한 알고리즘에서 활용된다.
또한, 이벤트 큐나 데이터 스트림 처리에서도 중요한 역할을 한다.

2.4. 큐의 시각적 다이어그램

큐 구조 (FIFO)
┌─────┐      ← Front (먼저 들어간 요소)
│  1  │
├─────┤
│  2  │
├─────┤
│  3  │      ← Rear (마지막에 추가된 요소)
└─────┘

위 그림은 큐에 숫자 1, 2, 3이 순서대로 들어간 상태를 나타낸다.
Dequeue 연산을 수행하면 가장 먼저 들어간 1부터 제거된다.

2.5. Queue 주요 메서드

메서드	설명	반환 결과 / 동작	특징 및 주의 사항
add(E item)	큐의 뒤쪽(Rear)에 요소를 추가한다.	추가 성공 시 true 반환, 큐가 꽉 찼을 경우 예외 발생	실패 시 예외를 발생시키므로, 큐 용량 제한이 있는 경우 주의해야 한다.
offer(E item)	큐의 뒤쪽에 요소를 추가한다. (add와 동일한 기능이나 예외 대신 false를 반환)	추가 성공 시 true, 실패 시 false 반환	add와 달리 큐가 꽉 찼을 때 예외를 발생시키지 않고 false를 반환한다.
remove()	큐의 앞쪽(Front)의 요소를 제거하고 반환한다.	제거된 요소 반환 (E)	빈 큐일 경우 NoSuchElementException 발생.
poll()	큐의 앞쪽 요소를 제거하고 반환한다.	제거된 요소 반환 (E), 빈 큐일 경우 null 반환	remove()와 달리 빈 큐에서 예외 대신 null을 반환하여 안전하게 사용할 수 있다.
peek()	큐의 앞쪽 요소를 조회한다 (제거하지 않음).	큐의 front 요소 (E) 반환, 빈 큐일 경우 null 반환	단순 조회이므로 큐 상태는 변하지 않는다.
isEmpty()	큐가 비어있는지 확인한다.	boolean (true: 비어있음, false: 요소 존재)	큐 사용 전후 상태 확인에 유용하다.

---

3. Stack과 Queue의 주요 차이점

아래 표는 스택과 큐의 차이점을 비교한 것이다.

항목	Stack (스택)	Queue (큐)
순서	후입선출(LIFO)	선입선출(FIFO)
데이터 추가	Push: 맨 위에 추가	Enqueue: 뒤쪽에 추가
데이터 제거	Pop: 맨 위에서 제거	Dequeue: 앞쪽에서 제거
사용 사례	함수 호출 관리, 괄호 검사, Undo 기능 등	프로세스 스케줄링, BFS, 이벤트 처리 등
구현 방식	배열, 연결 리스트 등을 사용하여 구현	배열, 연결 리스트 등을 사용하여 구현

---

4. 실제 코딩 테스트에서의 활용 예제

4.1. 스택을 이용한 괄호 검사 예제

import java.util.Stack;

class Solution {
    public boolean solution(String s) {
        // 스택 생성: 괄호의 짝을 맞추기 위한 용도로 사용한다.
        Stack<Character> stack = new Stack<>();
        
        // 문자열의 각 문자를 순회한다.
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 만약 현재 문자가 '('이면 스택에 추가한다.
            if (c == '(') {
                stack.push(c);
            } else { // 현재 문자가 ')'이면
                // 스택이 비어있으면 올바르지 않은 괄호 문자열이다.
                if (stack.isEmpty()) {
                    return false;
                }
                // 스택에서 가장 최근에 추가된 '('를 제거하여 짝을 맞춘다.
                stack.pop();
            }
        }
        // 모든 문자를 처리한 후, 스택이 비어있다면 괄호가 올바르게 짝지어진 것이다.
        return stack.isEmpty();
    }
}

 

해설:
문자열을 처음부터 끝까지 순회하면서 여는 괄호는 스택에 추가하고, 닫는 괄호가 나오면 스택에서 가장 최근에 추가된 여는 괄호와 매칭하여 제거한다.
순회 중에 스택이 비어있는 상태에서 닫는 괄호가 나오면 괄호의 순서가 올바르지 않으므로 false를 반환하며, 모든 처리가 끝난 후 스택이 비어있어야 올바른 괄호 문자열이다.

 

4.2. 큐를 이용한 BFS 예제

import java.util.LinkedList;
import java.util.Queue;

class BFSSolution {
    public void bfs(int start, int[][] graph) {
        // 큐 생성: 너비 우선 탐색(BFS)에 사용된다.
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        
        // 시작 노드를 큐에 추가하고 방문 처리한다.
        queue.add(start);
        visited[start] = true;
        
        // 큐가 빌 때까지 반복하면서 노드를 방문한다.
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            
            // 현재 노드의 모든 인접 노드를 검사하여 아직 방문하지 않았다면 큐에 추가한다.
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

 

해설:
큐를 사용하여 그래프의 노드를 선입선출 방식으로 방문하는 너비 우선 탐색(BFS) 알고리즘을 구현하였다.
먼저 시작 노드를 큐에 넣고 방문 처리한 후, 큐에서 노드를 하나씩 꺼내 인접한 노드를 검사하고, 아직 방문하지 않은 노드를 큐에 추가하는 방식으로 진행된다.

---

5. 결론

Stack과 Queue는 각각 후입선출(LIFO)과 선입선출(FIFO) 원칙을 기반으로 데이터를 처리하는 자료구조이다.

• **Stack(스택)**은 함수 호출 관리, 괄호 검사, Undo 기능 등에서 효과적으로 사용된다.
• **Queue(큐)**는 프로세스 스케줄링, BFS, 이벤트 큐 등에서 필수적으로 활용된다.