[자료 구조] Stack이란?

1. 스택(Stack)이란?

• LIFO(Last In First Out)
• push: 스택에 데이터를 넣는 작업
• pop: 스택에서 데이터를 꺼내는 작업
• 푸시와 팝이 이루어지는 꼭대기는 top, 스택의 가장 아랫부분은 bottom이라고 한다.

2. 직접 스택 생성하기

static class IntStack {
  private int[] stack; // 스택 배열
  private int capacity;  // 스택 용량
  private int stackPointer; // 스택에 쌓여있는 데이터 수

  // 실행시 예외: 스택이 비어 있는 경우
  public class EmptyIntStackException extends RuntimeException {
    public EmptyIntStackException() {};
  }

  // 실행시 예외: 스택이 가득 찬경우
  public class OverflowIntStackException extends RuntimeException {
    public OverflowIntStackException() {};
  }

  public IntStack(int maxlen) {
    this.stackPointer = 0;
    this.capacity = maxlen;
    try {
      this.stack = new int[capacity];
    } catch(OutOfMemoryError e) {
      this.capacity = 0;
    }
  }

  public int push(int x) throws OverflowIntStackException{
    if(this.stackPointer >= capacity) {
      throw new OverflowIntStackException();
    }
    return this.stack[this.stackPointer++] = x;
  }

  public int pop() throws EmptyIntStackException{
    if(this.stackPointer <= 0) {
      throw new EmptyIntStackException();
    }
    return this.stack[--this.stackPointer];
  }

  public int peek() throws EmptyIntStackException {
    if(this.stackPointer <= 0) {
      throw new EmptyIntStackException();
    }
    return this.stack[this.stackPointer - 1];
  }

  public void clear() {
    this.stackPointer = 0;
  }

  public int indexOf(int x) {
    for(int i = this.stackPointer - 1; i >= 0; i--) {
      if(this.stack[i] == x) {
        return i;
       }
    }
    return -1;
  }

  public int getCapacity() {
    return this.capacity;
  }

  public int size() {
    return this.stackPointer;
  }

  public boolean isEmpty() {
    return this.stackPointer <= 0;
  }

  public boolean isFull() {
    return this.stackPointer >= this.capacity;
  }
}