스택(Stack)

특징

• 스택은 배열을 사용하면 고정된 크기를 가질 수 있으며, 연결 리스트를 사용하면 동적으로 크기를 변경할 수 있습니다.
• 들어온 순서의 반대 순서로 나갑니다. (LIFO - 후입선출)

메서드

Stack에서 사용하는 메서드에 대해서 알아보겠습니다.
push(), pop(), peek() 메서드는 모두 O(1)이라는 시간복잡도를 갖습니다.

메서드	설명
Object push()	원소를 객체에 삽입	스택이 꽉 찬 상태에서 데이터를 더 넣게되면 Stack Overflow condition이 됩니다.
Object peek()	다음에 빼낼 원소 조회. 스택의 꼭대기 요소 반환
Object pop()	원소를 빼내서 반환	스택이 비어있는 상태에서 꺼내려하면 Stack Underflow condition이 됩니다.
boolean empty()	Stack이 비어있는지 여부 반환
int search(Object o)	주어진 객체를 찾아 위치 반환	위치는 1부터 시작하고 없으면 -1을 반환합니다.

⁉️ Stack Overflow / Underflow

• Stack Overflow
  • 스택이 고정된 크기를 가지는 경우, 예를 들어 배열 기반의 스택에서, 스택이 꽉 찬 상태에서 push 메서드를 호출하면 발생합니다.
    일반적으로 재귀 함수가 너무 깊어져 스택이 한계에 도달할 때도 발생할 수 있습니다.

    public void recursiveCall() {
    // 재귀 호출이 계속되면서 Stack Overflow 발생
      recursiveCall(); 
    }

💡 배열 기반의 스택은 고정된 크기를 가지기 때문에 Stack Overflow의 위험이 있지만, 연결 리스트를 사용하면 동적으로 크기를 조정할 수 있어 이러한 위험이 줄어들게 됩니다!

• Stack Underflow
  • 스택이 비어 있는 상태에서 pop 메서드를 호출할 때 발생합니다.
    예를 들어, 잘못된 루프 조건이나 논리 오류로 인해 비어 있는 스택에서 요소를 꺼내려고 할 때 발생합니다.

  Stack<Integer> stack = new Stack<>();
  // 비어 있는 상태에서 pop 호출 -> Stack Underflow 발생
  stack.pop(); 

코드로 보기

public class StackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        stack.push(1);
        stack.push(2);
        stack.push(3);

		System.out.println("=====push=====");
        System.out.println(stack);
        
        System.out.println("=====pop=====");
        System.out.println(stack.pop());

        System.out.println("=====peek=====");
        System.out.println(stack.peek());

        System.out.println("=====empty=====");
        System.out.println(stack.empty());

        System.out.println("=====search=====");
        System.out.println(stack.search(1));
    }
}

활용 예시

• 함수 호출 관리: 함수 호출 시마다 호출 스택에 함수가 추가되고, 함수가 끝나면 스택에서 제거됩니다.
• 괄호 짝 검사: 컴파일러나 파서에서 중괄호, 대괄호 등의 짝을 검사할 때 스택이 사용됩니다.
• 깊이 우선 탐색(DFS): 그래프 탐색 알고리즘인 DFS에서 스택이 사용됩니다.
• Undo 기능: 문서 편집기에서 작업을 취소할 때, 이전 상태를 저장하고 되돌리는 기능에서 스택이 사용됩니다.

참고

• Stack(스택) 클래스 사용법 및 함수(Method) 정리
• 자바 Stack 구조 & 사용법 정리