[자료구조] 스택과 큐

스택(Stack)

스택이란?

• LIFO(Last In, First Out) 구조를 가지는 자료구조
  • 마지막에 삽입된 데이터가 가장 먼저 제거되는 특성

사용 사례

• 함수 호출 스택 관리
• 웹 브라우저의 뒤로 가기/앞으로 가기 기능
• 수식 계산(예: 후위 표기법)

주요 연산

• push : 데이터를 스택에 삽입
• pop : 스택의 가장 상단 데이터를 제거하고 반환
• peek(또는 top) : 스택의 상단 데이터를 제거하지 않고 반환
• isEmpty : 스택이 비어 있는지 확인
• size : 스택의 크기 반환

예시 코드( 전용 클래스 활용 )

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Stack: " + stack); // [10, 20, 30]

        System.out.println("Top Element: " + stack.peek()); // 30
        System.out.println("Popped Element: " + stack.pop()); // 30
        System.out.println("Stack after pop: " + stack); // [10, 20]
    }
}

예시 코드( Array 활용 )

class CustomStack {
    private int[] stack; // 스택 데이터를 저장할 배열
    private int top; // 스택의 최상단 요소를 가리키는 변수
    private int size; // 스택의 최대 크기

    public CustomStack(int size) {
        this.size = size;
        this.stack = new int[size]; // 지정된 크기의 배열 생성
        this.top = -1; // 초기값 -1 (스택이 비어 있음)
    }

    // Push: 스택에 요소 추가
    public void push(int value) {
        if (top == size - 1) { // 스택이 가득 찬 경우
            throw new StackOverflowError("스택이 가득 찼습니다!");
        }
        stack[++top] = value; // top을 증가시키고 값을 저장
    }

    // Pop: 스택의 최상단 요소 제거 및 반환
    public int pop() {
        if (isEmpty()) { // 스택이 비어 있는 경우
            throw new IllegalStateException("스택이 비어 있습니다!");
        }
        return stack[top--]; // 최상단 요소 반환 후 top 감소
    }

    // Peek: 최상단 요소를 확인 (제거하지 않음)
    public int peek() {
        if (isEmpty()) { // 스택이 비어 있는 경우
            throw new IllegalStateException("스택이 비어 있습니다!");
        }
        return stack[top]; // 최상단 요소 반환
    }

    // 스택이 비어 있는지 확인
    public boolean isEmpty() {
        return top == -1; // top이 -1이면 스택이 비어 있음
    }

    // 스택이 가득 찼는지 확인
    public boolean isFull() {
        return top == size - 1; // top이 배열 크기의 마지막 인덱스에 도달했는지 확인
    }
}

public class StackTest {
    public static void main(String[] args) {
        CustomStack stack = new CustomStack(5); // 크기 5의 스택 생성
        stack.push(10); // 스택에 10 추가
        stack.push(20); // 스택에 20 추가
        stack.push(30); // 스택에 30 추가
        System.out.println("최상단 요소: " + stack.peek()); // 30
        System.out.println("제거된 요소: " + stack.pop()); // 30
        System.out.println("최상단 요소 (제거 후): " + stack.peek()); // 20
    }
}

예시 코드( LinkedList 활용 )

import java.util.LinkedList;

class LinkedListStack {
    private LinkedList<Integer> stack;

    public LinkedListStack() {
        stack = new LinkedList<>();
    }

    // Push: 요소를 스택에 추가
    public void push(int value) {
        stack.addLast(value); // LinkedList의 마지막에 요소 추가
    }

    // Pop: 최상단 요소를 제거 및 반환
    public int pop() {
        if (stack.isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다!");
        }
        return stack.removeLast(); // LinkedList의 마지막 요소 제거 및 반환
    }

    // Peek: 최상단 요소를 확인 (제거하지 않음)
    public int peek() {
        if (stack.isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다!");
        }
        return stack.getLast(); // LinkedList의 마지막 요소 반환
    }

    // 스택이 비어 있는지 확인
    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

public class LinkedListStackTest {
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("최상단 요소: " + stack.peek()); // 30
        System.out.println("제거된 요소: " + stack.pop()); // 30
        System.out.println("최상단 요소 (제거 후): " + stack.peek()); // 20
    }
}

스택의 변형 형태

이중 스택(Double Stack)

• 정의
  • 하나의 배열을 양쪽 끝에서 사용하여 두 개의 스택을 구현
  • 배열의 앞쪽과 뒤쪽에서 데이터를 각각 쌓아올림
• 특징
  • 메모리를 효율적으로 사용하며, 공간 낭비를 최소화
  • 두 스택이 중앙에서 충돌하지 않도록 관리해야 함
• 활용 사례
  • 제한된 메모리 환경에서 다중 스택 관리

예시 코드

class DoubleStack {
    private int[] arr;
    private int top1, top2;

    public DoubleStack(int size) {
        arr = new int[size];
        top1 = -1;
        top2 = size;
    }

    public void push1(int data) {
        if (top1 + 1 < top2) {
            arr[++top1] = data;
        } else {
            throw new StackOverflowError("Stack1 Overflow");
        }
    }

    public void push2(int data) {
        if (top1 + 1 < top2) {
            arr[--top2] = data;
        } else {
            throw new StackOverflowError("Stack2 Overflow");
        }
    }

    public int pop1() {
        if (top1 >= 0) {
            return arr[top1--];
        } else {
            throw new IllegalStateException("Stack1 Underflow");
        }
    }

    public int pop2() {
        if (top2 < arr.length) {
            return arr[top2++];
        } else {
            throw new IllegalStateException("Stack2 Underflow");
        }
    }
}

최소/최대 스택(Min/Max Stack)

• 정의
  • 최소값 또는 최대값을 O(1) 시간 복잡도로 반환할 수 있는 스택
• 특징
  • 보조 스택을 사용하여 최소값 또는 최대값을 관리
  • push 연산 시 보조 스택에 최소값 또는 최대값을 업데이트
• 활용 사례
  • 알고리즘 문제(예: 주어진 스택에서 최솟값 찾기)

예시 코드

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int data) {
        stack.push(data);
        if (minStack.isEmpty() || data <= minStack.peek()) {
            minStack.push(data);
        }
    }

    public int pop() {
        if (stack.isEmpty()) {
            throw new IllegalStateException("Stack Underflow");
        }
        int data = stack.pop();
        if (data == minStack.peek()) {
            minStack.pop();
        }
        return data;
    }

    public int getMin() {
        if (minStack.isEmpty()) {
            throw new IllegalStateException("No elements in stack");
        }
        return minStack.peek();
    }
}

---

큐(Queue)

큐란?

• 큐는 FIFO(First In, First Out) 구조를 가지는 자료구조
  • 먼저 삽입된 데이터가 가장 먼저 제거

사용 사례

• BFS(너비 우선 탐색)
• 작업 스케줄링
• 프린터 작업 관리

주요 연산

• add : 데이터를 큐에 삽입
• dequeue : 큐에서 가장 앞 데이터를 제거하고 반환
• peek : 큐의 가장 앞 데이터를 제거하지 않고 반환
• isEmpty : 큐가 비어 있는지 확인
• size : 큐의 크기 반환
• contains : 큐에 특정 데이터가 포함되어 있는지 확인

예시 코드 ( 전용 클래스 활용 )

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        System.out.println("Queue: " + queue); // [10, 20, 30]

        System.out.println("Front Element: " + queue.peek()); // 10
        System.out.println("Dequeued Element: " + queue.poll()); // 10
        System.out.println("Queue after dequeue: " + queue); // [20, 30]
        System.out.println("Queue contains 10?:  " + queue.contains(10); // false 
    }
}

예시 코드 ( Array 활용 )

class CustomQueue {
    private int[] queue; // 큐 데이터를 저장할 배열
    private int front; // 큐의 앞쪽 요소를 가리키는 인덱스
    private int rear; // 큐의 마지막 요소를 가리키는 인덱스
    private int size; // 큐의 최대 크기
    private int count; // 현재 큐에 저장된 요소의 개수

    public CustomQueue(int size) {
        this.size = size;
        this.queue = new int[size]; // 지정된 크기의 배열 생성
        this.front = 0; // 초기값 0 (큐의 시작 위치)
        this.rear = -1; // 초기값 -1 (요소가 없음)
        this.count = 0; // 현재 요소 개수 0
    }

    // Enqueue: 큐에 요소 추가
    public void enqueue(int value) {
        if (isFull()) { // 큐가 가득 찬 경우
            throw new IllegalStateException("큐가 가득 찼습니다!");
        }
        rear = (rear + 1) % size; // rear를 순환 구조로 업데이트
        queue[rear] = value; // 새로운 요소 추가
        count++; // 요소 개수 증가
    }

    // Dequeue: 큐의 앞쪽 요소 제거 및 반환
    public int dequeue() {
        if (isEmpty()) { // 큐가 비어 있는 경우
            throw new IllegalStateException("큐가 비어 있습니다!");
        }
        int value = queue[front]; // front에 있는 요소 저장
        front = (front + 1) % size; // front를 순환 구조로 업데이트
        count--; // 요소 개수 감소
        return value; // 제거된 요소 반환
    }

    // Peek: 큐의 앞쪽 요소 확인 (제거하지 않음)
    public int peek() {
        if (isEmpty()) { // 큐가 비어 있는 경우
            throw new IllegalStateException("큐가 비어 있습니다!");
        }
        return queue[front]; // front에 있는 요소 반환
    }

    // 큐가 비어 있는지 확인
    public boolean isEmpty() {
        return count == 0; // 요소 개수가 0이면 큐가 비어 있음
    }

    // 큐가 가득 찼는지 확인
    public boolean isFull() {
        return count == size; // 요소 개수가 큐의 크기와 같으면 가득 참
    }
}

public class QueueTest {
    public static void main(String[] args) {
        CustomQueue queue = new CustomQueue(5); // 크기 5의 큐 생성
        queue.enqueue(10); // 큐에 10 추가
        queue.enqueue(20); // 큐에 20 추가
        queue.enqueue(30); // 큐에 30 추가
        System.out.println("큐의 앞쪽 요소: " + queue.peek()); // 10
        System.out.println("제거된 요소: " + queue.dequeue()); // 10
        System.out.println("큐의 앞쪽 요소 (제거 후): " + queue.peek()); // 20
    }
}

예시 코드 ( LinkedList 활용 )

import java.util.LinkedList;

class LinkedListQueue {
    private LinkedList<Integer> queue;

    public LinkedListQueue() {
        queue = new LinkedList<>();
    }

    // Enqueue: 큐에 요소 추가
    public void enqueue(int value) {
        queue.addLast(value); // LinkedList의 마지막에 요소 추가
    }

    // Dequeue: 큐의 앞쪽 요소 제거 및 반환
    public int dequeue() {
        if (queue.isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다!");
        }
        return queue.removeFirst(); // LinkedList의 첫 번째 요소 제거 및 반환
    }

    // Peek: 큐의 앞쪽 요소 확인 (제거하지 않음)
    public int peek() {
        if (queue.isEmpty()) {
            throw new IllegalStateException("큐가 비어 있습니다!");
        }
        return queue.getFirst(); // LinkedList의 첫 번째 요소 반환
    }

    // 큐가 비어 있는지 확인
    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

public class LinkedListQueueTest {
    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("큐의 앞쪽 요소: " + queue.peek()); // 10
        System.out.println("제거된 요소: " + queue.dequeue()); // 10
        System.out.println("큐의 앞쪽 요소 (제거 후): " + queue.peek()); // 20
    }
}

큐의 변형 형태

원형 큐(Circular Queue)

정의

• 큐가 배열의 끝에서 다시 시작점을 연결하여 빈 공간을 활용하는 큐
• 선형 큐의 메모리 낭비 문제를 해결

• 특징
  • front와 rear 포인터 사용
  • (rear + 1) % capacity로 다음 삽입 위치 계산
• 활용 사례
  • 제한된 메모리 환경에서 데이터 스트리밍 처리

예시 코드

class CircularQueue {
    private int[] queue;
    private int front, rear, size, capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    public boolean enqueue(int data) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        queue[rear] = data;
        size++;
        return true;
    }

    public int dequeue() {
        if (isEmpty()) throw new IllegalStateException("Queue is empty");
        int data = queue[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

덱(Deque: Double-Ended Queue)

• 정의
  • 양쪽 끝에서 삽입과 삭제가 가능한 큐
• 특징
  • enqueueFront와 enqueueRear로 데이터를 삽입
  • dequeueFront와 dequeueRear로 데이터를 삭제
• 활용 사례
  • 브라우저의 뒤로 가기/앞으로 가기 기능
  • 슬라이딩 윈도우 알고리즘

---

구현 방식에 따른 특징

---

면접 대비질문

기본 질문

1. 스택과 큐의 차이점을 설명해보세요.
   • 모범 답안:
     • 스택은 LIFO(Last In, First Out) 구조로, 마지막에 삽입된 데이터가 가장 먼저 제거됩니다. 큐는 FIFO(First In, First Out) 구조로, 먼저 삽입된 데이터가 먼저 제거됩니다.
     • 스택은 웹 브라우저의 뒤로 가기 기능, 함수 호출 관리에 사용되며, 큐는 BFS 탐색, 작업 스케줄링에 주로 사용됩니다.
2. 스택과 큐의 시간 복잡도에 대해 설명하세요.
   • 모범 답안:
     • 스택:
       • push와 pop 연산은 O(1).
       • peek 연산도 O(1).
     • 큐:
       • enqueue와 dequeue 연산은 O(1).
       • 배열 기반 큐의 경우, 크기를 초과하면 배열 재할당에 O(n) 비용이 발생할 수 있습니다.
3. 스택이 사용되는 대표적인 사례를 3가지 이상 말해보세요.
   • 모범 답안:
     1. 함수 호출 시 호출 스택 관리.
     2. 웹 브라우저의 뒤로 가기/앞으로 가기 기능.
     3. 후위 표기법 계산.
4. 큐와 연결리스트(Linked List)의 차이점은 무엇인가요?
   • 모범 답안:
     • 큐는 FIFO 구조로 동작하며, 보통 데이터 삽입과 제거 연산이 제한됩니다.
     • 연결 리스트는 노드로 연결된 일반적인 자료구조로, 삽입/삭제가 자유롭습니다.
     • 큐는 FIFO 규칙을 유지하기 위해 연결 리스트를 내부적으로 사용할 수 있습니다.
5. 스택과 큐의 구현 방식 차이를 설명하세요.
   • 모범 답안:
     • 스택은 배열 기반이나 Stack 클래스를 이용하여 구현합니다.
     • 큐는 Queue 인터페이스를 사용하며, 보통 LinkedList나 ArrayDeque를 활용합니다. 이때, LinkedList는 동적 메모리를 사용하고, ArrayDeque는 배열 기반입니다.

---

심화 및 압박 질문

1. 스택의 크기를 제한했을 때, overflow를 방지할 방법은 무엇인가요?
   • 모범 답안:
     • 스택의 최대 크기를 설정하고 push 연산 시 크기 제한을 초과하는지 확인합니다.
     • 메모리가 부족할 경우, 예외를 발생시키거나 적절한 처리를 통해 스택 확장을 구현합니다.
     • 동적 크기 조정이 필요한 경우 배열 대신 LinkedList를 사용합니다.
2. 큐에서 순환 큐(Circular Queue)의 장점과 구현 방법에 대해 설명하세요.
   • 모범 답안:
     • 순환 큐는 배열 기반 큐에서 메모리 낭비를 줄이고 빈 공간을 재활용합니다.
     • front와 rear 포인터를 사용하여 배열 끝과 시작을 연결해 순환 구조를 만듭니다.
     • (rear + 1) % capacity와 같은 연산을 사용해 삽입 위치를 결정합니다.
     • 삽입/삭제 연산은 O(1)의 시간 복잡도를 가집니다.
3. 스택을 사용해 큐를 구현하려면 어떻게 해야 하나요? (구현 로직 및 성능 분석 포함)
   • 모범 답안:
     • 두 개의 스택을 사용합니다.
     • 삽입 연산(enqueue)은 첫 번째 스택에 데이터를 추가합니다(O(1)).
     • 삭제 연산(dequeue)은 첫 번째 스택에서 두 번째 스택으로 데이터를 옮기고, 두 번째 스택의 최상단 데이터를 제거합니다(O(n)).
4. 큐를 사용해 스택을 구현하려면 어떻게 해야 하나요? (구현 로직 및 성능 분석 포함)
   • 모범 답안:
     • 두 개의 큐를 사용합니다.
     • 삽입 연산(push) 시 새 데이터를 빈 큐에 삽입한 후, 기존 데이터를 모두 옮겨 스택의 순서를 유지합니다(O(n)).
     • 삭제 연산(pop)은 큐의 맨 앞 데이터를 제거합니다(O(1)).
5. 주어진 데이터가 매우 크고 제한된 메모리 공간에서 큐를 구현해야 한다면 어떤 접근 방식을 사용할 수 있을까요?
   • 모범 답안:
     • 외부 저장소 활용: 데이터가 메모리에 적합하지 않으면 파일 시스템이나 데이터베이스를 사용합니다.
     • 메모리 맵(Map) 활용: 필요한 데이터만 메모리에 로드하고 나머지는 디스크에 저장합니다.
     • 순환 큐: 제한된 메모리를 최대한 효율적으로 사용합니다.
6. 프로세스 스케줄링에서 큐를 사용할 때 우선순위 큐(Priority Queue)로 변경하면 어떤 장점이 있나요?
   • 모범 답안:
     • 우선순위 큐를 사용하면 중요한 작업이 먼저 처리됩니다.
     • 일반 큐에서는 도착 순서대로 처리되지만, 우선순위 큐는 중요도에 따라 효율적으로 자원을 분배합니다.
     • 우선순위 큐는 힙(Heap)을 사용해 구현되며, 삽입/삭제 연산에서 O(log n)의 시간 복잡도를 가집니다.
7. 스택과 큐를 활용한 BFS와 DFS의 차이를 설명하세요.
   • 모범 답안:
     • BFS는 큐를 사용하며, 현재 노드와 인접한 모든 노드를 먼저 탐색한 후 다음 레벨로 이동합니다.
     • DFS는 스택을 사용하며, 현재 노드의 한 방향으로 끝까지 탐색한 뒤 돌아옵니다.
8. 스택 오버플로우(Stack Overflow)란 무엇인가요?
   • 모범 답안:
     • 스택 오버플로우는 스택 메모리의 크기를 초과하여 데이터를 삽입할 때 발생하는 오류입니다. 주로 재귀 함수 호출이 너무 깊거나 스택 크기를 고려하지 않고 무한 데이터를 삽입했을 때 발생합니다.
9. 우선순위 큐와 일반 큐의 차이점을 설명해보세요.
   • 모범 답안:
     • 일반 큐는 FIFO 구조를 따르며, 삽입된 순서대로 데이터를 처리합니다.
     • 우선순위 큐는 각 데이터에 우선순위를 부여하여 높은 우선순위를 가진 데이터가 먼저 처리됩니다. 이를 위해 힙(Heap) 자료구조를 활용합니다.

---

Reference

https://www.geeksforgeeks.org/introduction-to-stack-data-structure-and-algorithm-tutorials/

https://www.geeksforgeeks.org/queue-data-structure/?ref=header_outind