스택

Stack ADT

연산 (Operations)

• boolean isFull() → 스택이 가득 찼는지 확인하여 boolean 값을 반환합니다.
• boolean isEmpty() → 스택이 비어 있는지 확인하여 boolean 값을 반환합니다.
• void push(itemType item) → 스택에 데이터를 추가합니다.
• itemType pop() → 스택에서 최근에 추가된 데이터를 제거하고 해당 값을 반환합니다.

상태 (State)

• int top → 스택에서 최근에 추가된 데이터의 위치를 기록합니다.
• itemType data[maxsize] → 스택의 데이터를 관리하는 배열로, 최대 maxsize개의 데이터를 관리합니다.

세부 동작 (Detailed Operations)

스택에 데이터를 추가하고 빼는 경우에서의 세부동작을 공부하면 추후 코딩테스트나 면접에서 도움이 될겁니다.

data(3) 추가

1. isFull() → 가득 찼는지 먼저 확인
2. 상태 top (시작 -1) 을 1 증가 시켜
3. data[top] 에 data 추가.

data pop()

1. isEmpty() → 비어있는지 먼저 확인
2. 상태 top 1감소
3. 데이터 3 반환해

→ 여기서 의문 ?? ‘3이 남아있는데? ‘ 라고 생각할 수 있다. ADT에서 top은 최근에 삽입한 데이터의 위치 상태를 나타낸다. 즉 top이 가리키는 위치가 -1 이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 봐도 된다.

Data 추가 (Push)

1. isFull() → 스택이 가득 찼는지 먼저 확인합니다.
2. top을 1 증가시킵니다.
3. data[top]에 새로운 데이터를 추가합니다.

Data 제거 (Pop)

1. isEmpty() → 스택이 비어 있는지 먼저 확인합니다.
2. top을 1 감소시킵니다.
3. data[top + 1]의 값을 반환합니다.

스택 ADT의 예시 구현

public class Stack<T> {
    private int maxSize;
    private int top;
    private T[] data;

    @SuppressWarnings("unchecked")
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.data = (T[]) new Object[maxSize];
        this.top = -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(T item) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        }
        data[++top] = item;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return data[top--];
    }
}

ArrayDeque

ArrayDeque는 Java의 Deque 인터페이스를 구현한 클래스 중 하나로, 스택과 큐의 기능을 모두 제공합니다. ArrayDeque는 배열 기반의 데이터 구조로, ArrayList와 유사하지만 스택과 큐 연산에 최적화되어 있습니다.

ArrayDeque의 주요 특징

1. 빠른 성능: ArrayDeque는 동적 배열을 사용하여 요소를 저장하며, 스택 연산 (push, pop)과 큐 연산 (offer, poll)을 모두 상수 시간 (O(1))에 수행합니다.
2. 메모리 효율성: ArrayDeque는 동적 배열 크기를 조정하여 메모리 사용을 최소화합니다.
3. 멀티스레드 환경에서는 주의: ArrayDeque는 동기화되지 않으므로, 멀티스레드 환경에서 안전하지 않습니다. 동기화된 스택 또는 큐가 필요한 경우 Collections.synchronizedDeque 또는 ConcurrentLinkedDeque를 사용해야 합니다.

ArrayDeque의 사용 예시

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // Push elements
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Pop elements
        System.out.println(stack.pop()); // Output: 30
        System.out.println(stack.pop()); // Output: 20

        // Check if stack is empty
        System.out.println(stack.isEmpty()); // Output: false

        // Push more elements
        stack.push(40);
        stack.push(50);

        // Peek at the top element
        System.out.println(stack.peek()); // Output: 50
    }
}

요약

• Stack ADT는 isFull, isEmpty, push, pop 메서드를 통해 스택의 기본 연산을 제공합니다.
• ArrayDeque는 스택과 큐의 기능을 모두 제공하며, 성능이 뛰어나고 메모리 효율적인 데이터 구조입니다.
• Java의 ArrayDeque는 스택과 큐 연산에 최적화되어 있으며, 멀티스레드 환경에서는 동기화된 대안을 사용하는 것이 좋습니다.