본문 바로가기
[이직 면접] 질의 응답

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

by 막개발자 2020. 12. 29.

# 질의 응답 상황

[면접관]

지원자님 자료 구조 중 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) 방식으로, 먼저 들어온 데이터가 먼저 처리됩니다.

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