[java] 자바 스택 구현시 링크드 리스트 사용하기

05 Dec 2023

java

스택은 데이터를 일시적으로 저장하는 자료구조로, 후입선출(LIFO) 원칙에 따라 동작합니다. 스택을 자바로 구현할 때에는 링크드 리스트를 사용하는 것이 일반적입니다. 이번 블로그 포스트에서는 자바에서 링크드 리스트를 사용하여 스택을 구현하는 방법을 알아보겠습니다.

링크드 리스트 구현하기

링크드 리스트는 여러 노드가 연결된 구조를 가지고 있습니다. 각 노드는 데이터와 다음 노드를 가리키는 링크를 가지고 있으며, head라는 포인터는 첫 번째 노드를 가리킵니다. 우선 링크드 리스트를 구현해보도록 하겠습니다.

public class Node {
    int data; // 노드에 저장될 데이터
    Node next; // 다음 노드를 가리키는 링크

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

public class LinkedList {
    Node head; // 첫 번째 노드를 가리키는 포인터

    public LinkedList() {
        this.head = null;
    }

    // 새로운 노드를 맨 앞에 추가하는 메소드
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 스택의 가장 위에 있는 데이터를 추출하는 메소드
    public int pop() {
        if (head == null) {
            throw new NoSuchElementException();
        }
        int data = head.data;
        head = head.next;
        return data;
    }

    // 스택이 비어있는지 확인하는 메소드
    public boolean isEmpty() {
        return head == null;
    }
}

위의 코드는 링크드 리스트를 구현하기 위한 Node 클래스와 LinkedList 클래스를 정의한 예입니다. push 메소드는 새로운 노드를 맨 앞에 추가하는 역할을 하고, pop 메소드는 스택의 가장 위에 있는 데이터를 추출할 수 있습니다. 또한 isEmpty 메소드를 사용하여 스택이 비어있는지 확인할 수 있습니다.

링크드 리스트 스택 사용하기

이제 링크드 리스트를 사용하여 스택을 구현했으니, 실제로 스택을 활용하는 예제를 살펴보겠습니다.

public class Main {
    public static void main(String[] args) {
        LinkedList stack = new LinkedList();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop()); // 3
        System.out.println(stack.pop()); // 2
        System.out.println(stack.pop()); // 1

        System.out.println(stack.isEmpty()); // true
    }
}

위의 코드는 링크드 리스트 스택을 사용하는 예제입니다. push 메소드를 사용하여 데이터를 스택에 추가하고, pop 메소드를 사용하여 스택의 데이터를 추출합니다. 마지막으로 isEmpty 메소드를 사용하여 스택이 비어있는지를 확인합니다.

이렇게 링크드 리스트를 사용하여 자바에서 스택을 구현할 수 있습니다. 링크드 리스트를 사용하면 데이터를 삽입하거나 삭제하는 과정이 간단해지기 때문에 스택을 효율적으로 구현할 수 있습니다.

링크드 리스트 구현하기

링크드 리스트 스택 사용하기

참고 자료