[코테] 자료구조 - 덱 메서드 정리

 

스택과 큐 클래스는 이제 자바에서 레거시가 되었다.

 

대신 자바에서 스택과 큐를 한번에 사용하기위한 목적으로 덱을 쓴다.

 

Deque<Integer> deque = new ArrayDeque<>(); // 덱 생성

addFirst()  // 맨 앞에 요소를 추가 (스택의 push)

addLast()  //  맨 뒤에 요소를 추가합니다.

offerFirst() // 맨 앞에 요소를 추가(가득 찼을 때 예외 발생 안 함), 안전한 추가 보장

offerLast()  // 맨 뒤에 요소를 추가합니다 (가득 찼을 때 예외 발생 안 함).

removeFirst()  // 맨 앞 요소를 제거하고 반환합니다.(없으면 에러반환) (스택의 pop)

removeLast() // 맨 뒤 요소를 제거하고 반환합니다.(없으면 에러반환)

pollFirst()  //  맨 앞의 요소를 제거하고 반환합니다 (비어 있으면 null 반환), 안전한 삭제 보장

pollLast() //  맨 뒤의 요소를 제거하고 반환합니다 (비어 있으면 null 반환), 안전한 삭제 보장

peekFirst()  // 맨 앞의 요소를 반환하지만 제거하지 않음 (비어 있으면 null).

peekLast()  // 맨 뒤의 요소를 반환하지만 제거하지 않음 (비어 있으면 null).

size() // Deque 크기 반환.

isEmpty() // 비어있는지 확인

clear() // 덱 모든 요소 제거

contains()  // 해당요소 존재하는지 확인

iterator()  // Deque의 요소에 대한 Iterator를 반환합

toArray()  // 모든 요소 배열로 변환

 

 

 

스택 문제 예제)

 

1. 올바른 괄호 문제

설명

괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

입력

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

출력

첫 번째 줄에 YES, NO를 출력한다.

예시 입력 1 

(()(()))(()

예시 출력 1

NO

 

 

코드)

 

Deque를 이용해 풀기

 

Stack의 push() -> Deque의 addFirst()로 대체

Stack의 pop() -> Deque의 removeFirst()로 대체

 

Scanner sc = new Scanner(System.in);

String str = sc.nextLine();

ArrayDeque<String> dq = new ArrayDeque<>();
String answer = "YES";

for(char ch: str.toCharArray()){
    if(ch=='('){
        dq.addFirst("(");
    } else{
        if(dq.isEmpty()){
            answer = "NO";
            break;
        }
        dq.removeFirst();

    }
}

if(!dq.isEmpty()){
    answer = "NO";
}
System.out.print(answer);