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

스택은 사전적인 의미로 "쌓다"라는 의미를 가지고 있습니다. 스택을 흔히 선출후입(LIFO)라고 부릅니다. 한쪽에서만 자료를 넣고 뺄수 있는 구조입니다. 실제로 인터넷 브라우적의 경우 '뒤로가기','앞으로가기' 버튼을 생각하시면 됩니다.

JAVA에서 제공해주는 Stack클래스

자바에서는 기본적으로 Stack클래스를 지원해줍니다. 물론 우리가 만들줄도 알아야 하지만 기왕에 주어진 기능 먼저 활용해 봅시다.

Stack<Element> stack = new Stack<>();

와 같이 생성할 수 있다. 기본적으로 push(), pop(), peek(), empty(), search()기능을 지원해 주는데 예제 코드를 사용해 각각이 어떤 기능인지 알아보자.

참고로 <Element>는 Stack 배열안에 들어가 데이터의 타입을 지정하면 된다. 정수를 넣고싶으면 <Integer>로 지정하면 되고 실수를 넣고 싶다면 <Double>로 지정하면 된다.

나는 정수값을 넣어볼것이다.

import java.util.Stack;

import javax.lang.model.element.Element;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();//push, pop, peek, empty, seach 지원
        for(int i=1; i<=5 ; i++) {
            stack.push(i);
            System.out.println(stack.peek());
        } //1, 2, 3, 4, 5 출력
        stack.pop();
        System.out.println("Pop()");
        System.out.println(stack.peek());    //4출력
        System.out.println(stack.search(3));    //2출력
        System.out.println(stack.empty());    //false출력
    }

}

• For문을 통해 1~5 숫자를 스택에 Push한다.
• stack.pop()으로 제일 최근에 들어간 값을 제거한다.
• stack.peek()으로 가장 최근에 들어간 값을 출력한다.(5가 pop()으로 제거되었으니 가장 최근에 넣은 값은 4이므로, 4가 출력되게 된다.
• stack.search(3)은 3의 인덱스를 출력해준다. 맨 밑부터 인덱스가 0,1,2,3 이므로 '3'은 현재 인덱스 2에 위치해 있다
• stack.empty()는 현재 스택이 비었으면 True, 값이 들어가 있으면 False를 출력해준다. 현재 스택에 값이 들어가 있으므로 출력값은 False이다.

배열로 Stack구현

자바에서 제공해주는 Stack을 이용하면 금방 스택을 사용할수 있지만 실제로 스택을 구현할줄도 알아야 한다. 그게 실력향상에 도움도 되고, 본인이 스택구조를 정확히 이해하고 있는지 없는지를 알수 있기 때문이다. (참고로, search와 empty는 자바에서 지원해주는 기능이고, Push, Pop, Peek은 스택의 주요기능이므로 Push, Pop, Stack만을 구현한다.)

public class ArrayStack {
    int top;    //인덱스
    int size;    //스택 배열의 크기
    int [] stack;
    public ArrayStack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }
}

멤버 변수에 top, size, []stack을 지정해 준다. 생성자로 멤버변수들을 초기화 해주면서 stack배열을 size만큼 초기화 해준다.

public class ArrayStack {
    int top;    //인덱스
    int size;    //스택 배열의 크기
    int [] stack;
    public ArrayStack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }

    public void push(int item) {
        stack[++top] = item;
        System.out.println(stack[top] + " Push!");
    }
    public void pop() {
        System.out.println(stack[top] + " Pop!");
        int pop = stack[top];
        stack[top--] = 0;
    }
    public void peek() {
        System.out.println(stack[top] + " Peek!");
    }
}

배열로 구현하는 것은 쉽습니다. 결과값을 보기위해서 System.out.println()을 사용해주었지만 굳이 사용하지 않아도 됩니다.

배열을 초기화 해줄때 int [] stack = new int [5]을 하게되면 배열의 크기는 5가 되고 값은 null 초기화 됩니다. 배열의 값들을 제거할때는 배열의 데이터 형태가 int형태이므로 null이 아닌 0값을 임의로 넣어줬습니다.

LinkedList로 Stack구현

링크드리스트로 Stack을 구현하는것은 배열보다 복잡하지만 링크드리스트 특성상 스택의 크기가 고정되어있지 않은 점에서 장점을 가지게 됩니다. LinkedList로 스택을 구현하려면 Node를 만들어야 합니다. Node는 데이터와 다음데이터를 가르키는 주소로 구성되어 있습니다.

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

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

    protected void linkNode(Node node) {//가르킬 노드를 지정
        this.node = node;
    }
    protected int getData() {
        return this.item;
    }
    protected Node getNextNode() { //다음 노드를 리턴
        return this.node;
    }
}

//LinkedListStack을 관리하는 클래스
public class NodeManager {
    Node top; //가장 최근에 들어온 노드를 가리킴

    public NodeManager() {
        this.top = null;
    }
    public void push(int data) {
        Node node = new Node(data);    //노드를 생성
        node.linkNode(top);    //새로 생성된 노드가 top이 가르키고 있는 노드를 맄크로 연결하게 함
        top = node;    //top의 값을 가장 최근에 생성된 node로 바꿈
    }
    public void pop() {
        top = top.getNextNode(); // 현재 top이 가리키고 있는 노드를 가리키게 함
    }
    public int peek() {
        return top.getData();
    }
}

코드를 짜면서 느낀점은 자료구조에서는 이해가 가지 않으면 그림을 그리면서 코드를 짜야한다는 점이다. LinkedListStack은 Node들은 그저 값을 보관하는 틀의 역할을 하고 NodeManager가 push pop peek의 역할을 하는것을 알 수 있다. top이라는 변수를 통해 가장 최근에 들어온 노드를 가리키고 잇습니다.

배열 스택

배열의 장점은 구현이 빠르고 데이터의 접근속도가 빨라 조회가 빠르다는 점 입니다. 하지만 배열의 크기가 정해져있어야만 사용할 수 있습니다. 실제 프로젝트에서 사용하기에는 좋지 않습니다.

LinkedListStack

장점은 스택에 들어가는 데이터의 양이 한정되어있지 않고 삽입 삭제가 용이합니다.(원한다면 중간에 있는 노드를 지울수도 있습니다.) 하지만 구현이 어렵고 배열과 달리 조회가 힘들다는 단점이 있습니다.

---

자바에서는 Stack을 제공해주어서 실제로 스택을 구현할 일은 거의 없을겁니다. 하지만 스택을 알고 쓰는것과 모르고 쓰는것은 천지차이 입니다. 이 글만 읽어도 알수 있듯이 자바에서 제공해주는 스택은 데이터의 개수가 한정되어있지 않다는 것을 알수 있습니다.(Stack클래스를 사용할때 어느 곳에서도 사이즈를 지정해 주지 않았습니다.) 그렇다는 것은 Stack 클래스는 LinkedList로 이루어 졌다는 의미이고 이것을 알고 사용하는것과 모르고 사용하는것은 큰 차이 입니다. 개념을 알게되면 코드로 구현할수 있는 능력은 반드시 필요합니다.