[자료구조] 스택(Stack) (Java)

 

스택이란? 쉽게 보면 박스 쌓기이다.

흔히 박스는 아래에서부터 위로 차곡차곡 쌓는다.

아래에 있는 박스를 치우기 위해서는 반드시 위에 있는 박스를 내려야 한다.

먼저 쌓은 것이 나중에 나온다. 나중에 쌓은 것이 먼저 나온다.

=> 선입후출(FILO), 후입선출(LIFO)

 

차근차근 스택에  쌓아보기

삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()의 과정을 수행해 보자.

 

 

삽입(5)

5

 

삽입(2)

5 2

 

삽입(3)

5 2 3

 

삽입(7) 

5 2 3 7

 

삭제() 

5 2 3

 

삽입(1)

5 2 3 1

 

삽입(4)

5 2 3 1 4

 

삭제() 

5 2 3 1

=> 삽입을 통해 데이터를 차례대로 쌓고 삭제를 통해 가장 마지막에 넣은 데이터를 내보낸다.

 

코드로 구현

 

Stack<Integer> s = new Stack<>();

// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();

while (!s.empty()) {
    System.out.print(s.peek() + " ");
    s.pop();
}

 

스택과 함께 쓰이는 함수들

 

원소 추가

- push()

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

    return item;
}

매개변수 값이 스택에 삽입되고 해당 원소를 반환한다.

 

원소 삭제

- pop()

public synchronized E pop() {
    E obj;
    int len = size();

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

    return obj;
}

스택 최상단 값이 삭제되고 해당 원소를 반환한다.

 

위의 코드의 while문 부분을 pop만을 사용해서 더 간단히 구현이 가능하다.

while (!s.empty()) {
    System.out.print(s.pop() + " ");
}

 

최상단 값 확인

- peek()

public synchronized E peek() {
    int len = size();

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

스택 최상단 값을 반환한다.

스택이 비어있는 경우 해당 메서드를 호출하면 EmptyStackException을 발생시킨다.

 

스택이 비어있는지 확인

- empty()

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

스택이 비어있는 경우는 true를, 비어있지 않은 경우는 false를 반환한다.

 

특정 원소 찾기

- search()

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

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

최상단으로부터 해당 원소가 몇 번째에 위치하는지를 반환한다. (최상단의 경우 1)

 

- 같은 값의 원소가 여러 개 존재하는 경우: 최상단과 가까운 값의 순번

- 해당 원소가 존재하지 않는 경우: -1

 

예시를 들어 살펴보자.

3 1 3 7

System.out.println(s.search(7));  // 1
System.out.println(s.search(3));  // 2

7이 최상단에 존재하므로 1

3은 여러 개 존재하므로 최상단과 가까운 값의 순번인 2가 출력된다.

   

 

Reference

이것이 코딩테스트다 - 나동빈