선형자료구조 - 데크

데크는 선형자료구조 중에서도 양방향에서 삽입 삭제가 가능한 구조를 가지는 자료구조이다. (stack + Queue)

이러한 데크는 사용시 일부기능을 제한하여 용도에 맞게 변형 가능하다. 

 

또한 데크는 삽입 출력및 삭제를 하는 메소드가 각각 두 개씩 있다. 

1. add 와 remove : 해당 메소드는 예외처리시 많이 사용한다. (왜냐하면 null등을 반환하지 않고 예외처리 발생을 하기 때문이다.)

2. offer 와 poll : null 이나 false를 반환해준다. 

 

데크의 종류 2가지 

1. 입력제한 데크 (Scroll) : 한쪽의 입력을 제한한 데크

2. 출력제한 데크 (Shelf) : rear 나 front 쪽 중 하나의 출력을 제한한 데크

 

java에서의 데크 사용

Deque deque = new ArrayDeque();

 

deque.addFirst(); // front 로 add

deque.addLast(); // rear로 add

deque.removeFirst(); // Front로 remove

deque.removeLase(); // rear로 remove

// add 와 remove는 꽉차있거나 비어있어 삽입 삭제가 불가능한 경우 null이나 false가 아닌 예외처리를 발생한다. 

 

deque.offerFirst(); // front로 값 추가 -> full시에 false 반환 가능 

deque.pollLase(); // rear로 값 삭제 -> empty시에 Null 반환 가능

 

java에서 import하지 않고 데크 구현해보기

1. ArrayList를 이용한 데크 구현

 생성자에서 ArrayList 객체 생성 후 

 단순히 isEmpty, addFirst, addLast, removeFirst, removeLast, printDeque 메소드 구현하기

 * addFirst 메소드 구현시 index 0에 삽입

 * get할때 (size - 1) 번 index꺼 꺼내오기 

 

2. 배열을 이용한 데크 구현

  isEmpty : rear == front 일때

  isFull : (rear + 1) % length == front 일때

  addFirst : isFull이 아닐때 data 넣고,  front = (front -1 + arr.length) % arr.length;

  addLast : isFull이 아닐때, data넣고,  rear = (rear + 1 ) % arr.length;

  removeFirst : isEmpty가 아닐때, front = (front + 1) % arr.length;  return arr[front];

  removeLast : isEmpty가 아닐때, data = arr[rear]; 후 !!!  rear = (rear - 1 + arr.length) % arr.length; return data;

 

데크를 이용한 연습문제

문제01) 0 -> 1-> ... -> n-1 -> n의 형태를 0 -> n -> 1 -> n-1 -> ... 형태로 변환하기

code)

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.removeLat(); 

  }

}

 

문제01) 펠린드롬 (palindrome) 찾기 (앞으로 읽나 뒤로 읽나 똑같이 읽히는 문자를 말한다.)

code)

Deque duque = new ArrayDeque();

boolean isFront = true;

boolean isPalindrome = true;

 

for(String s : str.split(" ")){

  deque.addFirst(s);

}

while( !deque.isEmpty()){

  String s1 = deque.pollFirst();

  String s2 = deque.pollLast();

  // remove 대신 poll을 이용하면 null 반환 가능해짐

  //글자수가 홀수개인 경우를 위해 s2가 null이여도 예외처리가 발생되지 않게 해주어야한다!

  if( s1 != null && s2 != null && !s1.equals(s2)){

      isPalindrome = false;

      break;

   }

}

 

return isPalindrome;

 

 

문제03) 배열로 데크구현 & middle data 넣기

 

문제04) 배열공간이 가득찼을때 2배로 늘린 공간으로 데크 옮기기