[DATA STRUCTURE] Stack 스택

What is Stack

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

Basic Operations

• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.
• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.

스택(Stack)의 사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

• 재귀 알고리즘

재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.

재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.

스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.

또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.

• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
• Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

public class StackTest1 {
    public static void main(String[] args) {
        Stack<Object> stack = new Stack<>();
        int[] arr = {10,20,30,40,50};
        System.out.println(stack.empty()); //True or False
        System.out.println("----------------------------------------------");
        Arrays.stream(arr).forEach(e -> System.out.println(stack.push(e)));
        System.out.println("----------------------------------------------");
        stack.push(7);
        System.out.println(stack); // 10,20,30,40,50,7
        System.out.println("----------------------------------------------");
        stack.pop();
        System.out.println(stack);//pop 7 out
        System.out.println("----------------------------------------------");
        System.out.println("current top is : " +stack.peek()); //top is 50
        System.out.println("----------------------------------------------");
        // 스택에 해당 값이 있는지 확인하고 없으면 -1, 있으면 해당하는 인덱스 값 반환(맨 위부터 1)
        System.out.println("Search(30) index is :" + stack.search(30)); // search element in stack
        System.out.println("----------------------------------------------");
        while (!stack.empty()) {
            // LIFO
            // pop out all elements in stack
            System.out.println(stack.pop());
            
        }
    }
}

References

• https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm