[자료구조] 스택과 큐(Stack & Queue)

스택(Stack)과 큐(Queue)

스택과 큐는 데이터를 저장하고 처리하는 기본적인 자료구조로, 각기 다른 데이터 처리 방식과 특징을 가진다.

---

스택(Stack)

스택이란?

• 정의: 데이터를 후입선출(LIFO, Last In First Out) 방식으로 처리하는 자료구조
• 구조:
  - 데이터를 넣는 작업: push
  - 데이터를 꺼내는 작업: pop
  - 가장 위의 데이터를 확인하는 작업: peek 또는 top

---

스택의 특징

• 후입선출(LIFO): 마지막에 삽입된 데이터가 가장 먼저 제거된다.
• 한쪽 끝에서만 삽입과 삭제가 가능하다.

---

스택의 활용 예시

1. 괄호 검사: 수식의 괄호가 올바르게 닫혔는지 확인

2. DFS(깊이 우선 탐색): 그래프 탐색 시 경로를 추적

3. 백트래킹: 잘못된 경로를 되돌아갈 때

4. 호출 스택(Call Stack): 함수 호출의 흐름을 관리

---

스택(Stack)의 주요 메서드

Java에서 스택은 java.util.Stack 인터페이스를 구현하여 사용할 수 있다.

 

주요 메서드

• push(E item)
  - 스택에 데이터를 삽입한다.
  - 시간 복잡도: O(1)
• pop()
  - 스택에 최상단 데이터를 제거하고 반환한다.
  - 시간 복잡도: O(1)
• peek()
  - 스택의 최상단 데이터를 제거하지 않고 반환한다.
  - 시간 복잡도: O(1)
• isEmpty()
  - 스택이 비어있는지 여부를 확인한다.
• search(Obejct o)
  - 스택에서 특정 요소의 위치를 반환한다.

 

사용 예제

import java.util.Stack;
public class StackExample {
	public static void main(String[] args) {
    	Stack<Integer> stack = new Stack<>();
        
        stack.push(10); // 10 삽입
        stack.push(20); // 20 삽입
        stack.push(30); // 30 삽입
        
        System.out.println("Top element: " + stack.peek()); // 출력: 30
        System.out.println("Pop element: " + stack.pop()); // 출력: 30
        System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false
    }
}

---

스택의 시간 복잡도

연산	설명	시간 복잡도
push	데이터 삽입	O(1)
pop	최상단 데이터 제거 및 반환	O(1)
peek	최상단 데이터 확인	O(1)
isEmpty	스택이 비어있는지 확인	O(1)
search	특정 요소 위치 검색	O(n)

 

---

큐(Queue)

큐란?

• 정의: 데이터를 선입선출(FIFO, First In First Out) 방식으로 처리하는 자료구조
• 구조:
  - 데이터를 넣는 작업: enqueue
  - 데이터를 꺼내는 작업: dequeue

---

큐의 특징

• 선입선출(FIFO): 먼저 삽입된 데이터가 가장 먼저 제거된다.
• 두 개의 끝(Front, Rear)을 사용하여 삽입과 삭제가 이루어진다.

---

큐의 활용 예시

1. 프로세스 관리: 운영 체제에서 작업 스케줄링

2. BFS(너비 우선 탐색): 그래프 탐색 시 경로 추적

3. 데이터 스트림 처리: 실시간 데이터 처리(ex 메시지 큐)

4. 프린터 작업 대기열: 작업 요청 순서대로 처리

---

큐의 주요 메서드

Java에서 큐는 java.util.Queue 인터페이스를 구현하여 사용할 수 있다.

주로 LinkedList나 ArrayDeque 클래스를 활용하여 큐를 구현한다.

 

주요 메서드

• add(E e)
  - 큐에 데이터를 삽입한다.
  - 큐가 가득 찬 경우 예외를 발생시킨다.
  - 시간 복잡도: O(1)
• offer(E e)
  - 큐에 데이터를 삽입한다.
  - 삽입에 실패하면 false를 반환한다.
  - 시간 복잡도: O(1)
• poll()
  - 큐의 첫 번째 데이터를 제거하고 반환한다.
  - 큐가 비어있으면 null을 반환한다.
  - 시간 복잡도: O(1)
• remove()
  - 큐의 첫 번째 데이터를 제거하고 반환한다.
  - 큐가 비어있으면 에외를 발생시킨다.
  - 시간 복잡도: O(1)
• peek()
  - 큐의 첫 번째 데이터를 제거하지 않고 반환한다.
  - 큐가 비어있으면 null을 반환한다.
  - 시간 복잡도: O(1)
• element()
  - 큐의 첫 번째 데이터를 제거하지 않고 반환한다.
  - 큐가 비어있으면 예외를 발생시킨다.
  - 시간 복잡도: O(1)

 

사용 예제

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

public class QueueExample {
	public static void main(String[] args) {
    	Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(10); // 10 삽입
        queue.offer(20); // 20 삽입
        queue.offer(30); // 30 삽입
        
        System.out.println("Front element: " + queue.peek()); // 출력: 10
        System.out.println("Remove element: " + queue.poll()); // 출력: 10
        System.out.println("Is queue empty? " + queue.isEmpty()); // 출력: false
    }
}

---

큐의 시간 복잡도

연산	설명	시간 복잡도
add/offer	데이터 삽입	O(1)
poll/remove	첫 번째 데이터 제거 및 반환	O(1)
peek/element	첫 번째 데이터 확인	O(1)

 

---

스택과 큐의 비교

구분	스택(Stack)	큐(Queue)
데이터 처리	후입선출(LIFO)	선입선출(FIFO)
삽입/삭제	한쪽 끝에서만 가능	삽입은 Rear, 삭제는 Front에서 가능
활용 예시	DFS, 괄호 검사, 백트래킹	BFS, 작업 대기열, 실시간 데이터 처리