[자료구조] Stack 구현

stack을 배열로 구현

삼단 논법처럼 생각하면 쉽다.
1. stack에서 데이터가 들어가고 나가는 입구는 top뿐이다.
2. 스택은 배열로 구현할 수 있다.
3. 배열에서 데이터에 접근할 때는 index를 이용한다.
=> 스택을 배열로 구현하면, top을 인덱스로 사용하며 이것이 데이터에 접근할 유일한 통로가 된다.

주의 사항
1)
데이터가 들어오지 않았을 때 top은 -1이다.
하나가 들어오면 그때 0으로 스택의 top을 표시해야 하므로 top은 -1로 초기화한다.
2)
배열로 스택을 구현하였을때, 길이가 정해져있다는 배열의 특성을 반영해야 한다.
따라서 push를 할 때는 배열이 가득 찼는지, pop이나 peek을 할 때는 배열이 empty는 아닌지 고려해야 한다.
이를 고려하지 않으면 top이 배열의 길이보다 길어지거나 -1이 되어 OutOfBounds 문제가 발생할 수 있다.
3)
top의 어감 때문에 오해가 발생할 수 있을 것 같은데, top은 '모든 원소들의 꼭대기'가 아니라,
가장 나중에 들어온 원소의 인덱스 즉, 아래 그림처럼 생각하면, 가장 위에 있는 원소의 인덱스를 나타낸다.
헷갈리지 않게 조심하자!

---

전체 코드

package Stack;

class Stack{
    int[] stack;
    int top = -1;

    Stack(int size){
        this.stack = new int[size];
    }
    public boolean isEmpty(){
        if(top == -1){
            return true;
        } else {
            return false;
        }
    }

    public boolean isFull(){
        if(top == stack.length-1){
            return true;
        } else {
            return false;
        }
    }

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

    // null을 리턴할 수 있으므로 리턴 타입을 int가 아니라 Integer로 설정
    public Integer pop(){
        if(isEmpty()){
            System.out.println("Stack is empty.");
            return null;
        } else {
            int v = this.stack[this.top];
            this.stack[this.top] = 0; // 사실 stap의 영역은 top까지이므로 안해줘도 상관 없음
            this.top--;
            return v;
        }
    }
    public int peek(){
        if(isEmpty()){
            System.out.println("Stack is empty.");
            return -1;
        } else {
            int v = this.stack[this.top];
            return v;
        }
    }

    public void print(){
        for (int i=0; i<=this.top; i++) {
            System.out.print(this.stack[i]+" ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        for (int i = 0; i <= 5; i++) {
            stack.push(i);
        }

        stack.print();

        for (int i = 0; i <= 5; i++) {
            Integer result = stack.pop();
            System.out.print(result==null ? " " : result+" ");
        }
    }
}