[Java] 배열로 Stack을 구현해보자!

[Java] 배열로 Queue를 구현해보자!에서 배열을 사용해 다른 자료구조(Queue) 처럼 이용할 수 있었습니다.

Stack도 Queue와 마찬가지로 배열로 해당 자료구조 처럼 사용할 수 가 있습니다.

물론 선행으로 배열의 크기를 정해주어야하니 최대로 들어올 자료의 수를 알고있어야 합니다.

그럼 배열로 간단하게 Stack을 구현해 보겠습니다.

배열을 이용한 Stack이므로 배열을 만들어 주었습니다.

int[] stack = new int[100];

Stack은 FILO(First In Last Out) 구조이므로 꺼낼 자료는 항상 top에 있는 자료 입니다. 따라서 꼭대기를 가리킬 top 변수를 선언해 주겠습니다.

int top = -1;

이제 배열로 만든 stack에 자료를 넣어보겠습니다. 일반적인 stack의 사용인 push 메서드의 호출은 필요없습니다. 그저 넣을 배열의 index인 top 변수를 이용하면 됩니다.

stack[++top] = 3;

배열로 만든 stack에 3을 넣었습니다. 조금 더 넣어보겠습니다.

stack[++top] = 4;
stack[++top] = 5;

3이후로 4와 5를 더 넣어주었습니다. 그럼 넣어둔 자료를 사용해보겠습니다. pop 메서드의 호출은 필요없습니다.

System.out.println(stack[top--]);
System.out.println(stack[top--]);
System.out.println(stack[top--]);

top 변수를 이용해 꼭대기에 있는 자료를 꺼낸뒤 top의 값을 -1 처리해주면됩니다. 좀 더 일반적인 Stack 처럼 만들고 싶드면 push()와 pop() 메서드를 따로 만들어서 변수를 받아 위의작업을 해주거나 return 값을 돌려주면 됩니다.

위의 예제에서 사용한 코드는 맨 아래있으며 그 출력은 다음과 같습니다.

3 넣음
4 넣음
5 넣음
5 나옴
4 나옴
3 나옴

아주 간단하게 Stack을 구현했지만 약간의 의구심이 들수도 있습니다. "왜 배열을 이용해서 자료구조를 구현해보는 걸까요?" 답은 간단합니다. 빠릅니다. 자료수의 최대값 이상으로 배열을 만들어서 메모리를 낭비하고 스피드를 얻는 전략? 입니다. 배열은 자료구조 중 읽기 쓰기가 가장 빠른 자료구조에 속하기 때문입니다.

배열로 만들어 쓰는 Queue와 Stack은 항상 index를 넘어가지 않도록 관리를 잘 해주기만 한다면 완성한 알고리즘의 속도를 조금은 더 빠르게 해줄 것 입니다!

<예제 코드>

public class Main {
    public static void main(String[] args) {
        int[] stack = new int[100];
        int top = -1;
        
        stack[++top] = 3;
        System.out.println("3 넣음");
        stack[++top] = 4;
        System.out.println("4 넣음");
        stack[++top] = 5;
        System.out.println("5 넣음");
        
        System.out.println(stack[top--]+" 나옴");
        System.out.println(stack[top--]+" 나옴");
        System.out.println(stack[top--]+" 나옴");
    }
}// end of class