[260608]스택

목차

• 스택의 특징
• 스택 응용 예시

스택의 특징

스택(Stack)이란 데이터를 차곡차곡 쌓아 올리는 데이터 관리 방식이다.

• LIFO(Last in First Out)구조

  	LIFO는 마지막에 들어온 데이터를 가장 먼저 빼낸다는 뜻이다.
  	이러한 특성을 활용하여, 뒤로가기(Undo)기능을 만들 수 있다. 

또한 스택은 Java에서 제공하는 내장 자료구조를 사용하여 구현없이 사용이 가능하다.

스택의 장점

• 구현이 간단
  스택은 배열과 리스트를 사용하여 간단하게 구현할 수 있고, 연산(push, pop, peek 등)도 간단하여 이해와 구현이 쉽다.
• 빠른 연산 속도
  위의 연산(push, pop, peek)들은 전부 O(1)시간 내에 수행되기 때문에 연산의 속도가 빠르다.
  또한, 데이터의 추가 및 삭제는 전부 한쪽 스택 데이터의 마지막 부분에서 일어나기 때문에 효율적이다.
• 메모리 관리에 유용
  메모리 할당과 해제를 체계적으로 관리할 수 있다.

스택의 단점

• 접근성의 제한
  데이터의 추가 및 삭제가 한쪽 끝에서만 일어나기 때문에, 연산 속도는 빠를지라도 중간 데이터에 직접 접근하는등의 작업이 불가능하다. 즉, 데이터의 특정 위치에 접근하는 작업이 스택을 활용하기엔 부적합하다.
• 고정된 크기 문제
  스택을 구현할때에는 미리 배열이나 리스트의 크기를 정해야 하기 때문에, 확장이 어렵다.

스택을 활용하는 방식

스택은 기본적으로 순서를 정해서 실행하는 구조이다. 이러한 특징을 활용할 수 있는 방식으로는,

1.깊이 우선 탐색(DFS): 제일 깊은곳까지 내려가는 알고리즘을 가진 DFS를 구현할때 스택을 이용한다.
2.괄호 검사: 수식에서 괄호의 짝을 맞추는데 사용된다.
3.함수 호출 관리: 함수 호출 시 호출스택(Call Stack)을 이용하여 함수의 실행 순서를 관리한다.

스택 응용 예시

괄호 짝 검사

스택에 괄호를 집어넣고 짝이 맞으면, 즉 스택이 비어있다면 유효한 수식이고, 그렇지 않다면 잘못된 수식이다. 이를 실제 코드로 구현하는 방법을 알아보자면,

접근방법:
- 스택의 LIFO 특성을 활용하여 괄호 매칭 검사
- 괄호 문자열 순회
  - 여는 괄호가 나오면 스택에 저장
  - 닫는 괄호가 나오면 스택의 top에 있는 괄호와 매칭
- 매칭 실패 시 false 반환

세부구현:
1. 여는 괄호('(', '{', '[') 처리
  1-1. 스택에 push

2. 닫는 괄호(')', '}', ']') 처리
  2-1. 스택이 비어있으면 false 반환
  2-2. 스택 top 괄호와 매칭되지 않으면 false 반환
  2-3. 매칭되면 pop 수행

3. 최종 반환
  3-1. 스택이 비어있으면 true
  3-2. 스택에 괄호가 남아있으면 false

import java.util.ArrayDeque;
import java.util.Deque; //스택 라이브러리

class Solution {
   public boolean isValidParentheses(String s) {

       // 스택 생성
       Deque<Character> stack = new ArrayDeque<>();
       
       // 문자열 순회
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           
           // 1. 여는 괄호('(', '{', '[') 처리
           if (c == '(' || c == '{' || c == '[') {
               // 1-1. 스택에 push
               stack.push(c);
           }
           // 2. 닫는 괄호(')', '}', ']') 처리
           else {
               // 2-1. 스택이 비어있으면 false 반환
               if (stack.isEmpty()) {
                   return false;
               }
               
               // 2-2. 스택 top 괄호와 매칭되지 않으면 false 반환
               char top = stack.pop();
               if ((c == ')' && top != '(') || 
                   (c == '}' && top != '{') || 
                   (c == ']' && top != '[')) {
                   return false;
               }
               // 2-3. 매칭되면 pop 수행 (이미 위에서 pop 완료)
           }
       }
       
       // 3. 최종 반환
       // 3-1. 스택이 비어있으면 true
       // 3-2. 스택에 괄호가 남아있으면 false
       return stack.isEmpty();
   }

   public static void main(String[] args) {
       Solution solution = new Solution();

       // 테스트 케이스
       String[] testCases = {
           "()",            // true: 단순 괄호 쌍
           "{[]}",          // true: 중첩된 괄호
           "()[]{}",        // true: 여러 괄호 쌍
           "(]",            // false: 괄호 불일치
           "([)]",          // false: 교차된 괄호
           "(",             // false: 닫는 괄호 부족
           ")",             // false: 여는 괄호 부족
           ""              // true: 빈 문자열
       };

       // 테스트 실행 및 결과 출력
       for (String test : testCases) {
           boolean result = solution.isValidParentheses(test);
           System.out.println("입력: " + test);
           System.out.println("결과: " + result);
           System.out.println();
       }
   }
}