스택 정의

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서를 후입선출(LIFO, Last In First Out) 입니다.(가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.)
스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 합니다.
이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다.

스텍 메서드

• push(): 스택에 데이터를 푸시하는 메서드. 스텍이 가득 차서 푸시할 수 없는 경우 예외 OverflowIntStackException을 던집니다.

  public int push(int x) throws OverflowIntStackException {
        if (ptr >= max)          // 스택이 가득 참
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }
  

• pop(): 스택의 꼭대기에서 데이터를 팝(제거)하고 그 값을 반환하는 메서드입니다. 스택이 비어 있어 팝을 할 수 없는 경우 예외 EmptyIntStackException을 던집니다.

  public int pop() throws EmptyIntStackException {
        if (ptr <= 0)                // 스택이 비어 있음
            throw new EmptyIntStackException();
        return stk[--ptr];
    }
  

• peek(): 스택의 꼭대기에 있는 데이터를 “몰래 엿보는” 메서드입니다. 스택이 비어 있는 경우 예외 EmptyIntStackException을 던집니다.

  public int peek() throws EmptyIntStackException {
        if (ptr <= 0)                // 스택이 비어 있음
            throw new EmptyIntStackException();
        return stk[ptr - 1];
    }
  

• indexOf(): 스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드입니다.

  public int indexOf(int x) {
        for (int i = ptr - 1; i >= 0; i--)				// 정상 쪽에서 선형 검색
            if (stk[i] == x)
                return i;								// 검색 성공
        return -1;										// 검색 실패
    }
  

• clear(): 스택의 모든 요소를 삭제하는 메서드

  public void clear() {
        ptr = 0;
    }
  

• capacity(): 용량을 확인하는 메서드

  public int capacity() {
        return max;
    }
  

• size(): 데이터 수를 확인하는 메서드

  public int size() {
        return ptr;
    }
  

• IsEmpty(): 스택이 비어 있는지 검사하는 메서드

  public boolean isEmpty() {
        return ptr <= 0;
    }
  

• IsFull(): 스택이 가득 찼는지 검사하는 메서드

  public boolean isFull() {
        return ptr >= max;
    }
  

• dump(): 스택 안에 있는 모든 데이터를 표시하는 메서드

  public void dump() {
        if (ptr <= 0)
            System.out.println("스택이 비어 있습니다.");
        else {
            for (int i = 0; i < ptr; i++)
                System.out.print(stk[i] + " ");
            System.out.println();
        }
    }
  

  
  

스텍의 사용사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

• 재귀 알고리즘
  • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
  • 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
  • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
• Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산
  

위와 같이 스텍의 이해와 스텍 관련 메서드를 알아보았다. 스텍은 Array와 LinkedList로도 구현해볼 수도있다. 두가지 방법으로 구현해보도록 하자.

참조

• 자료구조와 함께 배우는 알고리즘 입문 (자바 편)
• HeeJeong Kwon Blog