데크(Deque)
양쪽에서 삽입과 삭제가 모두 가능한 자료구조
-> Deque : Doubly-ended Queue
Stack과 Queue를 합친 형태
add와 remove는 공간이 가득 차거나 뺄 데이터가 없을 때, Exception을 발생시키는 반면
-> offer나 poll은 null을 반환시킴!
입력제한 데크(Scroll)
한쪽의 입력을 제한한 데크
출력제한 데크(Shelf)
한쪽의 출력을 제한한 데크
데크 클래스 사용해보기
public class Main {
public static void main(String[] args) {
Deque deque = new ArrayDeque();
// front 부분 입력
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
System.out.println(deque); // [3,2,1]
// rear 부분 입력
deque.addLast(10);
deque.addLast(20);
deque.addLast(30);
System.out.println(deque); // [3,2,1,10,20,30]
// front 부분 출력
System.out.println(deque.removeFirst()); // 3
System.out.println(deque); // [2,1,10,20,30]
// rear 부분 출력
System.out.println(deque.removeLast()); // 30
System.out.println(deque); // [2,1,10,20];
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque); // []
System.out.println(deque.pollLast()); // null
System.out.println(deque.removeLast()); // Exception
}
}ArrayList를 통한 deque 구현
class MyDeque1{
ArrayList list;
MyDeque1(){
this.list = new ArrayList();
}
public boolean isEmpty(){
return this.list.size() == 0? true : false;
}
public void addFirst(int data){
this.list.add(0, data);
}
public void addLast(int data){
this.list.add(data);
}
public Integer removeFirst(){
if(this.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}
public Integer removeLast(){
if(this.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
int data = (int)this.list.get(this.list.size() - 1);
this.list.remove(this.list.size() - 1);
return data;
}
public void printDeque(){
System.out.println(this.list);
}
}Array를 이용한 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 addFirst(int data){
if(this.isFull()){
System.out.println("Deque is Full!");
return;
}
// 여기서 this.front란 첫번째 칸을 가리키는 것이 아니라, 빈 공간을 가리키는 것이라고 이해해야함!!!!!!
this.arr[this.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 Integer removeFirst(){
if(this.isEmpty()){
System.out.println("Deque is Empty!");
return null;
}
this.front = (this.front + 1) % this.arr.length;
return 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();
}
}연습문제
연습문제 1 : 데이터 재정렬
// 데이터 재정렬
// D0 -> D1 -> ... -> Dn-1 -> Dn 순으로 되어있는 데이터를
// D0 -> Dn -> D1 -> Dn-1 -> .. 순이 되도록 재정렬 하시오.
// 입력 예시)
// 입력 데이터 : 1 -> 2 -> 3 -> 4 -> 5
// 출력 데이터 : 1 -> 5 -> 2 -> 4 -> 3
public class Practice4 {
public static void reorderData(int[] arr){
Deque deque = new ArrayDeque();
ArrayList result = new ArrayList();
IntStream.of(arr).forEach(x -> deque.addLast(x));
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) {
int[] arr = {1,2,3,4,5};
reorderData(arr);
int[] arr2 = {1,2,3,4,5,6,7};
reorderData(arr2);
}
}문제2 : Palindrome 찾기
private static boolean checkPalindrome(String str) {
Deque deque = new ArrayDeque();
boolean isPalindrome = true;
for(String s : str.split("")){
deque.addFirst(s);
}
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;
}문제3 : 데크 변형 문제(중간에 데이터 추가하는 기능 구현)
// 기본 데크 구조에서 중간에 데이터를 추가하는 기능 구현(단 추가적인 자료구조 생성 X)
// 입력 예시
// 초기 데크 상태 (size : 5)
// -> 1, 2, 3, 4
// 중간 입력 : 10
// -> 1, 2, 10, 3, 4
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;
int 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;
}문제4 : 데크 리사이즈
// 데크 리사이즈
// 기본 데크 구조에서 데크 공간이 풀일때 데이터를 추가하는 경우
// -> 데크 공간을 2배씩 늘려주는 코드 작성
public void 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;
}
Journey for Backend Developer