스택

스택 (Stack)

스택(Stack)은 데이터를 저장하는 선형 자료구조로, 후입선출(LIFO: Last-In, First-Out) 방식으로 작동

기본 연산

연산	설명
push()	데이터를 스택에 추가
pop()	스택의 최상단 데이터 제거 및 반환
peek()	최상단 데이터 조회 (제거 X)
isEmpty()	스택이 비어 있는지 확인

Java에서 Stack 사용

1. Stack 클래스

• java.util.Stack 클래스를 사용할 수 있지만, 성능 및 설계상 이유로 권장되지 않음.

2. ArrayDeque 사용 (권장)

• 가장 효율적이고 빠른 스택 구현 방식
• 배열 기반이므로 공간과 속도에서 유리함

import java.util.*;

Deque<Integer> stack = new ArrayDeque<>();

3. LinkedList 사용

• 연결 리스트 기반 스택
• Deque 인터페이스로 선언하면 같은 방식으로 사용 가능

import java.util.*;

Deque<Integer> stack = new LinkedList<>();

 

Stack 사용 예시

1. 스택 선언

Deque<Integer> stack = new ArrayDeque<>();

 

2. push - 데이터 추가

stack.push(1);  // [1]
stack.push(2);  // [1, 2]
stack.push(3);  // [1, 2, 3]

 

3. peek - 최상단 원소 조회

int top = stack.peek();  // 3

 

4. pop - 최상단 원소 제거

stack.pop();  // [1, 2]
stack.pop();  // [1]

 

5. isEmpty - 스택 비어 있는지 확인

boolean empty = stack.isEmpty();  // false

 

Deque 기반 스택과 덱(Deque)의 차이

Deque은 양쪽 끝에서 삽입/삭제가 가능한 자료구조로, 스택처럼 한쪽 끝만 사용할 수도 있고, 덱 기능도 함께 사용할 수 있음!

Deque 사용 예시

Deque<Integer> d = new ArrayDeque<>();

// 앞에 추가
d.addFirst(10);

// 뒤에 추가
d.addLast(20);

// 앞에서 제거
d.removeFirst();

// 뒤에서 제거
d.removeLast();

push(), pop() 같은 스택 연산은 내부적으로 addFirst(), removeFirst() 와 동일하게 동작

코딩 테스트 활용

1. 괄호 짝 검사 / 짝 제거 문제

• 스택의 대표적인 문제 유형
• 새 문자가 들어올 때, 스택 최상단과 비교하여 짝이면 pop(), 아니면 push()

예시: 올바른 괄호 문자열 판별

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            stack.pop();
        }
    }
    return stack.isEmpty();
}

 

2. 재귀 호출과 스택

• 재귀 함수는 내부적으로 스택을 사용하여 호출 상태를 관리
• 함수가 호출될 때마다 스택 프레임이 쌓이고, 리턴될 때마다 하나씩 제거되며 이전 상태로 돌아감..