[Java] 스택 직접 구현하기 & 라이브러리 사용 JAVA

 해당 포스터에서 스택에 대한 개념은 정리하지 않는다.

 

 하지만 코테준비를 위해 스택을 직접 구현한 코드(배열, 리스트)와 라이브러리를 활용 한 스택 자료구조 사용방법에 대해 정리하려고 한다.

 

 코테에서는 스택을 직접 구현하는 것보단 스택을 활용한 응용문제들이 많이 나오는 것 같다.

 

1. 배열로 직접 구현

---

 배열로 직접 구현하는 경우는 배열의 크기가 정해진 상황에서는 쉽게 구현할 수 있지만, 크기가 정해지지 않는 상태에서는 배열은 실행 중 크기를 동적으로 바꿀 수 없기 때문에 각 상황에 맞게 배열을 다시 생성해서 값들을 옮겨주는 귀찮은 작업을 해야한다.(해당 코드에서는 이 작업이 적용되어있지 않다.)

public class Stack_Array {

    int top;
    int [] stack;
    int size;

    public Stack_Array(int size) {
        this.size = size; //
        stack = new int[size];
        top = -1; // top 의 값 초기화
    }

    private void push(int item) {
        stack[++top] = item;
        System.out.println(stack[top] + " push!");
    }

    private void peek() {
        System.out.println(stack[top] + " peek!");
    }

    private void pop() {
        System.out.println(stack[top] + " pop!");
        stack[top--] = 0;
    }

    private int search(int item) {
        for (int i = 0; i <= top; i++) { // for 문은 top 만큼
            if (stack[i] == item)
                return (top - i) + 1; // top - 탐색한 배열의 인덱스, 배열 이므로 +1 추가
        }
        return -1;
    }

    private boolean empty() {
        return size == 0;
    }
}

 

 

2. 리스트로 직접 구현

---

public class Stack_List {

    Node top;

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

    private void push(int data) {
        Node node = new Node(data);
        node.linkNode(top);
        top = node;
    }

    public int peek() {
        return top.getData();
    }

    private void pop() {
        if (empty())
            throw new ArrayIndexOutOfBoundsException();
        else {
            top = top.getNextNode();
        }
    }

    private int search(int item) {
        Node searchNode = top;
        int index = 1;
        while(true) {
            if (searchNode.getData() == item) {
                return index;
            } else {
                searchNode = searchNode.getNextNode();
                index ++;
                if (searchNode == null)
                    break;
            }
        }

        return -1;
    }

    private boolean empty() {
        return top == null;
    }
}


class Node {

    private int data;
    private Node nextNode;

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

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

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

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

 

 

3. 스택 라이브러리의 사용

---

public class UseStack {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);     // stack에 1 추가
        stack.push(2);     // stack에 2 추가

        stack.pop();       // stack에 맨 위의 값 제거
        stack.clear();     // stack의 전체 값 제거 (초기화)

        stack.push(2);     // stack에 2 추가
        stack.push(4);     // stack에 4 추가
        stack.push(5);     // stack에 5 추가
        stack.peek();     // stack의 가장 상단의 값 출력 -> 5

        stack.contains(5); // stack에 5가 있는지 확인 -> false
        stack.size();      // stack의 크기 출력 : 2
        stack.empty();     // stack이 비어있는지 확인 (비어있다면 true)
    }
}