스택, 큐

스택 vs 큐

스택이란?

차곡 차곡 쌓아 올린 형태의 자료 구조
특징 - 한 방향(top)으로만 데이터를 넣고 빼고 할 수 있다
=> 가장 먼저 넣은 자료가 가장 마지막에 꺼낼 수 있다(LIFO, Last-In-First-Out)
ex.
웹 브라우저 방문 기록(뒤로 가기)
되돌리기 기능
접시 쌓기
프링글스 과자

vector로 -> thread safe 하지만 무거움 => arrayList 사용 / Deque
https://docs.oracle.com/javase/8/docs/api/index.html?overview-summary.html

큐란?

ex.
은행 업무
프로세스 관리
줄 서기
콜센터 전화 연결

https://school.programmers.co.kr/learn/courses/30/lessons/12909

import java.util.ArrayDeque;
class Solution {
    boolean solution(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] a = s.toCharArray();
        for(char c : a){
            if(c == '('){
                stack.push(c);
            } else{
                if(stack.isEmpty()||stack.pop()==c){
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

스택없이

// 여는 괄호 ( 는 스택에 넣는다.
// 닫는 괄호 ) ?? 이전 문자가 여는 괄호 확인
// 제공된 배열을 그대로 사용
// 2개의 인덱스 ( oi : 여는 괄호 '(' 를 위한 인덱스
// (((((())))) => (((((XX))))
public class Solution_올바른괄호2 {
    
    public static void main(String[] args) {
        System.out.println(new Solution_올바른괄호2().solution("(((((XX)()())))"));
    }
    
    boolean solution(String s) {
        
        char[] input = s.toCharArray();
        int len = input.length;
        int xCnt = 0; // X 로 표시된 글자 수
        
        for (int i = 0, oi = 0; i < len; i++) {
            if( input[i] == ')' ) { // 닫는 괄호
                if( input[oi] != '(' ) return false;
                
                // 두 괄호가 대응 일치 => X 로 표시
                input[i] = 'X';
                input[oi] = 'X';
                xCnt += 2;
                
                while( oi > 0 && input[oi] == 'X' ) oi--;
                
            }else { // 여는 괄호
                oi = i; // 마지막 여는 괄호의 index
            }
        }
        
        return xCnt == len;
    }
}