[자료 구조] Stack과 Queue의 차이점과 구현 방법

# 질의 응답 상황

[면접관]

지원자님 자료 구조 중 Stack과 Queue에 대해서 간략하게 설명해주세요.

 

[막개발자] 

Stack은 데이터를 LIFO(Last In, First Out) 순서로 다루는 자료 구조로, TOP 방향으로만 데이터를 삽입하고 삭제할 수 있습니다. 예를 들어, 브라우저 방문 기록이나 undo 기능이 이에 해당합니다. Queue는 데이터를 FIFO(First In, First Out) 순서로 처리하며, Rear 방향으로 데이터를 삽입하고 Front 방향으로 데이터를 삭제합니다. 프린터 인쇄나 콜센터 대기 기능 등이 대표적인 예입니다.

 

 

# 상세 설명

1. 스택(Stack) 구현

**스택(Stack)**은 LIFO (Last In, First Out) 구조로, 가장 나중에 삽입된 데이터가 가장 먼저 제거되는 자료 구조입니다. 스택은 일반적으로 undo 기능, 브라우저의 뒤로 가기 버튼 등에서 사용됩니다.

import java.util.EmptyStackException;

class Stack<T> {
    private Node<T> top;

    private static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T data = top.data;
        top = top.next;
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Peek: " + stack.peek()); // 30
        System.out.println("Pop: " + stack.pop());  // 30
        System.out.println("Pop: " + stack.pop());  // 20
        System.out.println("Is Empty: " + stack.isEmpty()); // false
    }
}

스택의 주요 메서드:

• push: 데이터를 스택에 삽입.
• pop: 데이터를 스택에서 제거.
• peek: 스택의 최상위 요소 확인.
• isEmpty: 스택이 비었는지 확인.

2. 큐(Queue) 구현

**큐(Queue)**는 FIFO (First In, First Out) 구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다. 큐는 프린터 인쇄 대기열이나 콜센터 대기 기능에서 사용됩니다.

class Queue<T> {
    private Node<T> front;
    private Node<T> rear;

    private static class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (rear != null) {
            rear.next = newNode;
        }
        rear = newNode;
        if (front == null) {
            front = newNode;
        }
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println("Peek: " + queue.peek()); // 10
        System.out.println("Dequeue: " + queue.dequeue()); // 10
        System.out.println("Dequeue: " + queue.dequeue()); // 20
        System.out.println("Is Empty: " + queue.isEmpty()); // false
    }
}

큐의 주요 메서드:

• enqueue: 데이터를 큐에 삽입.
• dequeue: 큐에서 데이터를 제거.
• peek: 큐의 앞 요소 확인.
• isEmpty: 큐가 비었는지 확인.

주요 특징

• **스택(Stack)**은 push, pop, peek 메서드를 구현하여 데이터를 추가하거나 제거할 수 있습니다.
• **큐(Queue)**는 enqueue, dequeue, peek 메서드를 구현하여 데이터 삽입과 제거를 관리합니다.
• 두 자료 구조는 제네릭(Generic)을 사용하여 다양한 데이터 타입을 처리할 수 있습니다.

Stack과 Queue의 차이점

• Stack은 후입선출(LIFO) 방식으로, 데이터가 쌓여 올라간 순서의 반대로 처리됩니다.
• Queue는 선입선출(FIFO) 방식으로, 먼저 들어온 데이터가 먼저 처리됩니다.

이와 같이 Stack과 Queue는 각각의 특성에 맞는 자료 구조를 제공하여, 다양한 분야에서 효율적인 데이터 처리 및 관리가 가능합니다.