자바[JAVA] 자료구조 구현 5 - Stack Interface

들어가기 전.

 

Stack 이나 Queue 는 이전 자료구조 수업에서 설명한 바가 있으니 가볍게 넘어가겠습니다.

2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack

 

0. Stack

 

스택은 컴퓨터에서 아주 많이 사용되는 자료구조입니다. 예를 들어, 웹 사이트의 "뒤로 가기" 기능, 가까이는 IDE 에서 Undo 기능 또한 스택으로 구현됩니다. 스택은 말 그대로 쌓아놓은 더미를 뜻합니다. 쉽게 이해하자면 벽돌을 쌓는 것과 유사합니다. 가장 먼저 쌓는 벽돌은 가장 아래에 위치할 것이고, 가장 나중에 들어온 벽돌은 가장 위에 위치할 것입니다. 벽돌을 다 쌓은 후 벽돌을 치운다고 했을 때, 가장 먼저 치워야 하는것은 가장 위에 있는 벽돌, 즉 가장 마지막에 올려놓은 벽돌이 될 것입니다. (가장 아래의 벽돌을 가장 먼저 뺀다면 쌓아놓은 벽돌은 무너지겠죠...?)

 

이러한 특징을 후입선출(LIFO) 라고 합니다. 나중에 서술할 큐는 이와 반대로 선입선출(FIFO) 입니다. 이는 먼저 들어온 것이 먼저 나가는 특징을 말합니다.

 

스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 자주 사용됩니다. 수식 괄호 검사, 페이지 뒤로 가기, 실행 취소등에 사용됩니다.

 

1. Stack Interface in JAVA

 

자바에 구현되어있는 스택 인터페이스의 대표적인 메소드들 입니다.

2. Stack Interface

 

package Interfaces;

public interface Stack <E> {

    /**
     * 스택의 맨 위에 요소를 추가합니다.
     *
     * @param item 스택에 추가할 요소
     * @return 스택에 추가된 요소를 반환
     */
    E push(E item);

    /**
     * 스택의 맨 위에 있는 요소를 제거하고 제거 된 요소를 반환합니다.
     *
     * @return 제거 된 요소 반환
     */
    E pop();

    /**
     * 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
     *
     * @return 스택의 맨 위에 있는 요소 반환
     */
    E peek();

    /**
     * 스택의 상반 부터 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
     * 중복되는 원소가 있을경우 가장 위에 있는 요소의 위치가 반환됩니다.
     *
     * @param value 스택에서 위치를 찾을 요소
     * @return 스택의 상단부터 처음으로 요소와 일치하는 위치를 반환.
     *         만약 일치하는 요소가 없을 경우 -1 을 반환
     */
    /*
     *         ________
     *         | a    |
     * idx 3   |______|   search("w")
     *         | e    |   --> 상단(idx 3)으로 부터 3번 째에 위치
     * idx 2   |______|       == return 되는 값 : 3
     *         | w    |
     * idx 1   |______|
     *         | k    |
     * idx 0   |______|
     *
     */
    int search(Object value);

    /**
     * 스택의 요소 개수를 반환합니다.
     *
     * @return 스택에 있는 요소 개수를 반환
     */
    int size();

    /**
     * 스택에 있는 모든 요소를 삭제합니다.
     */
    void clear();

    /**
     * 스택에 요소가 비어있는지를 반환합니다.
     *
     * @return 스택에 요소가 없을 경우 {@code true}, 그 외의 경우 {@code false}를 반환
     */
    boolean empty();
}