[자료구조] 스택 (Stack) 구현 (JAVA)

스택이란 후입선출(LIFO) 구조를 갖는 자료구조이다. 스택에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.

2024.06.15 - [CS/자료구조] - [자료구조] 스택 (Stack)

[자료구조] 스택 (Stack)

 

스택 구현 방법

---

스택을 구현하는 방법에는 크게 2가지 방법이 있다.

• 배열(Array) 기반 스택: 고정 크기의 배열을 사용하여 스택을 구현한다. 배열의 크기를 초과하면 새로운 배열을 할당해야 한다.
• 연결 리스트(Linked-List) 기반 스택: 동적 크기의 연결 리스트를 사용하여 스택을 구현한다. 요소를 추가하거나 제거할 때마다 노드를 생성하거나 삭제한다.

 

배열(Array) 기반 스택 구현 (JAVA)

---

public class ArrayStack {
    private int maxSize;
    private int top;
    Object[] stack;

    public ArrayStack(int size) {
        this.maxSize = size;
        this.stack = new Object[size];
        this.top = -1;
    }

    public void push(Object value) {
        if (isFull()) {
            System.out.println("Stack is full");
        } else {
            this.stack[++top] = value;
        }
    }

    public Object pop() {
        if (isEmpty()) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return this.stack[top--];
        }
    }

    public Object top() {
        if (isEmpty()) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return this.stack[top];
        }
    }

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

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

	public static void main(String[] args) throws Exception {
    }
}

ArrayStack 클래스:  멤버변수들과 push, pop, top, isEmpty, isFull 메소드로 구성되어 있다.

    public static void main(String[] args) throws Exception {
        ArrayStack stack = new ArrayStack(5);

        stack.push(1);
        stack.push("!2!");
        stack.push(3);
        stack.push("!4!");
        stack.push(5);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

메인함수는 스택을 테스트 및 이해하기 위해서 크기 5의 스택을 만들고 push, pop 연산을 수행했다. 코드 결과는 다음과 같다.

5
!4!
3
!2!
1

선입선출의 스택의 특징에 맞게 작동하고 있는 것을 알 수 있다.

 

연결 리스트(Linked-List) 기반 스택 구현 (JAVA)

---

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

Node 클래스

public class LinkedListStack {
    private Node top;

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

    public void push(int data) {
        Node newNode = new Node(data);
        if (top != null) {
            newNode.next = top;
        }
        top = newNode;
    }

    public int pop() throws Exception {
        if (top == null) {
            throw new Exception("Stack is empty");
        }
        int data = top.data;
        top = top.next;
        return data;
    }

    public int top() throws Exception {
        if (top == null) {
            throw new Exception("Stack is empty");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
    public static void main(String[] args) throws Exception {
        LinkedListStack stack = new LinkedListStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.top());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());

    }
}

LinkedListStack 클래스 및 메인 함수. 실행 결과는 다음과 같다.

3
2
false
2
1
true
Exception in thread "main" java.lang.Exception: Stack is empty
        at LinkedListStack.pop(LinkedListStack.java:18)
        at LinkedListStack.main(LinkedListStack.java:46)

스택의 기능에 맞게 잘 실행되는 것을 확인할 수 있다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!