[자료구조] 스택(Stack)이란?

1. 스택(Stack)이란?

스택은 컴퓨터 과학에서 사용되는 중요한 자료구조 중 하나입니다. 스택은 데이터를 저장하고 검색하는 데 사용되며, 주로 "Last In, First Out" (LIFO) 원칙을 따릅니다. 이것은 가장 최근에 추가된 항목이 가장 먼저 제거되는 원리를 의미합니다.

2. 스택의 구성 요소

스택은 다음과 같은 구성 요소로 이루어져 있습니다.

• 데이터 요소: 스택에 저장되는 각 항목 또는 데이터 요소입니다.
• 맨 위(Top): 스택의 맨 위에 위치한 데이터 요소를 가리키는 포인터입니다.

3. 스택의 기본 동작

스택은 다음과 같은 기본 동작을 갖습니다.

• Push: 스택에 데이터를 추가하는 작업입니다. 새로운 항목은 스택의 맨 위에 쌓이게 됩니다.
• Pop: 스택에서 가장 위에 있는 데이터를 제거하는 작업입니다. 스택의 맨 위 항목이 제거됩니다.
• Peek (또는 Top): 스택의 맨 위에 있는 데이터를 확인하지만 제거하지는 않습니다.
• isEmpty: 스택이 비어있는지 여부를 확인하는 작업입니다.

4. 스택 vs 리스트 비교

스택과 리스트의 주요 차이점은 다음과 같습니다.

• 스택은 LIFO(마지막에 추가된 것이 먼저 제거) 원칙을 따르지만, 리스트는 데이터를 일반적으로 선형 목록으로 저장하며, 순서가 중요하지 않습니다.
• 스택은 주로 데이터의 추가와 제거에 특화되어 있으며, 이러한 연산이 빠릅니다.
• 리스트는 데이터의 삽입 및 삭제 연산이 다양한 위치에서 가능하지만, 스택은 항상 맨 위에서만 연산이 수행됩니다.

5. 배열 활용 문제 풀어보기

import java.util.Stack;

public class BracketMatcher {
    public static void main(String[] args) { // Q1
        String input = "(()())"; 
        
        if (isValid(input)) {
            System.out.println("올바른 괄호");
        } else {
            System.out.println("올바르지 않은 괄호");
        }
    }

    public static boolean isValid(String s) {
        Stack<_________> stack = new Stack<>(); // Q2
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.______(c); // Q3
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') { // Q4
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

• Q.1. 위의 실행 결과는 무엇일까요?
• Q.2. _에 들어가야할 데이터 타입은 무엇일까요?
• Q.3. _에 들어가야할 메소드는 무엇일까요?(값을 넣는 메소드)
• Q.4. isEmpty() 메소드와 pop()메소드의 역할은 무엇일까요?