Dico

[Java] Class Stack

Collection Framework

데이터 군을 저장하는 클래스들을 표준화한 설계

컬렉션 Collection :  다수의 데이터. 데이터 그룹

프레임웍 Framework :  표준화된 프로그래밍 방식.

Class Stack

마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out) 방식의 자료 구조.  ex) 일반 독

넣는 순서와 꺼내는 순서가 반대다.

컬렉션 프레임웍 이전부터 존재했기 때문에 Vector로부터 상속받아 구현되었다.

Java에서 Stack 클래스로 구현하여 제공하고 있다.

method

반환타입이름설명
  boolean  empty()  Stack이 비어있는 지 확인
  E  peek()  맨 위에 저장된 객체를 반환. 객체를 꺼내진 않음.
  비어있으면 EmptyStackException 발생
  E  pop()  맨 위에 저장된 객체를 꺼낸다. 비어있으면 EmptyStackException 발생
  E  push(E item)  객체를 저장
  int  search(Object o)  주어진 객체를 찾아 그 위치(1~)를 반환. 못 찾으면 -1

실제 코드

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

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

        return item;
    }

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

        obj = peek();
        removeElementAt(len - 1); // 마지막 요소 삭제. 배열의 index가 0부터 시작하므로 1을 뺀다.

        return obj;
    }

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

        if (len == 0)
            throw new EmptyStackException(); 
        return elementAt(len - 1); // 마지막 요소 반환. 배열의 index가 0부터 시작하므로 1을 뺀다.
    }

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

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

        if (i >= 0) {
            return size() - i;  // Stack은 맨 위에 저장된 객체의 index를 1로 정의한다.
        }
        return -1;              // 해당 객체를 찾지 못하면 -1 반환.
    }

    private static final long serialVersionUID = 1224463164541339165L;
}

Example01

웹 브라우저의 뒤로/앞으로 가기, 워드프로세서의 되돌이기 기능을 구현한 예제.

import java.util.Stack;

public class Test {
    public static Stack<Integer> back = new Stack<>();
    public static Stack<Integer> forward = new Stack<>();

    public static void main(String[] args) {

        goIndex(0);
        goIndex(1);
        goIndex(2);
        status();

        goBack();
        status();

        goBack();
        status();

        goForward();
        status();
    }

    public static void goIndex(int index) {
        back.push(index);
        if (!forward.empty()) {
            forward.clear();
        }
    }

    public static void goForward() {
        if (!forward.empty()) {
            back.push(forward.pop());
        }
    }

    public static void goBack() {
        if (!back.empty()) {
            forward.push(back.pop());
        }
    }

    public static void status() {
        System.out.println("back : " + back);
        System.out.println("forward : " + forward);
        System.out.println("now index : " + back.peek());
    }
}
back : [0, 1, 2]
forward : []
now index : 2

back : [0, 1]
forward : [2]
now index : 1

back : [0]
forward : [2, 1]
now index : 0

back : [0, 1]
forward : [2]
now index : 1

Example02

괄호가 올바른지 확인하는 예제.

import java.util.Stack;

public class Test {
    public static void main(String[] args) {

        Stack<String> stack = new Stack<>();
        String expression = "((STACK) Example 02";
        
        try {
            for (int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);
                if (ch == '(') {
                    stack.push(ch + "");
                } else if (ch == ')') {
                    stack.pop();
                }
            }
        
            if (stack.isEmpty()) {
                System.out.println("The parentheses match.");
            } else {
                System.out.println("Parentheses do not match.");
            }
        } catch (Exception e) {
            System.out.println("Parentheses do not match.");
        }
    }
}
Parentheses do not match.

Stack API

참고 서적: 자바의 정석 3판 2