Stack 직접 구현해보기 (JAVA)

Stack은 LIFO(Last In First Out) 구조이며, 재귀 함수의 동작 흐름과 같은 구조를 가집니다. 삽입과 제거는 모두 top 위치에서 이뤄지므로 O(1)의 시간 복잡도를 갖고 탐색 연산은 해당 데이터를 찾을 때까지 수행해야 하므로 O(n)의 시간 복잡도를 갖습니다. 기본적으로 push, pop, peek, empty, search 등의 메소드를 지원합니다.

구현

public class Node{
	private int item;
    private Node next;

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

    protected void linkNode(Node next) {
        this.next = next;
    }

    protected int getData() {
        return this.item;
    }

    protected Node getNextNode() {
        return this.next;
    }
}

public class MyStack {
    private Node top;
    private int size;

    public MyStack() {
        this.top = null;
        this.size = 0;
    }

    // push() 메소드: 스택의 맨 위에 요소를 추가합니다.
    public void push(int item) {
        Node newNode = new Node(item);
        newNode.linkNode(top);
        top = newNode;
        size++;
    }

    // pop() 메소드: 스택의 맨 위에 있는 요소를 제거하고 반환합니다.
    public int pop() {
        if (empty()) {
            throw new RuntimeException("Stack is empty");
        }
        int item = top.getData();
        top = top.getNextNode();
        size--;
        return item;
    }

    // peek() 메소드: 스택의 맨 위에 있는 요소를 반환하지만 제거하지는 않습니다.
    public int peek() {
        if (empty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.getData();
    }

    // empty() 메소드: 스택이 비어있는지 확인합니다.
    public boolean empty() {
        return top == null;
    }

    // search() 메소드: 스택에서 특정 요소의 위치를 반환합니다. (1부터 시작)
    // 요소가 없으면 -1을 반환합니다.
    public int search(int item) {
        Node current = top;
        int position = 1;
        while (current != null) {
            if (current.getData() == item) {
                return position;
            }
            current = current.getNextNode();
            position++;
        }
        return -1;
    }