Stack

Stack이란?

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

 

Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 
3. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
4. 그래프의 깊이 우선 탐색(DFS)에서 사용
5. 재귀적(Recursion) 함수를 호출 할 때 사용

 

Stack 사용법 

Stack 선언

public void stackCreate() {
    Stack st = new Stack(); // 타입 설정x Object로 선언
    Stack<StackTestClass> demo = new Stack<StackTestClass>(); // class타입으로 선언
    Stack<Integer> i = new Stack<Integer>(); // Integer타입 선언
    Stack<Integer> i2 = new Stack<>(); // 뒤의 타입 생략 가능

    Stack<String> s = new Stack<String>(); // String타입 선언
    Stack<Character> ch = new Stack<Character>(); // Char타입 선언
}

자바에서 stack을 선언하려면 <stack>import java.util.Stack 을 import 한 뒤 Stack<Element> stack = new Stack<>();과 같은 형식으로 선언하면 됩니다. 

 

Stack 값 추가

public void stackPush() {
    Stack<String> s = new Stack(); // 타입 설정x Object로 선언

    // Stack 값 추가
    s.push("Hello");

    // World를 반환 -> String
    String world = s.push("World");

    // true를 반환 -> boolean
    boolean bool = s.add("World");

    System.out.println("s = " + s);
    System.out.println("world = " + world);
}

Stack에 값을 추가하고 싶다면 push(value)라는 메소드를 활용하면 됩니다. Stack에 위의 예제와 같이 값을 계속해서 추가해나간다면 아래 그림처럼 데이터가 쌓이게 됩니다.

Stack 값 삭제

public void stackPop() {
    Stack<String> s = new Stack<String>();

    // Stack 값 추가
    s.push("Hello");
    s.push("World");

    System.out.println(s); // 결과 출력

    s.pop(); // Stack 값 제거

    System.out.println("s1 = " + s);
    // 결과 출력

    s.clear(); // Stack 값 전체 제거

    System.out.println("s2 = " + s);
    // 결과 출력

    System.out.println(s); // 결과 출력
}

 스택에서 값을 제거하고싶다면 pop()이라는 메서드를 사용하면 됩니다. pop을 하면 가장 위쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다. 스택의 값을 모두 제거하고싶다면 clear()라는 메서드를 사용하면 됩니다.

 

Stack의 가장 상단의 값 출력

public void stackPrint() {
    Stack<String> s = new Stack<>();

    // Stack 값 추가
    s.push("Hello");
    s.push("World");

    // firstElement(), lastElement(), peek()을 사용 -> 처음, 마지막, 마지막 값을 불러온다
    System.out.println("처음 값 : " + s.firstElement());
    System.out.println("마지막 값 : " + s.lastElement());
    System.out.println("마지막 값 : " + s.peek());

    // get(i) 메서드를 사용하여 Stack의 Index 값을 출력
    for (int i = 0; i < s.size(); i++) {
        System.out.print(s.get(i) + " ");
    }

    System.out.println();

    // 향상된for문을 사용하여 Stack의 값을 출력
    for (String str : s) {
        System.out.print(str + " ");
    }
    // Iterator를 사용하여 Stack의 값을 출력
    Iterator iter = s.iterator();
    while (iter.hasNext())
        System.out.print(iter.next() + " ");
}

스택의 가장 위에 있는 값을 출력하고 싶다면 peek()라는 함수를 사용하면 됩니다. 아래 그림과 같이 가장 마지막에 들어간 값이 출력됩니다.

Stack의 검색메서드

public void stackSearch() {
    Stack<String> s = new Stack<String>();

    // Stack 값 추가
    s.push("Hello");
    s.push("World");
    s.push("Hello");
    s.push("World");

    System.out.println("값 검색(contains) : " + s.contains("Hello"));
    System.out.println("값 검색(indexOf) : " + s.indexOf("Hello"));
}

 

Stack의 기타 메서드

public void stackEtc() {
    Stack<Integer> stack = new Stack<>(); //int형 스택 선언
    stack.push(1);       // stack에 값 1 추가
    stack.push(2);       // stack에 값 2 추가
    stack.empty();            // stack이 비어있는제 check (비어있다면 true)
    stack.contains(1);        // stack에 1이 있는지 check (있다면 true)
    System.out.println("s.size = " + s.size()); // (stack size)
}

그 밖에도 stack에는 크기를 구하는 size()메서드와 stack이 비어있는지 확인하는 empty() 메서드(비어있다면 true, 그렇지 않다면 false를 return) stack의 값을 search하는 contains(int value)함수가 있습니다.