스택(Stack)

Kkd·2024년 12월 27일

매일메일 개념정리

목록 보기

45/93

스택(Stack)

스택은 선형 자료구조의 한 종류로, 데이터를 후입선출(LIFO, Last In First Out) 방식으로 관리합니다. 즉, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되거나 사용됩니다.
스택은 아래와 같은 기본 연산을 제공합니다:

스택의 주요 연산

push: 스택의 맨 위에 데이터를 삽입.
pop: 스택의 맨 위 데이터를 제거하고 반환.
peek (또는 top): 스택의 맨 위 데이터를 제거하지 않고 반환.
isEmpty: 스택이 비어 있는지 확인.
isFull: 스택이 꽉 찼는지 확인 (고정 크기 스택인 경우).

스택의 특징

후입선출(LIFO): 가장 나중에 삽입된 데이터가 가장 먼저 사용됨.
제한된 접근: 데이터를 삽입하고 삭제하는 작업은 스택의 맨 위(top)에서만 수행 가능.
순차적 저장: 일반적으로 배열(Array) 또는 연결 리스트(Linked List)로 구현.

스택의 구현

1. 배열 기반 스택

class Stack {
    private int[] stack;
    private int top;
    private int size;

    public Stack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1; // 초기에는 스택이 비어 있음
    }

    // 데이터 삽입
    public void push(int value) {
        if (top == size - 1) {
            throw new StackOverflowError("스택이 가득 찼습니다.");
        }
        stack[++top] = value;
    }

    // 데이터 제거 및 반환
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다.");
        }
        return stack[top--];
    }

    // 스택의 맨 위 요소 반환
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다.");
        }
        return stack[top];
    }

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

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println(stack.pop()); // 출력: 30
        System.out.println(stack.peek()); // 출력: 20
        System.out.println(stack.isEmpty()); // 출력: false
    }
}

2. 연결 리스트 기반 스택

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListStack {
    private Node top;

    public LinkedListStack() {
        this.top = null;
    }

    // 데이터 삽입
    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    // 데이터 제거 및 반환
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다.");
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    // 스택의 맨 위 요소 반환
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("스택이 비어 있습니다.");
        }
        return top.data;
    }

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

public class Main {
    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println(stack.pop()); // 출력: 30
        System.out.println(stack.peek()); // 출력: 20
        System.out.println(stack.isEmpty()); // 출력: false
    }
}