[자료구조][스택] - 연결 리스트 스택

연결 리스트 스택 구조

스택의 최상단은 연결 리스트의 첫 번째 노드

삽입 / 삭제 연산은 스택의 최상단에서 이루어짐

연결 리스트 스택 장점

배열과 다르게 동적이므로

효율적인 메모리 사용 가능

연결 리스트 스택 단점

데이터 이외에 다음 노드를 위한

포인터를 위한 메모리가 추가 필요하므로

작은 데이터셋에서는 오버헤드 발생 우려

연결 리스트 스택 구현 (Java)

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 data) {
        Node newNode = new Node(data);  
        newNode.next = top;            
        top = newNode;                  
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");  // 예외 처리
        }
        int popped = top.data;  
        top = top.next;       
        return popped;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

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

        System.out.println("Top element is " + stack.peek());   // 30
        System.out.println("Popped element is " + stack.pop()); // 30
        System.out.println("Top element is " + stack.peek());   // 20
    }
}