[Algorithm/Study] 2주차 - 스택과 큐

 

해당 스터디는 <코딩 테스트 합격자 되기 C++> 저자님과 함께하는 스터디입니다.

인프런 강의 < 코딩 테스트 합격자 되기 C++ > 을 보고 정리한 내용입니다.

---

 

 

스택의 개념

스택(Stack) : 가장 최근에 들어간 원소가 가장 먼저 나오는 자료구조, LIFO(Last In Fist Out) / FILO(First In Last Out)

Stack Data Structure and Implementation in Python, Java and C/C++ (programiz.com)

• DFS, 백트래킹에서 사용한다.
• "가장 최근 원소"를 봐야하는 경우에 사용한다. (중요!)

스택은 "가장 최근" 이라는 것에 키워드를 잡아보자!

1. 가장 최근에 들어온 원소를 알 수 있다.
2. 가장 최근에 들어온 원소 순으로 나온다.

스택의 ADT

❔ADT란?

• ADT(Abstract Data Type)는 추상 데이터 타입의 약어이다.
• 세부사항을 숨기고 사용자에게 필요한 기능만 명시한다.
• ADT를 사용하면 복잡한 자료구조의 내부 구현을 감추고, 필요한 연산만 정의함으로써 자료구조 동작 자체에 집중할 수 있다.

예시 ) 키보드를 구매할 때 키보드의 모든 세부 동작, 회로가 어떻게 동작하는지를 보고 하나하나 고민해서 고르진 않는다. 키보드가 잘 눌리는지, 촉감이 좋은지 등을 보고 고른다. ADT의 예로는 스택(Stack), 큐(Queue), 리스트(List), 트리(Tree), 그래프(Graph) 등이 있다.

 

강의 내에서는 C++로 설명해주시지만, 내가 주로 쓰는 언어는 Java와 Kotlin이기 때문에 해당 언어로 다시 정리해보았다. ADT는 프로그래밍 언어마다 조금씩 다르다.

Java

• push(E item) : 스택의 맨 위에 새로운 요소를 추가한다.
• pop() : 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환한다.
• peek() : 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
• isEmpty() : 스택이 비어있는지 확인한다.
• size() : 스택에 있는 요소의 개수를 반환한다.

Java에서 Stack 클래스는 오래되었고, 내부적으로 Vector를 기반으로 해 동기화가 필요하다. 따라서 현재는 스택을 구현할 때 Deque 인터페이스를 구현하는 ArrayDeque 클래스가  더 권장된다. 비동기화된 구조로 성능이 우수하고 스택과 큐 모두로 사용할 수 있다. 다음은 자바에서 ArrayDeque로 스택을 구현한 예시이다.

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeStackExample {
    public static void main(String[] args) {
        // ArrayDeque를 사용하여 스택 생성
        Deque<Integer> stack = new ArrayDeque<>();

        // Push 연산
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Peek 연산: 최상단 요소 확인
        System.out.println("Top element: " + stack.peek()); // 30

        // Pop 연산: 최상단 요소 제거
        System.out.println("Popped element: " + stack.pop()); // 30

        // Size 연산: 스택 크기 확인
        System.out.println("Stack size: " + stack.size()); // 2

        // isEmpty 연산: 스택이 비어있는지 확인
        System.out.println("Is stack empty? " + stack.isEmpty()); // false
    }
}

❔ Deque와 ArrayDeque의 차이

✔️ Deque는 인터페이스로, 스택과 큐의 기능을 모두 제공하는 메서드들을 포함하고 있다.

✔️ ArrayDeque는 Deque 인터페이스를 구현한 클래스 중 하나이다. 내부적으로 동적 배열을 사용한다.

❗인터페이스 타입(Deque)를 사용하여 변수를 선언하는 것은 유연성을 높이기 위해서이다. 인터페이스 타입으로 변수를 선언하면, 나중에 실체 구현 클래스를 바꾸더라도 코드의 나머지 부분을 바꾸지 않아도 된다.

Kotlin

Kotlin에서는 Stack 클래스를 제공하지 않는다. 자바의 Stack 클래스를 그래도 사용할 수 있지만 보통은 MutableList나 ArrayDeque를 사용한다.

• addLast(element) : 스택의 맨 위에 요소를 추가한다.(push)
• removeLast() : 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환한다.(pop)
• last() : 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.(peek)
• isEmpty() : 스택이 비어있는지 확인한다.
• size : 스택에 있는 요소의 개수를 반환한다.

다음은 코틀린에서 ArrayDeque로 스택을 구현한 예시이다.

fun main() {
    val stack = ArrayDeque<Int>()

    // Push 연산
    stack.addLast(10)
    stack.addLast(20)
    stack.addLast(30)

    // Peek 연산
    println("Top element: ${stack.last()}") // 30

    // Pop 연산
    println("Popped element: ${stack.removeLast()}") // 30

    // Size 연산
    println("Stack size: ${stack.size}") // 2

    // isEmpty 연산
    println("Is stack empty? ${stack.isEmpty()}") // false
}

스택 사용 예시

함수호출

함수의 호출 구조가 스택과 유사하다. 아래 예시를 보면 main -> A() -> B() 순으로 스택에 쌓인다고 생각하면 된다. 그리고 각 함수를 빠져나올 때 스택에서 제거된다.

fun main() { // 처음으로 스택에 저장
    A() // 두 번째로 스택에 저장
} // 스택에 저장된 A() 제거

fun A() {
    println("Start A")
    B() // 세 번째로 스택에 저장
    println("End A") // 스택에 저장된 B() 제거
}

fun B() {
    println("Start B")
    println("End B")
}

이전 페이지 가기

웹 페이지에서 뒤로 가기 버튼을 누를 때도 스택을 사용할 수 있다. 페이지를 전환할 때마다 스택에 push하고 이전 페이지로 갈 때 해당 페이지를 스택에서 pop한다.

괄호 짝 맞추기

괄호 짝이 맞는지 틀린지 판단하는 과정을 잘 생각해보면 스택을 사용할 수 있다는 것을 알 수 있다. 열린 괄호는 자신과 가장 가까운 닫힌 괄호와 매칭해야 한다.  강의를 듣고 프로그래머스에서 풀었던 <올바른 괄호> 문제를 떠올렸다. 이 문제를 한 번 풀어보면 바로 이해할 수 있을 것이다.

큐의 개념

큐(Queue) : 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조, FIFO(First In First Out) / LILO(Last In Last Out)

• BFS에서 사용한다.

큐의 ADT

Java

• offer(E element): 큐의 끝에 요소를 추가하는 연산으로 추가에 성공하면 true를 반환한다.
• poll(): 큐의 맨 앞 요소를 제거하고 반환한다. 큐가 비어 있으면 null을 반환한다.
• peek(): 큐의 맨 앞 요소를 제거하지 않고 반환한다. 큐가 비어 있으면 null을 반환한다.
• isEmpty(): 큐가 비어 있는지 확인한다.
• size(): 큐에 있는 요소의 개수를 반환한다.

자바에서는 Queue 인터페이스와 이를 구현한 다양한 클래스(LinkedList, ArrayDeque, PriorityQueue 등)를 통해 큐의 ADT를 사용할 수 있다. 다음은 LinkedList로 큐를 구현한 예시이다.

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        System.out.println("Front element: " + queue.peek()); // 10
        System.out.println("Removed element: " + queue.poll()); // 10
        System.out.println("Queue size: " + queue.size()); // 2
        System.out.println("Is queue empty? " + queue.isEmpty()); // false
    }
}

Kotlin

• add() / offer() : 큐의 끝에 요소를 추가한다.
• remove() / poll() : 큐의 맨 앞 요소를 제거하고 반환한다.
• element() / peek() : 큐의 맨 앞 요소를 제거하지 않고 반환한다.
• isEmpty() : 큐가 비어 있는지 확인한다.
• size :  큐의 요소 개수를 반환한다.

Kotlin에서는 Java의 표준 라이브러리를 그대로 사용할 수 있으며, 특히 ArrayDeque나 LinkedList를 큐로 사용하는 것이 일반적이다. 다음은 ArrayDeque로 큐를 구현한 예시이다.

fun main() {
    val queue: ArrayDeque<Int> = ArrayDeque()

    queue.add(10)
    queue.add(20)
    queue.add(30)

    println("Front element: ${queue.first()}") // 10
    println("Removed element: ${queue.removeFirst()}") // 10
    println("Queue size: ${queue.size}") // 2
    println("Is queue empty? ${queue.isEmpty()}") // false
}

큐의 사용 예시

줄서기

큐를 배울 때 가장 쉽고 이해가 잘 되는 예시 중 하나인 줄서기인 것 같다. front에는 가장 먼저 줄을 선 원소의 위치이고 rear은 가장 최근에 줄을 선 원소의 위치이다. 원소가 계속해서 줄을 설 때(push를 할 때)는  front는 변화가 없고 rear만 바뀐다. front에 있던 원소가 어딘가로 입장을 해서 빠져나가면(pop을 하면) 해당 위치에 있는 원소가 큐에서 삭제된다. 따라서 pop을 하면 rear는 변화가 없고 front만 바뀐다.

요세푸스 문제

요세푸스 문제의 과정은 다음과 같다.

1. N명의 사람들이 원형으로 둘러앉고, 각 사람들 번호를 1 ~ N으로 매김
2. 시작 위치부터 K번째 사람 제거
3. 제거한 위치부터 다시 K번째 사람 제거
4. 한 명이 남을 때까지 3번 과정 반복, 남은 한 명이 승리

요세푸스 문제를 배열로 푼다면 1) 제거의 방향이 바뀐다. 2) 제거 시 제거한 뒤의 원소가 모두 이동해야 한다. 시간복잡도는 O(N^2)이다. 원형을 잘 구현하려면 큐를 사용하면 된다. 요세푸스 문제를  큐로 풀면 1) 제거 동작이 push & pop으로 구현되므로 방향을 고려하지 않아도 된다. 2) 제거 후에도 원소 이동이 필요하지 않다. 시간복잡도는 O(N * K) 이다.

 

출처

코딩 테스트 합격자 되기 - C++ 강의 | 대시보드 - 인프런 (inflearn.com)