선형자료구조 - 데크/덱(Deque)

Deque.

Double-ended queue
양쪽에서 삽입과 삭제가 모두 가능한 자료구조
Java에서 Deque는 Java.util 패키지에 있는 Queue 인터페스의 하위 유형으로
이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있음
양 쪽 끝에 요소를 삽입하고 삭제할 수 있는 데이터구조를 지원
FIFO, LIFO 모두 사용 가능함(스택과 큐를 합친 것)
Deque는 Palindrome Checker , Song Playlist 등에서 사용

 

Deque 주요 메서드.

    

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        Deque deque = new ArrayDeque<>(); // 선언

        // 1. 데이터 추가
        // add() : deque 끝에 요소를 추가, 추가할 수 없으면 throw 발생
        deque.add(1);
        deque.add(2);
        System.out.println(deque); // [1, 2]

        // addFirst(), push() : 시작 부분에 요소를 추가, 데이터를 추가할 수 없으면 throw
        deque.addFirst(10);
        deque.push(20);
        System.out.println(deque); // [20, 10, 1, 2]

        // addLast() : 끝에 요소를 추가, 추가할 수 없으면 throw 발생
        deque.addLast(100);
        deque.addLast(200);
        deque.addLast(300);
        System.out.println(deque); // [20, 10, 1, 2, 100, 200, 300]

        deque.clear();

        // offer() : 끝에 요소 추가, 추가할 수 없으면 false 반환
        deque.offer(10);
        deque.offer(20);
        deque.offer(30);
        System.out.println(deque); // [10, 20, 30]

        // offerFirst() : 시작에 요소 추가, 추가할 수 없다면 false 반환
        deque.offerFirst(1);
        deque.offerFirst(2);
        deque.offerFirst(3);
        System.out.println(deque); // [3, 2, 1, 10, 20, 30]

        // offerLast() : 끝에 요소 추가, 추가할 수 없다면 false 반환
        deque.offerLast(1);
        deque.offerLast(2);
        deque.offerLast(3);
        System.out.println(deque); // [3, 2, 1, 10, 20, 30, 1, 2, 3]


        // 2. 삭제
        // pop(), remove(), removeFirst() : 첫번째 요소를 제거하고 반환, 비어있다면 throw 발생
        System.out.println(deque.pop()); // 3
        System.out.println(deque.remove()); // 2
        System.out.println(deque.removeFirst()); // 1
        System.out.println(deque); // [10, 20, 30, 1, 2, 3]

        // poll(), pollFirst() : 첫번째 요소를 제거하고 반환, 비었다면 null 반환
        System.out.println(deque.poll()); // 10
        System.out.println(deque); // [20, 30, 1, 2, 3]

        // removeLast() : 마지막 요소를 제거하고 반환, 비어있다면 throw 발생
        System.out.println(deque.removeLast()); // 3

        // pollLast() : 마지막 요소를 제거하고 반환, 비어있다면 null 발생
        System.out.println(deque.pollLast()); // 2
        System.out.println(deque); // [20, 30, 1]

        // removeFirstOccurrence() : 첫 번째로 나타나는 특정 요소를 제거, 제거되지 않으면 false
        System.out.println(deque.removeFirstOccurrence(1));
        System.out.println(deque); // [20, 30]
        System.out.println(deque.removeFirstOccurrence(100)); // false

        // removeLastOccurrence() : 마지막으로 나타나는 특정 요소를 제거, 제거되지 않음 false
        deque.addLast(20);
        deque.addLast(10);
        deque.addLast(30);
        System.out.println(deque); // [20, 30, 20, 10, 30]
        deque.removeLastOccurrence(20);
        System.out.println(deque); // [20, 30, 10, 30]

        // 3. 데이터 가져오기
        // peak(), peekFirst() : 첫번째 요소를 제거하지 않고 반환, 비었다면 null
        // getFirst() : 첫번째 요소를 제거하지 않고 반환, 비었다면 throw
        // peakLast() : 마지막 요소를 제거하지 않고 반환, 비었다면 null
        // getLast() : 마지막 요소를 제거하지 않고 반환, 비었다면 throw

        // 4. iterator() : 데크의 앞쪽부터 순차적으로 실행되는 이터레이터
        Iterator iterator = deque.iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            System.out.print(element + " "); // 20 30 10 30
        }

    }
}


    
  

 

Deque 관련 코딩테스트 문제.

프로그래머스 - 가장 긴 팰린드롬
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

    

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int solution(String s) {
        int answer = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = n; j > i; j--) {
                if (isPalindrome(s, i, j)) {
                    answer = Math.max(answer, j - i);
                    break;
                }
            }
        }

        return answer;
    }
    
    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end - 1)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}


    
  

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12904?language=java