여러상황에서 Deque 학습하기

Practice1 특정규칙에 따라 재정렬하는 프로그램 작성

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.stream.IntStream;

public class Practice1 {
    public static void reorderData(int[] arr) {
        Deque deque = new ArrayDeque();
        ArrayList result = new ArrayList();

        IntStream.of(arr).forEach(x -> deque.addLast(x));
        System.out.println(deque);

        while (!deque.isEmpty()) {
            result.add(deque.removeFirst());

            if (!deque.isEmpty()) {
                result.add(deque.removeLast());
            }
        }
        System.out.println("== 정렬 전 ==");
        printData(arr);
        System.out.println("== 정렬 후 ==");
        printData(result.stream().mapToInt(x -> (int)x).toArray());
    }

    public static void printData(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + " -> ");
        }
        System.out.println(arr[arr.length - 1]);
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {1, 2, 3, 4, 5};
        reorderData(arr);   // 1 -> 5 -> 2 -> 4 -> 3

        int[] arr2 = {1, 2, 3, 4, 5, 6, 7};
        reorderData(arr2);  // 1 -> 7 -> 2 -> 6 -> 3 -> 5 -> 4
    }
}

1. 데이터 재정렬 메서드

public static void reorderData(int[] arr) {
	Deque deque = new ArrayDeque();
    ArrayList result = new ArrayList();

-reorederData(int[] arr) : 배열을 재정렬하는 메서드
-Deque deque = new ArrayDeque() : Deque 자료구조를 초기화
-ArrayList result = new ArrayList() : 결과를 저장할 리스트를 초기화

2. 배열을 Deque에 추가

Intstream.of(arr).forEach(x -> deque.addLast(x));
System.out.println(deque);

-Intstream.of(arr).forEach(x -> deque.addLast(x)) : 배열의 모든 요소를 deque의 뒤쪽에 추가
-현재 deque의 상태를 출력

3. 재정렬 과정

while (!deque.isEmpty()) {
	result.add(deque.removeFirst());
    
    if (!deque.isEmpty()) {
    	result.add.(deque.removeLast());
    }
}

-while (!deque.isEmpty()) : deque가 비어 있지 않은 동안 반복
-result.add(deque.removeFirst()) : deque의 첫번째 요소를 제거하여 결과 리스트에 추가
-if (!deque.isEmpty()) { result.add(deque.removeLast()); } : deque가 비어있지 않으면 deque의 마지막 요소를 제거하여 결과 리스트에 추가

4. 결과 출력

printdata(arr);
printData(result.stream().mapToInt(x -> (int)x).toArray());

-재정렬 전과 후의 배열을 출력
-printData(arr) : 원래 배열을 출력
-printData(result.stream().mapToInt(x -> (int)x).toArray()) : 겨로가 리스트를 배열로 변환하여 출력

5. 배열 출력 메서드

public static void printData(int[] arr) {
	for (int i = 0; i < arr.length - 1; i++) {
    	System.out.print(arr[i] + " -> ");
    }
    System.out.println(arr.length - 1));
}

-printData(int[] arr) : 배열을 출력하는 메서드. 각 요소를 -> 로 구분하여 출력

practice2 주어진 문자열이 회문(palindrome) 인지 확인하는 프로그램

** 회문(palindrome) 이란?
앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미 (거꾸로 읽어도 기러기)

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

public class Practice2 {
    public static boolean checkPalindrome(String str) {
        Deque deque = new ArrayDeque();
        boolean isFront = true;
        boolean isPalindrome = true;

        for (String string : str.split("")) {
            deque.addFirst(string);
        }
        while (!deque.isEmpty()) {
            String s1 = (String)deque.pollFirst();
            String s2 = (String)deque.pollLast();

            if (s1 != null && s2 != null && !s1.equals(s2)) {
                isPalindrome = false;
                break;
            }
        }
        return isPalindrome;
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(checkPalindrome("a"));       // true
        System.out.println(checkPalindrome("aba"));     // true
        System.out.println(checkPalindrome("abba"));    // true
        System.out.println(checkPalindrome("abab"));    // false
        System.out.println(checkPalindrome("abcba"));   // true
        System.out.println(checkPalindrome("abccba"));  // true
        System.out.println(checkPalindrome("madam"));  // true
    }
}

1. palindrome 확인 메서드

public static boolean checkPalindrome(String str) {
	Deque deque = new ArrayDeque();
    boolean isPalindrome = true;
    
    for (String string : str.split("")) {
    	deque.addFirst(string);
    }

-checkPalindrome(String str) : 문자열이 palindrome인지 확인하는 메서드
-Deque deque = new ArrayDeque() : deque 자료구조를 초기화
-boolean isPalindrome = true : palindrome 여부를 저장할 변수를 초기화
-for (String string : str.split("")) { deque.addFirst(string); } : 문자열을 한글자씩 deque에 추가. 문자열의 각 문자를 split("") 을 통해 개별 문자로 나누고, deque의 앞쪽에 추가

2. palindrome 여부 확인

while (!deque.isEmpty()) {
	String s1 = (String)deque.pollFirst();
    Stirng s2 = (String)deque.pollLast();
    
    if (s1 != null && s2 != null && !s1.equals(s2)) {
    	isPalindrome = false;
    	break;
    }
}

-while (!deque.isEmpty()) : deque가 비어있찌 않은동안 반복
-String s1 = (String)deque.pollFirst() : deque의 첫번째 요소를 꺼내 s1에 저장
-String s2 = (String)deque.pollLast() : deque의 마지막 요소를 꺼내 s2에 저장
-if (s1 != null && s2 != null && !s1.equals(s2)) { isPalindrome = false; break; } : s1과 s2가 null이 아니고, 서로 다르다면 palindrome이 아니므로 isPalindrome을 false로 바꾸고 반복문을 종료

3. 결과 반환

return isPalindrome;

-palindrome 여부를 반환

Practice3 특정위치에 데이터를 추가하는 기능

https://velog.io/@yuno1012/Deque-학습하기
이전 글에서 배열을 사용하여 Deque 구현하기 에서 추가한 코드

class MyDeque {
    int[] arr;
    int front = 0;
    int rear = 0;

    MyDeque(int size) {
        this.arr = new int[size + 1];
    }

    public boolean isEmpty() {
        return this.rear == this.front;
    }

    public boolean isFull() {
        return (this.rear + 1)  % this.arr.length == this.front;
    }

    public void addFirst(int data) {
        if (this.isFull()) {
            System.out.println("Deque is full!");
            return;
        }

        this.arr[front] = data;
        this.front = (this.front - 1 + this.arr.length) % this.arr.length;
    }

    public void addLast(int data) {
        if (this.isFull()) {
            System.out.println("Deque is full!");
            return;
        }

        this.rear = (this.rear + 1) % this.arr.length;
        this.arr[this.rear] = data;
    }

    public void addMiddle(int data) {
        if (this.isFull()) {
            System.out.println("Deque is full!");
            return;
        }
        int elements = this.rear - this.front;
        if (elements < 0) {
            elements = this.arr.length + elements;
        }
        int mid = (this.rear - elements / 2 + this.arr.length) % this.arr.length + 1;

        int satar = (this.rear + 1) % this.arr.length;
        int end = (this.rear - elements / 2 + this.arr.length) % this.arr.length;
        for (int i = satar; i != end; i = (i - 1 + this.arr.length) % this.arr.length) {
            this.arr[i] = this.arr[(i - 1 + this.arr.length) % this.arr.length];
        }
        this.arr[mid] = data;
        this.rear = (this.rear + 1) % this.arr.length;
    }

    public Integer removeFirst() {
        if (this.isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        this.front = (this.front + 1) % this.arr.length;
        return this.arr[this.front];
    }

    public Integer removeLast() {
        if (this.isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        int data = this.arr[this.rear];
        this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
        return data;
    }

    public void printDeque() {
        int start = (this.front + 1) % this.arr.length;
        int end = (this.rear + 1) % this.arr.length;

        for (int i = start; i != end; i = (i + 1) % this.arr.length) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class Practice3 {
    public static void main(String[] args) {
        // Test code
        MyDeque myDeque1 = new MyDeque(5);
        myDeque1.addLast(1);
        myDeque1.addLast(2);
        myDeque1.addLast(3);
        myDeque1.addLast(4);
        myDeque1.printDeque();

        myDeque1.addMiddle(10);
        myDeque1.printDeque();

        MyDeque myDeque2 = new MyDeque(5);
        myDeque2.addLast(10);
        myDeque2.addLast(10);
        myDeque2.addLast(10);
        myDeque2.addLast(10);
        myDeque2.addLast(10);
        myDeque2.removeFirst();
        myDeque2.removeFirst();
        myDeque2.removeFirst();
        myDeque2.removeFirst();
        myDeque2.addLast(11);
        myDeque2.addLast(12);
        myDeque2.addLast(13);
        myDeque2.printDeque();

        myDeque2.addMiddle(100);
        myDeque2.printDeque();
    }
}

1. 중간에 데이터 넣기

public void addMiddle(int data) {
	if (this.isFull()) {
    	System.out.println("Deque is full!");
        return;
    }
    int elements = this.rear - this.front;
    if (elements < 0) {
    	elements = this.arr.length + elements;
    }
    int mid = (this.rear - elements / 2 + this.arr.length) % this.arr.length + 1;
    int start = (this.rear + 1) % this.arr.length;
    itn end = (this.rear - elements / 2 + this.arr.length) % this.arr.length;
    for (int i = start; i != end i = (i + 1 + this.arr.length) % this.arr.length) {
    this.arr[i] = this.arr[(i - 1 + this.arr.length) % this.arr.length];
	}
	this.arr[mid] = data;
	this.rear = (this.rear + 1) % this.arr.length;
}

-addMiddle(int data) : deque의 중간에 데이터를 추가. 배열이 가득 차면 데이터를 추가하지 않음
-elements : deque에 있는 요소의 갯수를 계산
-mid : 중간 위치를 계산
-for문 : 중간 위치에서부터 한 칸씩 뒤로 이동하여 자리를 만듬
-this.arr[mid] = data : 중간 위치에 데이터를 추가

Practice4 Deque가 꽉 찼을때 배열의 크기를 증가시키는 프로그램

https://velog.io/@yuno1012/Deque-학습하기
이전 글에서 배열을 사용하여 Deque 구현하기 에서 추가한 코드

class MyDeque2 {
    int[] arr;
    int front = 0;
    int rear = 0;

    MyDeque2(int size) {
        this.arr = new int[size + 1];
    }

    public boolean isEmpty() {
        return this.rear == this.front;
    }

    public boolean isFull() {
        return (this.rear + 1)  % this.arr.length == this.front;
    }

    public void increaseSize() {
        System.out.println("MuDeque2.increaseSize");
        int[] arrTmp = this.arr.clone();
        this.arr = new int[this.arr.length * 2];

        int start = (this.front + 1) % arrTmp.length;
        int end = (this.rear + 1) % arrTmp.length;

        int idx = 1;
        for (int i = start; i != end; i = (i + 1) % arrTmp.length) {
            this.arr[idx++] = arrTmp[i];
        }
        this.front = 0;
        this.rear = idx - 1;

    }

    public void addFirst(int data) {
        if (this.isFull()) {
            increaseSize();
        }

        this.arr[front] = data;
        this.front = (this.front - 1 + this.arr.length) % this.arr.length;
    }

    public void addLast(int data) {
        if (this.isFull()) {
            increaseSize();
        }

        this.rear = (this.rear + 1) % this.arr.length;
        this.arr[this.rear] = data;
    }

    public Integer removeFirst() {
        if (this.isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        this.front = (this.front + 1) % this.arr.length;
        return this.arr[this.front];
    }

    public Integer removeLast() {
        if (this.isEmpty()) {
            System.out.println("Deque is empty!");
            return null;
        }

        int data = this.arr[this.rear];
        this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
        return data;
    }

    public void printDeque() {
        int start = (this.front + 1) % this.arr.length;
        int end = (this.rear + 1) % this.arr.length;

        for (int i = start; i != end; i = (i + 1) % this.arr.length) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class Practice4 {
    public static void main(String[] args) {
        // Test code
        MyDeque2 myDeque = new MyDeque2(5);

        myDeque.addLast(1);
        myDeque.addLast(2);
        myDeque.addLast(3);
        myDeque.addLast(4);
        myDeque.addLast(5);
        myDeque.printDeque();

        myDeque.addLast(6);
        myDeque.addLast(7);
        myDeque.addLast(8);
        myDeque.addLast(9);
        myDeque.addLast(10);
        myDeque.printDeque();

        myDeque.removeLast();
        myDeque.removeLast();
        myDeque.addFirst(100);
        myDeque.addFirst(200);
        myDeque.printDeque();

        myDeque.addFirst(300);
        myDeque.addFirst(400);
        myDeque.addFirst(500);
        myDeque.printDeque();
    }
}

1. 배열 크기 증가 메서드

public void increaseSize() {
	System.out.println("MyDeque2.increaseSize");
    int[] arrTmp = this.arr.clone();
    this.arr = new int[this.arr.length * 2];
    
    int start = (this.front + 1) % arrTmp.length;
    int end = (this.rear + 1) % arrTmp.length;
    
    int idx = 1;
    for (int i = start; i != end; i = (i + 1) % arrTmp.length) {
    	this.arr[idx++] = arrTmp[i];
    }
    this.front = 0;
    this.rear = idx - 1;
}

-increaseSize() : 배열이 꽉 찼을때 배열의 크기를 두배로 늘림
-arrTmp = this.arr.clone() : 현재 배열을 복사
-this.arr = new int [this.arr.length * 2] : 새로운 배열을 두배 크기로 생성
-for문 : 복사한 배열의 데이터를 새로운 배열에 재배치
-this.front = 0; this.rear = idx - 1; : 새로운 배열에서 앞과 뒤 포인터를 재설정