[자료구조] 스택

스택

• 한 쪽 끝에서만 자료를 넣고, 뺄 수 있는 자료구조다.
• Push로 데이터를 집어넣고, Pop으로 데이터를 빼낸다.
  

  

• 그림 상으로는 스택의 각 인덱스에 있는 데이터를 알 수 있지만, 사실상 제일 위에 있는 데이터만 알 수 있는 자료구조다. 보통 제일 위에 있는 데이터를 top라고 한다.

스택의 구현

• 일차원 배열 하나로 구현이 가능하다.

public class Stack<T> {
    private T[] data;
    private int size;

    @SuppressWarnings("unchecked")
    public Stack(int capacity) {
        data = (T[])new Object[capacity];
        size = 0;
    }

    public Stack() {
        this(10);
    }

    public void push(T data) {
        this.data[size++] = data;
    }

    public T pop() {
        return this.data[--size];
    }

    public int getSize() {
        return size;
    }
}

• 1차원 배열 data와, stack의 크기를 알려주는 size를 선언했다.
• 사용자는 스택의 최대 크기를 지정할 수 있다. 만약 최대 크기를 정해주지 않는다면 최대크기는 default 10이다
• 앞서 말한 것처럼 push로 데이터를 저장할 수 있다.
  • 예를 들어 처음 push(10) 을 한다면 data[0]에 10이 저장된다.
  • 후위연산자로 식을 수행한 뒤 size + 1이 된다
• 앞서 말한 것처럼 pop으로 데이터를 빼낼 수 있다.
  • 예를 들어 배열에 [3,1,6] 이와 같은 값이 저장돼있다면, pop()을 수행할 시 맨 마지막 값인 6을 반환한다.
  • 현재 size는 3이기 때문에 data[3]은 null이다. 따라서 전위연산자로 식을 수행하기 전 size - 1을 한 뒤 값을 빼낸다