[자료구조] 스택

overview

이번 자료구조 포스트에서는 stack에 대해서 공부를 해볼 것이다.

stack

stack을 우리나라 말로 하면 쌓다라는 의미이다.
stack이라는 자료구조는 데이터를 차곡차곡 쌓아올린 자료구조이다.

위 그림처럼 데이터가 들어오면 차곡차곡 쌓아올린다. 그런데 보면 데이터가 드나들 수 있는 출입구가 하나이다.
이 말은 데이터의 입출구가 같다는 것이다. 그래서 나타나는 특징이 stack은 먼저, 들어온 데이터가 나중에 나가는 선입후출(Frist In, Last Out)이라는 특징을 가진다.

자바를 기준으로 보았을 때, stack을 사용하면서 자주 사용을 하는 메소드들이 있다.
push, push는 stack에 top에 데이터를 추가하는 메소드이다.
pop, pop은 stack에 top에 있는 데이터를 제거하는 메소드이다.
isEmpty, isEmpty는 스택에 데이터가 없는 지를 판단을 하는 메소드이다.
peek, peek은 스택에 가장 위에 위치한 데이터를 반환을 하는 메소드이다.

stack 사용해보기

이제 stack이 무엇인지, stack에 어떤 메소드들이 있는지 알아보았으니 이를 사용을 해보자.

push

public class StackStudy {
    public static void main(String[] args) {
        Stack<Integer> stackInt = new Stack<>();
        stackInt.push(1);
        stackInt.push(2);
        stackInt.push(3);

        System.out.println("stackInt = " + stackInt);
    }
}

stack이라는 객체를 만들어주고 push라는 메소드를 사용을 해서 1, 2, 3을 넣어주었다.
그리고 이를 출력을 해보았다.

코드에서 넣어주었던 1,2,3이 나오는 것을 확인을 할 수 있었다.

pop

public class StackStudy {
    public static void main(String[] args) {
        Stack<Integer> stackInt = new Stack<>();
        stackInt.push(1);
        stackInt.push(2);
        stackInt.push(3);

        Integer pop = stackInt.pop();
       

        System.out.println("stackInt = " + stackInt);
        // 1, 2
        System.out.println("pop = " + pop);
        // 3

    }
}

이제 pop이라는 메소드를 사용을 해보자. 위에서 했던 코드에서 pop 메소드를 사용을 해보았다.
그리고 stack가 pop을 했을 때 반환하는 값을 출력을 해보았다.

stack은 3이 빠진 1, 2를 확인을 할 수 있는 것을 알 수 있다. 그리고 pop을 했을 때, 반환이 되는 값이 3인 것을 알 수 있다.
여기서 한 가지 알 수 있는 사실은 stack의 선입후출 특징이다.
코드를 보면 우리는 1을 먼저, 3을 나중에 넣었다. 근데 pop을 했을 때 반환이 되는 값이 3인 것을 알 수 있다. 이는 stack의 선입후출 특징이 적용이 된 것을 알 수 있다.

isEmpty

public class StackStudy {
    public static void main(String[] args) {
        Stack<Integer> stackIntOne = new Stack<>();
        Stack<Integer> stackIntTwo = new Stack<>();
        stackIntOne.push(1);
        stackIntOne.push(2);
        stackIntOne.push(3);

        System.out.println("stackIntOne = " + stackIntOne.isEmpty());
        System.out.println("stackIntTwo = " + stackIntTwo.isEmpty());
    }
}

isEmpty는 값이 비어 있는지를 확인을 하는 메소드이다.
값이 들어있는 stackIntOne과 비어 있는 sackIntTwo를 만들고 isEmpty 메소드를 사용해서 출력을 해보았다.

값이 들어 있는 stackIntOne은 false가 나오고 비어 있는 sackIntTwo는 true가 나오는 것을 확인을 했다.

peek

public class StackStudy {
    public static void main(String[] args) {
        Stack<Integer> stackInt = new Stack<>();
        stackInt.push(1);
        stackInt.push(2);
        stackInt.push(3);

        Integer peek = stackInt.peek();

        System.out.println("peek = " + peek);
    }
}

peek은 stack에서 가장 위에 있는 데이터를 반환을 한다.
stackInt에 peek을 한 것을 출력을 해보았다.

현재, 나중에 들어온 3이 가장 위에 있다. 그렇기 때문에 peek을 했을 때, 가장 위에 있는 3이 출력이 되는 것을 확인을 할 수가 있다.

Java로 stack 구현하기

public class makeStack {

    private int maxSize;
    private int[] stackArray;
    private int top;

    public makeStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[this.maxSize];
        this.top = -1;
    }

    public void push(int data) {
        if (isFull()) {
            System.out.println("스택이 가득 찾습니다.");
        } else {
            stackArray[++top] = data;
        }
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("삭제할 데이터가 없습니다.");
            return -1; // 스택이 비어있으면 -1을 반환
        } else {
            return stackArray[top--];
        }
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("데이터가 없습니다.");
            return -1;
        } else {
            return stackArray[top];
        }
    }

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

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

array를 통해서 간단하게 stack을 구현을 해보았다.
array를 선택한 이유는 순서가 보장이 되는 자료구조이기 때문이다.

isEmpty와 isFull메소드를 통해서 stack에 데이터가 가득 찼는지 비어 있는지를 판단을 하였다. 그리고 push에 경우 가득 차있지 않다면 stackArray에 값을 추가를 해주고 pop은 비어 있지 않다면 가장 위에 있는 값, array를 기준으로 가장 뒤어 있는 값을 제거해주었다.
peek 또한 비어 있는지를 판단을 하고 비어 있지 않다면 가장 뒤에 있는 값을 반환을 해주도록 하였다.