[JAVA][자료구조] Stack

목표

• Stack 관련 메소드를 알아보자.

Stack 클래스

Stack은 데이터를 후입선출(LIFO, Last-In-First-Out)의 구조로 저장하는 컬렉션 클래스입니다.

스택은 주로 임시적인 데이터 저장이나 메소드 호출 등에 사용됩니다.

 

위의 그림에서 숫자 1 2 3 4는 search()메소드의 반환될 index 값 입니다.

 

숫자를 각 요소라고 생각했을 때, 위의 상태로 만드려면 4 3 2 1 순서대로  삽입을 해야합니다.

위의 상태에서 pop을 5번하면 1 2 3 4 마지막 다섯번째에서 예외(EmptyStackException)를 던집니다.

 

아래는 Stack 클래스의 내용입니다.

class Stack<E> extends Vector<E> {
    public Stack() {
    }

    public E push(E item) {
        addElement(item);

        return item;
    }

    /**
     * @return  The object at the top of this stack 
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * @return  the object at the top of this stack 
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     * @return  true if and only if this stack contains no items; false otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

Stack 관련 메소드

• push(element) : 스택 맨 위에 요소(element)를 추가합니다.
• pop() : 스택 맨 위의 요소를 제거하고 반환합니다.
• peek() : 스택 맨 위의 요소를 반환하지만, 제거하지 않습니다.
• empty() : 스택이 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• search(element) : 해당 요소가 발견되면 상대적인 위치(맨 위가 1)를 반환하며, 발견되지 않으면 -1을 반환합니다.

시간복잡도

• 조회: O(n)
  조회는 앞에서부터 순서대로 조회하기때문에 O(n)이다
• 삽입, 삭제: O(1)

예시

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek()); // 3 출력
System.out.println(stack.search(3)); // 1 출력
System.out.println(stack.pop()); // 3 출력
System.out.println(stack.peek()); // 2 출력
System.out.println(stack.search(3)); // -1 출력
System.out.println(stack.search(2)); // 1 출력
System.out.println(stack.search(1)); // 2 출력
System.out.println(stack.empty()); // false 출력