[자료구조] 스택(Stack)

📌스택 : 후입선출(Last In First Out, LIFO) 방식을 따르는 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 꺼내지는 구조를 가지고 있다.

 

스택 구현

 

1. Deque<E>를 스택처럼 사용

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

2. Stack<E> 사용
   

   Stack<Integer> stack = new Stack<>();

 

기본 메서드

• push(E item) : 스택의 맨 위에 요소를 추가
• pop() : 스택의 맨 위에 있는 요소를 제거하고 반환
• peek() : 스택의 맨 위에 있는 요소를 제거하지 않고 반환
• isEmpty() : 스택이 비어 있는지 여부를 확인
• size() : 스택 안의 요소 개수 반환

 

코딩 테스트 빈출 유형

 

괄호 유효성 검사

: "다양한 유형의 괄호 (), {}, [] 가 포함된 문자열에서 올바르게 괄호가 짝지어져 있는가? "

• 풀이법 ) 여는 괄호는 스택에 쌓고 닫는 괄호가 나올 때마다 스택에서 짝이 맞는 여는 괄호를 꺼낸다.

📄 유형 이해 코드 📄

public boolean isValid(String s) {
	//ArrayDeque<>인터페이스를 통해 스택 구현
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
    	// 여는 괄호 -> 스택에 쌓기
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } 
        else {
        	//스택이 비어있을 경우 false값 반환
            if (stack.isEmpty()) return false;
            //스택의 맨 위에 있는 요소 제거 후, open값에 반환
            char open = stack.pop();
            //isMatching메서드 이용하여 다른 경우 false값 반환
            if (!isMatching(open, c)) return false;
        }
    }
    //isEmpty메서드를 사용하여 스택이 비어있는지 여부 확인
    return stack.isEmpty();
}

//isMatching 메서드 정의: open값과 close값이 짝을 이루면 true, 그렇지 않으면 false값 반환
private boolean isMatching(char open, char close) {
    return (open == '(' && close == ')') || (open == '{' && close == '}') || (open == '[' && close == ']');
}

 

 

2. 최솟값 스택 구현

• 기본 스택 외에 최솟값을 저장하는 보조 스택을 사용해야 한다.

📄 유형 이해 코드 📄

class MinStack {
    //기본 스택 구현
    private Deque<Integer> stack = new ArrayDeque<>();
    //최소값을 저장하는 보조 스택 구현
    private Deque<Integer> minStack = new ArrayDeque<>();
    
    //push 메서드 작성
    public void push(int x) {
        stack.push(x);
        //보조스택이 비어있거나, 매개변수 x가 보조 스택 맨 위의 요소보다 같거나 작을 경우
        if (minStack.isEmpty() || x <= minStack.peek()) {
        	//스택에 추가
            minStack.push(x);
        }
    }
    
    //pop 메서드 작성
    public void pop() {
    	//기본 스택의 맨 위의 요소 값이 보조 스택의 맨 위의 요소값과 같을 경우
        if (stack.pop().equals(minStack.peek())) {
        	//보조 스택의 맨 위의 요소를 제거한다.
            minStack.pop();
        }
    }
    //top 메서드 작성
    public int top() {
    	//기본 스택의 맨 위 요소 반환
        return stack.peek();
    }
    
    //getMin() 메서드 작성
    public int getMin() {
    	//보조 스택의 맨 위 요소 반환
        return minStack.peek();
    }
}

 

스택 사용 시 유의 사항

• 시간 복잡도
• 메모리 관리 : 재귀함수의 깊이가 너무 깊을 경우 스택 오버플로우 발생. 
  → 재귀를 반복문으로 대체해야 한다
• Deque 사용 권장 : Stack는 동기화 문제로 상대적으로 성능이 좋지 않다.