Stack

 

Stack 이란?

데이터를 차곡차곡 쌓아 올린 형태의 자료구조.

 

 

Stack 특징

1. LIFO (Last In First Out)
   • 먼저 들어간 데이터가 가장 나중에 나오는 후입선출의 구조
2. 데이터는 하나씩 넣고 뺄 수 있다. 
3. 하나의 입출력 방향만을 가지고 있다. 
   • 정해진 방향으로만 쌓을 수 있고, top 으로 정한 곳을 통해서만 접근할 수 있다. 

 

 

Stack의 사용 사례

• 웹 브라우저의 방문기록
• 실행취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

 

 

Stack 메서드 (Collection Framework)

리턴 타입	메서드	설명
boolean	empty()	Stack 이 비어 있는지 알려준다.
Object	push(Object item)	Stack에 객체(item)를 저장한다.
Object	pop()	Stack의 맨 위에 저장된 객체를 꺼낸다.  (비었을 때는 EmptyStackException 발생)
Object	peek()	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않는다.  (비었을 때는 EmptyStackException 발생)
int	search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못 찾으면 -1 을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작)

 

 

Stack 직접 구현해보기

• 실제 Stack은 컬레션 프레임워크 이전부터 존재하던 것이어서 Vector로부터 상속받아 구현되어 있지만, ArrayList를 통해 메서드들이 동일한 기능을 하도록 구현해보기 
• 구현하려는 기능
  • push() : 스택에 데이터를 추가하고 추가한 데이터 리턴
  • pop() : 가장 나중에 추가된 데이터를 스택에서 삭제하고, 삭제한 데이터 리턴
  • size() : 스택에 추가된 데이터의 크기 리턴
  • peek() : 가장 나중에 추가된 데이터 리턴
  • show() : 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴
  • clear() : 현재 스택에 포함되어 있는 모든 데이터 삭제
  • search() : 주어진 객체를 찾아서 그 위치 반환
  • empty() : 스택이 비어있는지 여부 리턴

public class MignonStack {
    private ArrayList<Object> listStack = new ArrayList<Object>();

    // push()
    public Object push(Object item) {
        listStack.add(item);
        return item;
    }

    // pop()
    public Object pop() {
        // 만일 Stack 이 비어있다면 peek() 메서드가 EmptyStackException() 을 발생시킨다.
        Object obj = peek();
        listStack.remove(listStack.size() - 1);
        return obj;
    }

    // peek()
    public Object peek() {
        if(listStack.size() == 0) throw new EmptyStackException();
        // 마지막 요소 반환하기
        return listStack.get(listStack.size() - 1);
    }

    // search()
    public int search(Object o) {
        // 끝에서부터 객체를 찾아서 저장된 위치의 index를 반환
        int i = listStack.lastIndexOf(o);

        if(i >= 0) { // 객체를 찾은 경우
            return i;
        }
        return -1; // 객체를 찾지 못한 경우

        // return listStack.lastIndexOf(o); 로만 해도 위의 내용이 구현되어 있어서 사실 동일
    }

    // size()
    public int size() {
        return listStack.size();
    }

    // empty()
    public boolean empty() {
        return listStack.size() == 0;
    }

    // clear()
    public void clear() {
        listStack.clear();
    }

    // show()
    public String show() {
        return listStack.toString();
    }
}