[자료구조] 스택과 큐

스택

후입 선출(LIFO, Last In First Out) 형태로 데이터를 저장하는 구조

• 여기서 가장 마지막에 넣은 3번이 가장 먼저 나온다. 
• 이렇게 나중에 넣은 것이 가장 먼저 나오는 것을 후입 선출이라 하고, 이런 자료 구조를 스택이라 한다.
• 블럭을 빼려면 위에서 부터 순서대로 빼야한다.

 

스택 주요 동작

• push: 데이터를 스택에 넣는 연산.
• pop: 스택에서 가장 마지막에 들어간 데이터를 꺼내는 연산.
• peek: 스택의 최상위 데이터를 제거하지 않고 반환하는 연산.

 

스택 사용 사례

• 스택 메모리
• 스택 프레임

 

장점

• 간단한 구현: 스택은 자료의 추가와 제거가 하나의 끝에서만 이루어지기 때문에 구현이 단순하다.
• 빠른 데이터 처리: 마지막에 추가된 데이터에 접근하는 것이 O(1)로 매우 빠르다.
• 재귀적 문제 해결: 재귀적인 구조의 문제를 스택으로 쉽게 해결할 수 있다. 예를 들어, 함수 호출 스택, 수식의 괄호 검사, DFS(깊이 우선 탐색) 등이 스택을 사용한다.

 

단점

• 접근 제한: 스택은 가장 마지막에 추가된 데이터만 접근할 수 있어, 중간 데이터에 직접 접근하기 어렵다.

 

코드 예시

public class StackExample {
    public static void main(String[] args) {
        // 스택 생성
        Stack<Integer> stack = new Stack<>();
        
        // 스택에 데이터 삽입 (push)
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        // 스택의 최상단 요소 보기 (peek)
        System.out.println("Peek: " + stack.peek());  // 출력: 30
        
        // 스택에서 데이터 제거 (pop)
        System.out.println("Pop: " + stack.pop());  // 출력: 30
        System.out.println("Pop: " + stack.pop());  // 출력: 20
        
        // 스택이 비었는지 확인
        if(stack.isEmpty()) {
            System.out.println("스택이 비었습니다.");
        } else {
            System.out.println("스택에 데이터가 있습니다.");
        }
    }
}

---

큐

선입 선출(FIFO, First In First Out) 형태로 데이터를 저장하는 구조

• 후입 선출과 반대로 가장 먼저 넣은 것이 가장 먼저 나오는 것을 선입 선출이라 한다. 
• 이런 자료 구조를 큐(Queue)라한다.

 

큐 주요 동작

• enqueue: 데이터를 큐에 추가하는 연산.
• dequeue: 큐에서 가장 먼저 들어온 데이터를 제거하고 반환하는 연산.
• peek: 큐의 맨 앞에 있는 데이터를 제거하지 않고 반환하는 연산.

 

장점

• 선입선출 구조: FIFO 특성 덕분에 순서대로 처리해야 하는 작업에 적합하다. 예를 들어, 작업 스케줄링이나 프린터 작업 대기열 등에서 유용하다.
• 중간 데이터 처리 불필요: 큐는 순차적으로 처리되므로, 중간 데이터를 직접 접근하지 않아도 된다.

 

단점

• 접근 제한: 큐의 앞이나 뒤의 데이터만 접근할 수 있고, 중간 데이터는 접근할 수 없다.

 

코드 예시

public class QueueExample {
    public static void main(String[] args) {
        // 큐 생성
        Queue<String> queue = new LinkedList<>();
        
        // 큐에 데이터 삽입 (enqueue)
        queue.offer("첫 번째");
        queue.offer("두 번째");
        queue.offer("세 번째");
        
        // 큐의 첫 번째 요소 보기 (peek)
        System.out.println("Peek: " + queue.peek());  // 출력: 첫 번째
        
        // 큐에서 데이터 제거 (dequeue)
        System.out.println("Dequeue: " + queue.poll());  // 출력: 첫 번째
        System.out.println("Dequeue: " + queue.poll());  // 출력: 두 번째
        
        // 큐가 비었는지 확인
        if(queue.isEmpty()) {
            System.out.println("큐가 비었습니다.");
        } else {
            System.out.println("큐에 데이터가 있습니다.");
        }
    }
}

---

스택(Stack)과 큐(Queue) 비교

특징	스택(Stack)	큐(Queue)
저장 방식	후입선출(LIFO): 마지막에 들어간 데이터가 먼저 나옴	선입선출(FIFO): 처음에 들어간 데이터가 먼저 나옴
주요 연산	push, pop, peek	enqueue, dequeue, peek
사용 예시	재귀 알고리즘, 함수 호출 스택, DFS 탐색	작업 대기열, BFS 탐색, 작업 스케줄링
데이터 접근 제한	마지막 데이터에만 접근 가능	첫 번째 데이터에만 접근 가능
장점	구현이 간단하고 빠름, 데이터 삽입/삭제가 빠름	FIFO 구조 덕분에 순서대로 처리하기 용이
단점	중간 데이터 접근 불가, 마지막 데이터만 처리 가능	중간 데이터 접근 불가, 첫 번째/마지막 데이터만 처리 가능

 

 

실제 사용 시 스택과 큐를 선택하는 기준

• 스택을 사용하는 경우:
  • 후입선출(LIFO) 방식으로 데이터를 처리해야 할 때 사용한다.
  • 재귀적 문제나 괄호 검사, 백트래킹 알고리즘처럼 마지막에 들어간 데이터를 먼저 처리해야 하는 경우 적합하다.
• 큐를 사용하는 경우:
  • 선입선출(FIFO) 방식이 필요한 경우 사용한다.
  • 작업 대기열이나 BFS와 같은 순차적 처리가 필요한 경우, 또는 여러 작업을 대기 상태에서 하나씩 처리해야 하는 경우 큐가 유용하다.

---