글 작성자: ST_
728x90





 

자료구조 관련 목록 링크 펼치기 

 

 

 








  • Deque (using Array)



 

 

만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글과 큐 인터페이스 (Queue Interface)을 먼저 보고 오셨으면 한다. (필자가 앞서 언급했지만, Queue 인터페이스를 만들어 두고 이를 implements 하여 구체적으로 구현하고자 한다고 했다. 그러니 꼭 Queue 인터페이스 글도 읽어오시길 바란다.)

 

또한 추가로 단순히 int형식에 한정한 구현이 아닌 제네릭을 사용하여 구현을 할 것이라 최소한의 제네릭에 대한 이해를 필요로 하니 필요하다면 다음 글도 읽어오는 것을 추천드린다.

제네릭에 대한 이해

 

 

 

그리고 '반드시' Array Quque 구현 글을 읽고 오시길 바란다. 

오늘 구현할 배열을 사용하는 큐는 기본적으로 Object[] 배열과 자료구조 기본 개념은 알고있어야 한다. 

 

기본적으로 배열을 사용하여 구현되는 자료구조 클래스는 내부에서 최상위 타입 배열인 Object[] 배열을 사용하여 데이터들을 관리하고 있다. 그러면 덱 구조를 한 번 보도록하자.

 

 

그럼 본격적으로 Deque(덱)에 대해 알아보고 구현하고자 한다.

왜 Deque(덱)일까? Deque는 Double-ended queue의 줄임말이다.

여기서 오해가 있을 수도 있는데 카드게임에서 말하는 덱은 Deck이다. 다만 발음은 같다. 여튼 Queue(큐)를 구현해봤으면 알겠지만, 큐는 단방향 자료구조다. 단방향 연결리스트(Singly LinkedList)와 유사한 메커니즘이다.

반대로 Deque는 양방향 연결리스트(Doubly LinkedList)와 유사한 메커니즘이다. 앞서 말한 double-ended, 두 개의 종료 지점이 있다는 것. 한 마디로 단 방향으로 삽입 삭제가 이루어 진 것에서 양 쪽 방향으로 삽입 삭제가 이루어 질 수 있도록 구현 한 것이 Deque다.

 

양방향 큐. 즉 덱의 장점이라 하면 스택처럼 사용할 수도 있고 큐 처럼 사용할 수도 있는 자료구조다.

 

아무래도 Deque의 경우 양 방향이다보니 메소드들이 헷갈릴 수 있는데 다음 큐와 비교한 그림을 보면서 덱의 구조와 기본적인 메소드의 매칭을 잘 알아두도록 하자. 그리고 다시 한 번 말하지만 필자가 포스팅한 ArrayQueue(배열 큐) 글을 보고 오시길 바란다.

 

 

 

 

보다시피 Deque는 삽입, 삭제가 총 12개가 있다.

 

offer 계열과 poll 계열의 경우 삽입과 삭제 과정에서 저장공간이 넘치거나 삭제 할 원소가 없을 때 특정 값(null, false 등..)을 반환하지만, add 계열과 remove 계열의 경우 예외를 던진다.

 

또한 offer(add)은 offerLast(addLast)와 같고, poll(remove)은 pollFirst(removeFirst)와 같다.

 

정리하자면 우리가 삽입 삭제에서 구현해야 할 것은 크게 4가지다. (add계열은 이 번 구현에서 최대 용적을 제한하지 않을 것이기 때문에 빼고 offer 계열만 구현한다.)

 

offerLast, offerFirst, pollFirst, pollLast 만 정확하게 구현하면 된다.

 

그 외에 peek(element) 의 경우도 peek(element)은 peekFirst와 같으며, peekLast은 따로 존재한다. 아래 표를 참고하시면 된다.

 

 

 

 

그리고 기본적으로 ArrayQueue에 몇 가지 메소드를 추가하는 것이기 때문에 ArrayQueue 포스팅에서의 메소드 구현과 내용이 같은 부분도 존재한다는 것을 미리 일러둔다. (혹시나 무성의해 보일까봐..)

 

 

그리고 배열로 덱을 구현하는 경우 Queue와 마찬가지로 원형 형태로 구현 할 것이다.

 

 







  • ArrayDeque 구현



 

- 사전 준비

 

[Queue Interface 소스]

더보기

 

[Queue.java]

package Interface_form;

/**
 * 
 * 자바 Queue Interface입니다. <br>
 * Queue는 ArrayQueue, LinkedListQueue,
 * ArrayDeque, LinkedListDeque, PriorityQueue 에 의해 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this Que
 *
 * @version 1.0
 * 
 */


public interface Queue<E> {
	
	/**
	 * 큐의 가장 마지막에 요소를 추가합니다.
	 * 
	 * @param e 큐에 추가할 요소 
	 * @return 큐에 요소가 정상적으로 추가되었을 경우 true를 반환 
	 */
	boolean offer(E e);
	
	/**
	 * 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환합니다.
	 * 
	 * @return 큐의 삭제 된 요소 반환 
	 */
	E poll();
	
	/**
	 * 큐의 첫 번째 요소를 반환합니다.
	 * 
	 * @return 큐의 첫 번째 요소 반환 
	 */
	E peek();
	
	
}

 

 

[구현 바로가기]

 

<필수 목록>

◦ 클래스 및 생성자 구성

◦ resize 메소드 구현

◦ offer 계열 메소드 구현

◦ poll 계열 메소드 구현

◦ peek 계열 메소드 구현

◦ size, isEmpty, contains ,clear 메소드 구현

 

<부가 목록>

◦ toArray, clone, sort 구현

 

◦ 전체 코드

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[Deque 클래스 및 생성자 구성하기]

 

 

이 번에 구현 할 덱은 '배열'을 이용하므로, ArrayDeque 라는 이름으로 생성한다. 그리고 앞선 Queue Interface 포스팅에서 작성했던 Queue 인터페이스를 implements 해준다. (필자의 경우 인터페이스는 Interface_form 이라는 패키지에 생성해두었다.)

implements 를 하면 class 옆에 경고표시가 뜰 텐데 인터페이스에 있는 메소드들을 구현하라는 것이다. 어차피 모두 구현해나갈 것이기 때문에 일단은 무시한다. 

 

[ArrayDeque.java]

import Interface_form.Queue;

public class ArrayDeque<E> implements Queue<E>{

	private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기

	private Object[] array; // 요소를 담을 배열
	private int size; // 요소 개수

	private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
	private int rear; // 마지막 요소의 인덱스를 가리키는 변수

	// 생성자1 (초기 용적 할당을 안할 경우)
	public ArrayDeque() {
		this.array = new Object[DEFAULT_CAPACITY];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}

	// 생성자2 (초기 용적 할당을 할 경우)
	public ArrayDeque(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}
}

 

 

변수부터 먼저 차례대로 설명해주도록 하겠다.

 

DEFAULT_CAPACITY : 배열이 생성 될 때의 최초 할당 크기(용적)이자 최소 할당 용적 변수로 기본값은 64으로 설정해두었다. (capacity가 용적이라는 의미다)

array : 요소들을 담을 배열

size : 배열에 담긴 요소(원소)의 개수 변수 (용적 크기가 아니다. 절대 헷갈리지 말자)

front : 시작 위치(index)를 가리키는 변수 (빈 공간이다.) 

rear : 마지막 요소의 위치(index)를 가리키는 변수

 

참고로 front와 rear은 '큐(Queue)' 관점을 기준으로 쓴다.

그리고 DEFAULT_CAPACITY 변수는 상수로 쓸 것이기 때문에 static final 키워드를 붙인다.

 

 

그리고 보면 생성자가 2개를 두었다.

생성자 1의 경우 사용자가 공간 할당을 안하고 객체만 생성할 때, 즉 다음과 같은 상태일 때이다.

ArrayDeque<Integer> q = new ArrayDeque<>();

 

 

 

 

반면에 사용자가 데이터의 개수를 예측할 수 있어서 미리 공간 할당을 해놓고 싶을 경우, 즉 다음과 같이 생성할 경우 

ArrayDeque<Integer> q = new ArrayDeque<>(100);

 

array의 공간 할당을 입력 된 수 만큼 (예제에서는 array = new Object[100]) 배열을 만든다. 그리고 마찬가지로 size, front, rear 들을 0으로 초기화 시켜놓는다.

 

(size는 요소(원소)의 개수를 의미하는 것이다. 공간을 할당해놓는 것하고는 다른 개념이다.)

 

 

 

 

 

 

 

[동적할당을 위한 resize 메소드 구현]

 

 

앞서 필자가 말했던 것 처럼 우리는 들어오는 데이터에 개수에 따라 '최적화'된 용적을 갖을 필요가 있다. 만약 데이터는 적은데 용적이 크면 메모리가 낭비되고, 반대로 용적은 적은데 데이터가 많으면 넘치는 데이터들은 보관할 수 없게 되는 상황을 마주칠 수 있다.

 

그렇기 때문에 size(요소의 개수)가 용적(capacity)에 얼마만큼 차있는지를 확인하고, 적절한 크기에 맞게 배열의 용적을 변경해야 한다. 또한 용적은 외부에서 마음대로 접근하면 데이터의 손상을 야기할 수 있기 때문에 private로 접근을 제한해주도록 하자.

 

용적이 변경되는 경우는 크게 용적을 증가시켜야 하는 경우와 용적을 줄여야 하는 경우. 이 두가지로 나뉜다. 그러나 따로 용적을 증가해야 하는 경우와 줄여야 하는 경우를 굳이 나눌 필요 없다. 밑에서 그림을 보면 알겠지만, 먼저 코드부터 보고 가자. 

 

 

private void resize(int newCapacity) {

	int arrayCapacity = array.length; // 현재 용적 크기

	Object[] newArray = new Object[newCapacity]; // 용적을 변경한 배열

	/*
	 * i = new array index 
	 * j = original array 
	 * index 요소 개수(size)만큼 새 배열에 값 복사
	 */
	for (int i = 1, j = front + 1; i <= size; i++, j++) {
		newArray[i] = array[j % arrayCapacity];
	}

	this.array = null;
	this.array = newArray; // 새 배열을 기존 array의 배열로 덮어씌움

	front = 0;
	rear = size;

}

 

 

 

 

 

용적을 증가하는 경우 : ((rear + 1) % arrayCapacity == front)

 

 

 

 

 

용적이 가득 찰 경우다. 이 의미는 rear의 다음 인덱스(rear +1) 이 front 랑 같다는 말과 동일하다. 다만 (rear+1)에 % arrayCapacity 즉, 기존 배열의 길이를 나누는 이유는 front 가 rear보다 작을경우를 고려해야 하기 때문이다.

예로들어 rear가 7이고, front가 0이라면 7+1 = 8이므로, 0과 같지 않다. 이러한 이유로 길이(예시에서는 8)로 나눠준 나머지 (7+1)%8 = 0 을 해야 정확한 조건 때 용적을 증가 시킬 수 있다.

 

 

 

 

 

 

 

용적을 줄여야 하는 경우 : (size < (arrayCapacity / 4))

 

 

 

 

 

데이터가 1/4 미만으로 떨어질 경우에는 필요없는 공간이 너무 많아지게 되므로 절반정도로만 줄인다.

 

코드를 보면 알겠지만 새로운 용적의 배열에 값을 복사하는 과정 자체는 똑같기 때문에 따로 두 경우의 조건문은 달지 않고 파라미터(newCapacity)로 받은 새 용적을 이용하여 용적의 사이즈를 변경할 것이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[offer 계열 메소드 구현]

 

 

이제 본격적으로 Deque에 데이터를 추가할 수 있도록 해보자. 

 

Deque의 삽입은 크게 두 가지로 나뉜다.

기본 메소드 offer() 및 offerLast()는 후방(맨 뒤)에 데이터를 추가한다. 리스트로 치면 add(E value) 및 addLast(E value)와 같은 역할이다.  두 번째는 전방(맨 앞)에 데이터를 추가하는 경우다. 이는 offerFirst()가 담당하며 리스트로 치면 addFirst()와 같은 역할이다.

 

다만 두 메소드 모두 고려해야 할 부분이라면 배열이 꽉 차있을 경우다.

 

 

- 가장 마지막 부분에 추가 : offer(E item), offerLast(E item)

- 가장 앞의 부분에 추가 : offerFirst(E item)

 

 

그럼 하나씩 구현해보자.

 

 

1. 기본 삽입 : offer(E item) , offerLast(E item)

 

가장 기본적인 삽입 방법이다. 만약 Array Queue를 구현해보았다면 원리는 다를게 없기 때문에 쉬울 것이다. 일단 그림을 먼저 보고가자.

 

 

 

이를 토대로 구현하는 것은 어렵지 않다. offer() 및 offerLast() 메소드를 구현하자면 이렇다. (참고로 offerLast()를 베이스로 구현을 한 뒤, offer() 메소드에서 offerLast() 을 호출하는 방식으로 구현한다.)

 

@Override
public boolean offer(E item) {
	return offerLast(item);
}
	
public boolean offerLast(E item) {
		
	// 용적이 가득 찼을 경우 
	if((rear + 1) % array.length == front) {
		resize(array.length * 2);	// 용적을 두 배 늘려준다. 
	}
		
	rear = (rear + 1) % array.length;	// rear을 rear의 다음 위치로 갱신 
		
	array[rear] = item;
	size++;	// 사이즈 1 증가 
		
	return true;
}

 

 

또한 필자가 '동적할당'을 강조했듯 용적이 가득찼다면 array의 용적을 늘려주어야 한다. 그렇기 때문에 앞서 구현한 resize() 메소드를 호출하여 용적을 두 배 늘려준 뒤 데이터를 추가해주도록 하자.

 

 

 

 

 

2. 전방 삽입 : offerFirst(E item)

 

덱의 앞 부분에 삽입하는 메소드다. 조금만 생각해본다면 offerLast와 크게 다를 것은 없으니 한 번 그림을 보면 쉽게 구현 할 수 있을 것이다.

 

offerLast는 rear(후방) 변수를 이용하였다면, 이 번에는 반대로 front(전방) 변수를 이용하여 반대로만 구현 하면 된다.

 

이 때 주의해야 할 점이 있다. offerLast의 경우 rear는 항상 0 이상의 수이기 때문에 rear 값을 새로 갱신하는 경우에 1 증가 시킨 뒤 용적 크기로 나머지값을 구했다. 즉, rear = (rear + 1) % array.length 이었다.

 

하지만 이 번의 경우 front를 오히려 감소시켜야 한다. 이게 왜 문제냐면 front = 0일 때 앞부분에 원소를 추가하면 front 값을 새로운 값으로 갱신시키게 된다. 이 때 front 에 1을 빼버리면 -1이 된다.

만약 front = (front - 1) % array.length 수식에 front = 0 이라면 어떻게 될까? 예로들어 용적(array.length)이 8이라고 해보자.

수식에 대입해보면 이럴 것이다.

(0 - 1) % 8

= -1 % 8

= ???

-1 을 8로 나눈 나머지 값은 얼마일까? 자바에서는 다음과 같은 값을 내보내게 된다.

 

-1 % 8 = -1

즉, 음수가 나와버리게 되어 배열 인덱스를 잘못참조해버리는 일이 발생하게 된다. 그러면 어떻게 해결하냐?

 

매우 간단하다. 나누려는 값만큼 먼저 더해주면 된다. front - 1 에서 용적의 크기를 더한 뒤 그 수를 용적의 크기로 나눈 나머지를 구해주면 되는 것이다.

쉽게 생각해서 다음과 같은 수식을 써야한다.

 

front = (front - 1 + array.length) % array.length

 

 

public boolean offerFirst(E item) {
	// 용적이 가득 찼을 경우
	if((front - 1 + array.length) % array.length == rear) {
		resize(array.length * 2);	// 용적을 두 배 늘려준다. 
	}
		
	array[front] = item;	// front위치는 빈 공간이기 때문에 추가 해준 뒤 front 값을 갱신한다.
	front = (front - 1 + array.length) % array.length;
	size++;	// 사이즈 1 증가
		
	return true;
}

 

 

 

그림을 보면 알겠지만, front 위치 자체가 빈 공간이기 때문에 먼저 채운 뒤 front 값을 갱신해주어야 한다. 이 부분만 조심해주면 된다.

 

 

 

 

 

 

 

[offer 메소드 묶어보기]

 

더보기 
// 후방 삽입
@Override
public boolean offer(E item) {
	return offerLast(item);
}
	
public boolean offerLast(E item) {
		
	if((rear + 1) % array.length == front) {
		resize(array.length * 2);
	}
		
	rear = (rear + 1) % array.length;	
	array[rear] = item;
	size++;	
		
	return true;
}
	

// 전방 삽입 
public boolean offerFirst(E item) {

	if((front - 1 + array.length) % array.length == rear) {
		resize(array.length * 2);
	}
		
	array[front] = item;
	front = (front - 1 + array.length) % array.length;
	size++;
		
	return true;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[poll 계열 메소드 구현]

 

 

 

 

poll 메소드 또한 앞부분에서 offer와 마찬가지로 크게 두 가지 경우로 나뉜다.

poll 및 pollFirst 메소드는 맨 앞의 요소를 삭제하는 메소드로 리스트에서의 removeFirst()와 같은 역할이며 front + 1 위치에 있는 요소를 삭제하면 된다.

반대로 pollLast 메소드는 맨 뒤의 요소를 삭제하는 메소드로 리스트에서의 removeLast()와 같은 역할이며 rear 위치에 있는 요소를 삭제하면 된다.

 

다만 두 가지 모두 중요한 점은 '삭제할 요소가 없는 경우' 다.

 

자바의 Deque에 관한 API 문서를 보면 알겠지만 삭제하려는 요소가 없을 경우 poll 계열의 경우 예외가 발생하는 것이 아닌 null을 반환한다. 하지만, remove 계열은 null이 아닌 NoSuchElementException 예외를 던진다.

 

다시 한 번 표를 보면 이렇다.

 

 

 

참고 문서 링크 : docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html

 

(add()의 경우 앞서 언급했듯 만약 용적이 제한되어있는데 용적보다 더 많은 요소를 추가 할 경우 예외를 던지는데, 지금 구현하는 것에서는 최대 제한을 걸지 않아 넘어갔다.)

 

 

 

 

1. 전방 삭제 : poll(), pollFrist()

 

일단 poll() 및 pollFirst() 메소드를 구현하고 이를 remove() 메소드에 응용하여 적용할 것이다.

 

 

poll의 구조 또한 매우 쉬우니 그림을 다시 한 번 보고 구현해보도록 하자.

 

 

 

이번 메소드 또한 pollFirst()를 먼저 구현한 뒤 poll() 메소드 안에서 pollFirst()를 호출하는 방식으로 할 것이다.

또한 remove및 removeFirst()의 경우는 예외를 처리해주어야 하기 때문에 pollFirst()의 값을 받아왔는데 해당 값이 null이면 예외를 던져주는 식으로 만들어 주면 된다.

 

@Override
public E poll() {		
	return pollFirst();
}
	
public E pollFirst() {
	if(size == 0) {	// 삭제할 요소가 없을 경우 null 반환 
		return null;
	}
		
	front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
	
	@SuppressWarnings("unchecked")
	E item = (E) array[front];	// 반환할 데이터 임시 저장 
	
	array[front] = null;	// 해당 front의 데이터 삭제
	size--;	// 사이즈 감소 
	
	
	// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
	if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
			
		// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다. 
		resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
	}
		
	return item;
}
	
public E remove() {
	return removeFirst();	// 예외는 removeFirst()에서 던져준다.
}

public E removeFirst() {
	E item = pollFirst();	// pollFirst()을 호출한다.
	
	if(item == null) {
		throw new NoSuchElementException();
	}
	
	return item;
}

 

여기서 @SuppressWarnings("unchecked") 에 대해 잠깐 언급하고 가겠다.

@SuppressWarnings("unchecked")을 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다. 반환되는 것을 보면 E 타입으로 캐스팅을 하고 있고 그 대상이 되는 것은 Object[] 배열의 Object 데이터다. 즉, Object -> E 타입으로 변환을 하는 것인데 이 과정에서 변환할 수 없는 타입을 가능성이 있다는 경고로 메소드 옆에 경고표시가 뜨는데, 우리가 push하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재한다. 

그렇기 때문에 형 안정성이 보장된다. 한마디로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 것이 @SuppressWarnings("unchecked") 이다. 물론 절대 남발하면 안되고, 형 변환시 예외 가능성이 없을 확실한 경우에 최소한의 범위에서 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있기 때문이다.

 

remove() 는 removeFirst() 메소드를 호출하고, removeFirst()는  pollFirst() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.

 

 

 

 

 

2. 후방 삭제 : pollLast()

 

 

pollFirst와는 달리 마지막에 있는 요소를 삭제하는 메소드다. 리스트에서는 removeLast()와 같은 역할인 것이다.

조금 응용하여 생각해보자면 offer() 와 pollLast() 을 조합하면 스택으로도 사용할 수 있는 것이다.

 

일단 그림을 먼저 보고 가자.

 

 

 

여기서 중요한 점은 offerFirst 때 했던 것처럼 rear 또한 0일 경우를 대비하여 -1 음수가 나오지 않도록 위치를 갱신할 때 용적의 크기만큼 더해준 뒤 나누어야 한다. 즉, rear = (rear - 1 + array.length) % array.length 를 해주어야 음수가 나오지 않는다.

 

public E pollLast() {
	if(size == 0) {	// 삭제할 요소가 없을 경우 null 반환 
		return null;
	}
		
	@SuppressWarnings("unchecked")
	E item = (E) array[rear];	// 반환할 데이터 임시 저장 
		
	array[rear] = null;	// 해당 rear의 데이터 삭제
	
	rear = (rear - 1 + array.length) % array.length; // rear 를 한 칸 옮긴다.
	size--;	// 사이즈 감소 
		
		
	// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
	if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
			
		// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다. 
		resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
	}
		
	return item;
}
	
public E removeLast() {
	E item = pollLast();
		
	if(item == null) {
		throw new NoSuchElementException();
	}
		
	return item;
}

 

 

removeLast() 메소드는 pollLast() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.

 

 

 

 

 

 

 

 

 

 

[poll / remove 메소드 묶어보기]

더보기 
@Override
public E poll() {		
	return pollFirst();
}
	
public E pollFirst() {
	if(size == 0) {
		return null;
	}		
	front = (front + 1) % array.length;
		
	@SuppressWarnings("unchecked")
	E item = (E) array[front];
		
	array[front] = null;
	size--;
		
	if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
		resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
	}
		
	return item;
}
	
public E remove() {
	return removeFirst();
}
	
public E removeFirst() {
	E item = pollFirst();
	
	if(item == null) {
		throw new NoSuchElementException();
	}
	
	return item;
}
	
	
public E pollLast() {
	if(size == 0) {
		return null;
	}
	
	@SuppressWarnings("unchecked")
	E item = (E) array[rear]; 
	
	array[rear] = null;	
	
	rear = (rear - 1 + array.length) % array.length;
	size--;
	
	if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
		resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
	}
		
	return item;
}
	
public E removeLast() {
	E item = pollLast();
	
	if(item == null) {
		throw new NoSuchElementException();
	}
	
	return item;
}

 

 

 

 

 

 

 

 

 

 

 

[peek 계열 메소드 구현]

 

 

 

보통 가장 앞 또는 뒤에 있는 데이터를 삭제하지 않고 확인만 하고싶을 때가 있다. 그럴 때 쓰는 것이 peek() 계열의 메소드다. 한마디로 poll() 메소드에서 삭제과정만 없는 것이 peek() 이다.

 

peek()은 가장 앞에 있는 데이터를 반환하는 것이고, 이는 peekFirst() 메소드와 같다.

또한 가장 뒤에 있는 데이터를 반환하는 것이 peekLast() 다.

그래서 pollFirst(), pollLast()에서 삭제과정만 빼고 그대로 반환하면 되기 때문에 설명 할 것이 없다.

 

그리고 참고로 덱에 데이터가 없는 경우는 null을 던진다. 반대로 이와 유사한 element() 메소드는 큐에 요소가 없을 경우 remove() 메소드와 마찬가지로 NoSuchElementException 예외를 던진다. 

이 때 보통은 elementLast()와 elementFirst()로 나뉠 것으로 예상했겠지만, 자바에서는 getLast()와 getFirst() 로 나뉜다.

 

 

즉, getFirst()가 elementFIrst() 의미라고 생각하고, getLast()가 elementLast() 의미라고 생각하면 된다.

 

 

 

 

 

1. peek, peekFirst 메소드

 

@Override
public E peek() {
	return peekFirst();
}
	
public E peekFirst() {
	// 요소가 없을 경우 null 반환
	if(size == 0) {
		return null;
	}
		
	@SuppressWarnings("unchecked")
	E item = (E) array[(front + 1) % array.length];
	return item;
}

 

마찬가지로 E 타입 원소를 반환해야하는지라 Object 타입을 E 타입으로 캐스팅을 해주면서 경고창이 뜬다. 하지만 poll()메소드에서 설명했듯이 마지막 원소 또한 E Type 외에 들어오는 것이 없기 때문에 형 안정성이 확보되므로 경고표시를 무시하기 위해 @SuppressWarnings("unchecked")을 붙인다.

 

 

 

 

 

2. peekLast() 메소드

 

public E peekLast() {
	// 요소가 없을 경우 null 반환
	if(size == 0) {
		return null;
	}
		
	@SuppressWarnings("unchecked")
	E item = (E) array[(rear)];
	return item;
}

 

removeLast() 에서 삭제 과정이 없는 것과 같다.

 

 

 

 

3. element, getFirst 메소드

 

public E element() { 
	return getFirst(); 
} 

public E getFirst() { 
	E item = peek(); 

	// 앞의 원소가 null 이라면(size = 0) 예외를 던진다.  
	if(item == null) { 
		throw new NoSuchElementException(); 
	} 
	return item; 
}

 

 

 

앞서 말했듯 element() 메소드와 getFirst() 는 같은 메소드다. 또한 우리가 구현한 peek 메소드를 호출하여 맨 앞의 원소를 얻고, 만약 null이라면 그 때 예외를 던져주면 된다.

 

 

 

 

 

4. getLast() 메소드

 

public E getLast() {
	E item = peekLast();

	// 앞의 원소가 null 이라면(size = 0) 예외를 던진다.
	if(item == null) {
		throw new NoSuchElementException();
	}
	return item;
}

 

마찬가지로 마지막 원소를 반환하되 null이면 예외를 던지면 된다.

 

 

 

 

 

[peek / element 메소드 묶어보기]

 

 

더보기 
@Override
public E peek() {
	return peekFirst();
}
	
public E peekFirst() {
	if(size == 0) {
		return null;
	}
	
	@SuppressWarnings("unchecked")
	E item = (E) array[(front + 1) % array.length];
	return item;
}
	
public E peekLast() {
	if(size == 0) {
		return null;
	}
		
	@SuppressWarnings("unchecked")
	E item = (E) array[(rear)];
	return item;
}
	
public E element() {
	return getFirst();
}
	
public E getFirst() {
	E item = peek();
	
	if(item == null) {
		throw new NoSuchElementException();
	}
	return item;
}
	
public E getLast() {
	E item = peekLast();
    
	if(item == null) {
		throw new NoSuchElementException();
	}
	return item;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

[size, isEmpty, contains, clear 메소드 구현]

 

 

 

이제 나머지는 그나마 자주 사용되는, 거의 필수적인 메소드를 구현해보고자 한다.

 

 

 

 

1. size() 메소드

 

 

size는 매우 간단하게 현재 덱에 있는 요소의 개수를 알려준다.

 

public int size() {
	return size;
}

 

 

 

 

 

2. isEmpty() 메소드

 

isEmpty() 메소드는 현재 덱에 비어있는지를 확인 할 때 쓰인다. 요소의 개수가 0개라면 비어있다는 뜻이므로, 비어있다면 true를, 비어있지 않다면 false를 반환한다.

 

public boolean isEmpty() {
	return size == 0;	
}

 

 

 

 

 

 

 

 

3. contains() 메소드

 

 

contains() 는 현재 찾고자하는 요소가 덱에 들어가있는지를 알려주는 메소드다.

 

public boolean contains(Object value) {
		
	int start = (front + 1) % array.length;
		
	/**
	 *  i : 요소 개수만큼만 반복한다. 
	 *  idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신 
	 */
	for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
		if(array[idx].equals(value)) {
			return true;
		}
	}
	return false;
}

 

이 때 0번째 인덱스부터 용적크기(array.length)까지 모두 검사할 수도 있겠지만, 기본적으로 용적 크기에 비해 요소의 개수가 훨씬 적은 경우가 많다.

 

굳이 모든 공간을 찾기보단, 요소의 개수만큼만 정확히 범위를 짚어서 반복해주는 것이 더욱 효율적이지 않겠는가?

 

만약 해당 범위 외의 공간에 요소가 있으면 어떡해요? 라고 한다면, 그 것은 구현이 잘못된 것이기에.. 한 마디로 잘못된 참조가 있다는 것이고 굳이 그 요소를 검사할 필요가 없다.

 

 

 

 

 

 

 

 

 

4. clear() 메소드

 

 

 

clear() 메소드는 단어 그대로 Deque의 모든 요소를 비워버린다.

 

public void clear() {
		
	for(int i = 0; i < array.length; i++) {
		array[i] = null;
	}
		
	front = rear = size = 0;
}

 

이 때는 혹시 모를 경우까지 대비해 모든 공간을 명시적으로 null 처리를 해주는 것이 좋다.

그리고 빈 공간은 초기 상태와 마찬가지로 front 와 rear와 size 모두 0으로 초기화 해준다.

 

 

 

 

 

이렇게 size, isEmpty, contains, clear 메소드들을 만들어보았다. 해당 메소드들을 묶어서 한 눈에 보고싶다면 아래 더보기를 누르면 된다.

 

 

 

[ size, isEmpty, contains, clear 메소드 묶어보기]

 

 

더보기 
public int size() {
	return size;
}

public boolean isEmpty() {
	return size == 0;
}
	
public boolean contains(Object value) {
		
	int start = (front + 1) % array.length;
		
	/**
	 *  i : 요소 개수만큼만 반복한다. 
	 *  idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신 
	 */
	for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
		if(array[idx].equals(value)) {
			return true;
		}
	}
	return false;
}
	
public void clear() {
		
	for(int i = 0; i < array.length; i++) {
		array[i] = null;
	}
		
	front = rear = size = 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<부가 목록>

 

 

[toArray, clone, sort 메소드 구현]

 

 

 

이 부분은 굳이 구현하는데 중요한 부분은 아니라 넘어가도 된다. 다만 조금 더 많은 기능을 원할 경우 추가해주면 좋은 메소드들이긴 하다. toArray는 사용자가 main 함수에서 특정 배열로 반환받고싶다거나 복사하고 싶을 때 Deque에 저장된 데이터들을 배열로 반환해주는 역할을 하기 위해 만들었다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 만드는 것이다. 

 

마지막으로 sort()메소드는 말 그대로 정렬해주는 메소드다.

 

 

 

 

 

1. toArray() 메소드

 

toArray()는 크게 두 가지가 있다.

하나는 아무런 인자 없이 현재 있는 큐의 요소들을 객체배열(Object[]) 로 반환해주는 Object[] toArray() 메소드가 있고,

다른 하나는 덱를 이미 생성 된 다른 배열에 복사해주고자 할 때 쓰는 T[] toArray(T[] a) 메소드가 있다.

 

즉 차이는 이런 것이다.

 

ArrayDeque<Integer> arraydeque = new ArrayDeque<>();

// get ArrayDeque to array (using toArray())
Object[] dq1 = arraydeque.toArray();

// get ArrayDeque to array (using toArray(T[] a)
Integer[] dq2 = new Integer[10];
dq2 = arraydeque.toArray(dq2);

 

1번의 장점이라면 덱에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점이다.

2번의 장점이라면 객체 클래스로 상속관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다. 또한 덱의 원소 5개가 있고, dq2 배열에 10개의 원소가 있다면 dq2에 0~4 index에 원소가 복사되고, 그 외의 원소는 기존 q2배열에 초기화 되어있던 원소가 그대로 남는다.

 

다만 ArrayDeque 에서는 앞(front)이 뒤(rear)보다 항상 앞에 있는 것이 아니라 중간이 비어버리는 경우가 발생할 수 있기 때문에 이러한 것을 방지하기 위해 정확한 시작 위치와 끝나는 위치 범위를 잘 설정해야 한다.

 

복사되는 원소의 범위는 (front + 1) % array.length 부터 rear까지다.

 

 

두 메소드 모두 구현해보자면 다음과 같다.

 

public Object[] toArray() {	
	return toArray(new Object[size]);
}
	

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
		
	final T[] res;
	// 들어오는 배열의 길이가 덱의 요소 개수보다 작은경우
	if(a.length < size) {
		/*
		 * front가 rear보다 뒤에 있을 경우 (또는 요소가 없을 경우 f==r)
		 *  ______________________
		 *  |  |  |  |  |  |  |  |
		 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
		 *    	f        r
		 */
		if(front <= rear) {
			return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
		}
		
	 	/*
		 * front가 rear보다 앞에 있을 경우
		 *  ______________________
		 *  |  |  |  |  |  |  |  |
		 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
		 *    	r        f
	  	 */
	 	
		res = (T[]) Arrays.copyOfRange(array, 0, size, a.getClass());
		int rearlength = array.length - 1 - front;	// 뒷 부분의 요소 개수
		
		// 뒷 부분 복사
		if(rearlength > 0) {
			System.arraycopy(array, front + 1, res, 0, rearlength);
		}
		// 앞 부분 복사  
		System.arraycopy(array, 0, res, rearlength, rear + 1);
		
		return res;
	}
	
		
	/*
	 * front가 rear보다 뒤에 있을 경우 (또는 요소가 없을 경우 f==r)
	 *  ______________________
	 *  |  |  |  |  |  |  |  |
	 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
	 *    	f        r
	 */
	if(front <= rear) {
		System.arraycopy(array, front + 1, a, 0, size);
	}
	
	
	/*
	 * front가 rear보다 앞에 있을 경우
	 *  ______________________
	 *  |  |  |  |  |  |  |  |
	 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
	 *    	r        f
	 */
	else {

		int rearlength = array.length - 1 - front;	// 뒷 부분의 요소 개수
		
		// 뒷 부분 복사
		if(rearlength > 0) {
			System.arraycopy(array, front + 1, a, 0, rearlength);
		}
		// 앞 부분 복사  
		System.arraycopy(array, 0, a, rearlength, rear + 1);
	}
	
	return a;
}

 

 

 

먼저 첫 번째 toArray() 메소드의 경우 두 번째 toArray(T[] a) 로 보내도록 하겠다. (동작 구현이 겹치기 때문이다.)

 

두 번째 T[] toArray(T[] a) 메소드를 보자.

이 부분은 제네릭 메소드로, 우리가 만들었던 ArrayQueue의 E타입하고는 다른 제네릭이다. 예로들어 E Type이 Integer라고 가정하고, T타입은 Object 라고 해보자.

Object는 Integer보다 상위 타입으로, Object 안에 Integer 타입의 데이터를 담을 수도 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.

즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성하는 것이다.

 

그리고 중요한 점이 있다. 기본적으로 toArray(T[] a) 에서 a로 들어오는 파라미터 배열의 길이가 덱에 들어있는 요소 개수보다 작은 경우 요소 개수를 모두 복사할 수 있도록 고려해야한다는 점에 추가하여 원형 큐로 구현하다보니  front와 rear의 위치에 따라 복사 과정이 다르다.

 

그냥 Arrays.copyOf() 메소드를 쓸 수 없다는 것이다.

만약 파라미터로 들어오는 배열의 경우 Arrays.copyOfRange() 로 지정된 범위 만큼 복사하여 크기를 맞춰주어야 하며, front와 rear의 위치에 따라 front가 rear보다 앞에 있는 경우 front + 1 ~ rear 까지 복사하면 되고, 만약 rear가 front 가 앞설 경우 front + 1 부터 시작하는 뒷 부분을 먼저 저장 한 뒤, 0번째부터 rear까지 뒤이어서 복사해주어야 한다.

 

조금 복잡해보일 수는 있으나, 최대한 이해할 수 있도록 주석을 달아놓았으니 참고해보고 이해가 안된다면 댓글은 남겨주시면 답변드리도록 하겠다.

 

 

 

 

 

 

 

 

 

2. clone() 메소드

 

만약 사용자가 사용하고 있던 Deque를 새로 하나 복제하고 싶을 때 쓰는 메소드다. 즉, 얕은 복사가 아닌 깊은 복사로 아예 다른 하나의 클론을 만드는 것이다.

단순히 = 연산자로 객체를 복사하게 되면 '주소'를 복사하는 것이기 때문에 복사한 객체에서 데이터를 조작할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(shallow copy)가 된다는 것이다.

 

ArrayDeque<Integer> original = new ArrayDeque<>();
original.offer(10);	// original에 10추가 

ArrayDeque<Integer> copy = original;
copy.offer(20);	// copy에 20추가

System.out.println("original ArrayDeque");
int i = 0;
for(Object a : original.toArray()) {
	System.out.println(i + "번 째 data = " + a);
	i++;
}

System.out.println("\ncopy ArrayDeque");
i = 0;
for(Object a : copy.toArray()) {
	System.out.println(i + "번 째 data = " + a);
	i++;
}

System.out.println("\noriginal ArrayDeque reference : " + original);
System.out.println("copy ArrayDeque reference : " + copy);

 

 

[결과]

 

 

보다시피 객체의 주소가 복사되는 것이기 때문에 주소와 데이터 모두 같아져버리는 문제가 발생한다.

 

 

이러한 것을 방지하기 위해서 깊은 복사를 하는데, 이 때 필요한 것이 바로 clone()이다. Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 구현해야 할 경우 반드시 Cloneable 인터페이스를 implement 해야한다.

 

즉, public class ArrayDeque<E> implements Queue<E> 에 Cloneable도 추가해주어야 한다.

그리고나서 clone()을 구현하면 되는데, 다음과 같이 재정의를 하면 된다.

@Override
public Object clone() {
		
	// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다. 
	try {
			
		@SuppressWarnings("unchecked")
		ArrayDeque<E> clone = (ArrayDeque<E>) super.clone();// 새로운 덱 객체 생성 
	
		// 새로운 덱의 배열도 생성해주어야 함 (내부 객체는 깊은 복사가 되지 않기 때문)
		clone.array = Arrays.copyOf(array, array.length);
		return clone;
	}
	catch(CloneNotSupportedException e) {
		throw new Error(e);
	}
}

 

조금 어려워 보일 수 있는데, 이해하지 못해도 된다. 자료구조에서 중요한 부분은 아니니... 

 

설명을 덧붙이자면, super.clone() 자체가 생성자 비슷한 역할이고 shallow copy를 통해 사실상 new ArrayDeque<>() 를 호출하는 격이라 제대로 완벽하게 복제하려면 clone한 큐의 array 또한 새로 생성해서 해당 배열에 copy를 해주어야 한다.

 

 

위와같이 만들고 나서 clone()한 것 까지 포함해서 테스트를 해보자.

 

ArrayDeque<Integer> original = new ArrayDeque<>();
original.offer(10); // original에 10추가

ArrayDeque<Integer> copy = original;
ArrayDeque<Integer> clone = (ArrayDeque<Integer>) original.clone();

copy.offer(20); // copy에 20추가
clone.offer(30); // clone에 30추가

System.out.println("original ArrayDeque");
int i = 0;
for (Object a : original.toArray()) {
	System.out.println(i + "번 째 data = " + a);
	i++;
}

System.out.println("\ncopy ArrayDeque");
i = 0;
for (Object a : copy.toArray()) {
	System.out.println(i + "번 째 data = " + a);
	i++;
}

System.out.println("\nclone ArrayDeque");
i = 0;
for (Object a : clone.toArray()) {
	System.out.println(i + "번 째 data = " + a);
	i++;
}

System.out.println("\noriginal ArrayDeque reference : " + original);
System.out.println("copy ArrayDeque reference : " + copy);
System.out.println("clone ArrayDeque reference : " + clone);

 

 

[결과]

 

 

결과적으로 clone으로 복사한 ArrayDeque는 원본 ArrayDeque에 영향을 주지 않는다. 

 

 

 

 

 

 

3. sort() 메소드

 

 

 

ArrayDeque의 경우는 내부적으로 Object[] 배열을 사용하기 때문에 정렬 자체는 매우 쉽다.

 

 

일단 sort()를 구현하기 전에 자바의 비교기에 대해 알아야 한다.

자바의 데이터 정렬을 위한 비교기는 크게 두 가지가 있다. 하나는 Comparable, 다른 하나는 Comparator다. 정말정말 쉽게 말하자면 Comparable을 쓰는 경우는 해당 객체의 기본 정렬 방법을 설정할 때이고, Comparator의 경우는 특정한 경우에 임시적으로 쓸 수 있게 정렬을 정의할 때 쓰인다.

 

 

우리가 흔히 쓰는 int[] 배열, String[] 배열 등 수많은 클래스들은 기본적으로 자체 정렬 방식을 지원하기 때문에 Comparator을 쓰지 않아도 정렬 할 수 있었다.

 

만약 래퍼(Wrapper) 클래스 타입(ex. Integer, String, Double ...)이라면 따로 Comparator 을 구현해주지 않아도 되지만, 사용자 클래스, 예로들어 Student 클래스를 만든다거나.. 이러한 경우는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 또는 Comparator를 구현해주어 파라미터로 넘겨주어야 한다.

 

Arrays.sort() 메소드를 뜯어본 분들은 알겠지만 Arrays.sort()의 종류중에서는 인자를 두 개 받는 경우가 있다. 정렬을 해보신 분은 알겠지만 가끔 2차원 배열을 정렬하고 싶을 때 다음과 같이 쓰지 않았는가?

 

int[][] arr = new int[10][10];

Arrays.sort(arr, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
		// 구현부
	}
});

 

이러한 메소드가 바로 아래 사진의 메소드로 간다.

 

 

 

 

 

위 사진을 보면 크게 if(c == null) 일 경우와 아닌 경우로 나뉜다.

즉, Comparator 인자가 있는지, 또는 없는지를 말해주는데, Comparator 인자(c)가 없는 경우 해당 객체의 Comparable 구현이 있는지를 확인하고 있으면 정렬하며, 구현되지 않았을 경우 에러를 뱉는다.

 

결과적으로 sort() 메소드를 만들 때, 기본적으로 두 가지 경우를 생각해야 한다는 것이다. 첫 번째는 객체에 Comparable이 구현되어 있어 따로 파라미터로 Comparator를 넘겨주지 않는 경우고, 다른 하나는 Comparator을 넘겨주어 정의 된 정렬 방식을 사용하는 경우다.

 

public void sort() {
	/**
	 *  Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
	 *  정렬 방식을 사용한다.
	 *  만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
	 *  에러가 발생한다.
	 *  만약 구현되어있을 경우 null로 파라미터를 넘기면
	 *  Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
	 */
	sort(null);
}
	
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
	
	// null 접근 방지를 위해 toArray로 요소만 있는 배열을 얻어 이를 정렬한뒤 덮어씌운다. 
	Object[] res = toArray();
	
	Arrays.sort((E[]) res, 0, size, c);
	
	clear();
	/*
	 *  정렬된 원소를 다시 array에 0부터 차례대로 채운다. 
	 *  이 때 front = 0 인덱스는 비워야 하므로 사실상 1번째 인덱스부터 채워야 한다.
	 *  
	 */
	System.arraycopy(res, 0, array, 1, res.length);	// res 배열을 array에 복사 
	
	this.rear = this.size = res.length;
	
}

 

여기서 Comparator<? super E> 는 상속관계이면서 부모 클래스에서 정렬 방식을 따르는 경우도 생각하여 <? super E>로 하였다. 이러한 경우를 고려하지 않는다면 Comparator<E>로 해주어도 종속관계 영향을 안받는 객체의 경우는 괜찮다.

 

그런다음 Object[] 배열을 Arrays.sort()메소드를 통해 정렬해주면 된다. 이 때 배열에 null이 들어가 있으면 NullPointerException 예외가 발생하기 때문에 이를 방지하기 위해 우리가 앞서 만들었던 toArray() 메소드를 이용하여 요소들만 있는 배열을 하나 임시로 만들어 이 임시배열을 정렬해준뒤, 기존에 있던 배열(array)를 초기화 하고 이 배열에 덮어씌워주는 방식으로 한다.

 

 

이때 Comparator를 넘겨주는 방식은 크게 두 가지가 있는데, 그 중 하나인 Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) 를 쓸 것이다.

관련 API 문서는 아래 링크로 남겨두겠다.

 

docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html#sort(T%5B%5D,int,int,java.util.Comparator)

 

Arrays (Java SE 11 & JDK 11 )

Compares two int arrays lexicographically over the specified ranges. If the two arrays, over the specified ranges, share a common prefix then the lexicographic comparison is the result of comparing two elements, as if by Integer.compare(int, int), at a rel

docs.oracle.com

 

 

 

그럼 한 번 테스트를 해보자. 

 

Student 클래스를 통해 이름과 성적을 입력받고, 이를 정렬하는 테스트를 해보도록 한다.

 

<Student 클래스가 Comparable을 구현하지 않았을 경우>

 

[test.java]

public class test {
	public static void main(String[] args) {

		ArrayDeque<Student> dq = new ArrayDeque<>();
		
		dq.offer(new Student("Chen" , 89));
		dq.offer(new Student("Malli" , 65));
		dq.offer(new Student("Tomas" , 53));
		dq.offer(new Student("Cris" , 79));
		dq.offer(new Student("Julia" , 93));
		
		dq.sort();
		
		for(Object a : dq.toArray()) {
			System.out.println(a);
		}
	}
}

class Student {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
}

 

 

[결과]

 

 

이렇게 Comparable을 구현하지 않아 해당 객체의 정렬 방법을 몰라 빨갛게 에러를 뱉어준다. 즉, 명시적으로 Arrays.sort()에 정렬 방법을 알려주던가, Student 클래스에 정렬 방법을 구현하던가 해야한다.

 

 

 

 

 

 

<Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법>

 

[test.java]

import java.util.Comparator;

public class test {
	public static void main(String[] args) {

		ArrayDeque<Student> dq = new ArrayDeque<>();
		
		dq.offer(new Student("Chen" , 89));
		dq.offer(new Student("Malli" , 65));
		dq.offer(new Student("Tomas" , 53));
		dq.offer(new Student("Cris" , 79));
		dq.offer(new Student("Julia" , 93));
		
		dq.sort(customComp);
		
		for(Object a : dq.toArray()) {
			System.out.println(a);
		}
	}
	// 사용자 설정 comparator(비교기)
	static Comparator<Student> customComp = new Comparator<Student>() {
		@Override
		public int compare(Student o1, Student o2) {
			return o2.score - o1.score;	// 성적 내림차순
		}
	};
}

class Student {
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
}

 

 

이렇게 하면 정렬이 될까? 당연하겠지만 된다.

 

 

[결과]

 

 

 

 

 

 

 

<Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법>

 

객체 기본 정렬방식을 설정해주는 방법. 즉 Comparable 구현 방법으로도 가능하다.

 

public class test {
	public static void main(String[] args) {

		ArrayDeque<Student> dq = new ArrayDeque<>();
		
		dq.offer(new Student("Chen" , 89));
		dq.offer(new Student("Malli" , 65));
		dq.offer(new Student("Tomas" , 53));
		dq.offer(new Student("Cris" , 79));
		dq.offer(new Student("Julia" , 93));
		
		dq.sort();	// Comparator 인자가 필요하지 않음

		for(Object a : dq.toArray()) {
			System.out.println(a);
		}
	}
}

class Student implements Comparable<Student>{
	String name;
	int score;
	
	Student(String name, int score){
		this.name = name;
		this.score = score;
	}
	
	public String toString() {
		return "이름 : " + name + "\t성적 : " + score;
	}
	
	@Override
	public int compareTo(Student o) {
		return o.score - this.score;
	}
}

 

 

이러면 sort() 내부에서 Comparator가 없으니 해당 클래스의 Comparable에서 compareTo() 을 구현한 내용을 찾아 작성한대로 정렬을 해준다.

 

[결과]

 

 

 

 

 

 

 

 

 

[toArray, clone, sort 메소드 묶어보기]

 

더보기

 

public Object[] toArray() {	
	return toArray(new Object[size]);
}
	

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
		
	final T[] res;
	if(a.length < size) {
		if(front <= rear) {
			return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
		}
		res = (T[]) Arrays.copyOfRange(array, 0, size, a.getClass());
		int rearlength = array.length - 1 - front;	
		if(rearlength > 0) {
			System.arraycopy(array, front + 1, res, 0, rearlength);
		}
		System.arraycopy(array, 0, res, rearlength, rear + 1);
		
		return res;
	}
	
	if(front <= rear) {
		System.arraycopy(array, front + 1, a, 0, size);
	}
	else {
		int rearlength = array.length - 1 - front;	
		if(rearlength > 0) {
			System.arraycopy(array, front + 1, a, 0, rearlength);
		}
		System.arraycopy(array, 0, a, rearlength, rear + 1);
	}
	
	return a;
}	

	
@Override
public Object clone() {
	try {
		@SuppressWarnings("unchecked")
		ArrayDeque<E> clone = (ArrayDeque<E>) super.clone();
		clone.array = Arrays.copyOf(array, array.length);
		return clone;
	}
	catch(CloneNotSupportedException e) {
		throw new Error(e);
	}
}
	
	
public void sort() {
	sort(null);
}
	
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
	Object[] res = toArray();
	Arrays.sort((E[]) res, 0, size, c);
	
	clear();
	System.arraycopy(res, 0, array, 1, res.length);	
	
	this.rear = this.size = res.length;
}

 

 

 

 

 

 

 

 

 

 






  • 전체 코드

 

 

 

 

import Interface_form.Queue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

/**
*
* @param <E> the type of elements in this Deque
* 
* @author st-lab.tistory.com
* @version 1.0
* @see Queue
* 
*/

public class ArrayDeque<E> implements Queue<E>, Cloneable {

	private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기

	private Object[] array; // 요소를 담을 배열
	private int size; // 요소 개수

	private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
	private int rear; // 마지막 요소의 인덱스를 가리키는 변수

	// 생성자1 (초기 용적 할당을 안할 경우)
	public ArrayDeque() {
		this.array = new Object[DEFAULT_CAPACITY];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}

	// 생성자2 (초기 용적 할당을 할 경우)
	public ArrayDeque(int capacity) {
		this.array = new Object[capacity];
		this.size = 0;
		this.front = 0;
		this.rear = 0;
	}

	private void resize(int newCapacity) {

		int arrayCapacity = array.length; // 현재 용적 크기

		Object[] newArray = new Object[newCapacity]; // 용적을 변경한 배열

		/*
		 * i = new array index 
		 * j = original array 
		 * index 요소 개수(size)만큼 새 배열에 값 복사
		 */
		for (int i = 1, j = front + 1; i <= size; i++, j++) {
			newArray[i] = array[j % arrayCapacity];
		}

		this.array = null;
		this.array = newArray; // 새 배열을 기존 array의 배열로 덮어씌움

		front = 0;
		rear = size;

	}

	@Override
	public boolean offer(E item) {
		return offerLast(item);
	}
	
	public boolean offerLast(E item) {
		
		// 용적이 가득 찼을 경우 
		if((rear + 1) % array.length == front) {
			resize(array.length * 2);	// 용적을 두 배 늘려준다. 
		}
		
		rear = (rear + 1) % array.length;	// rear을 rear의 다음 위치로 갱신 
		
		array[rear] = item;
		size++;	// 사이즈 1 증가 
		
		return true;
	}
	
	public boolean offerFirst(E item) {
		// 용적이 가득 찼을 경우 
		if((front - 1 + array.length) % array.length == rear) {
			resize(array.length * 2);	// 용적을 두 배 늘려준다. 
		}
		
		array[front] = item;	// front위치는 빈 공간이기 때문에 추가 해준 뒤 front 값을 갱신한다.
		front = (front - 1 + array.length) % array.length;
		size++;	// 사이즈 1 증가
		
		return true;
	}
	
	

	@Override
	public E poll() {		
		return pollFirst();
	}
	
	public E pollFirst() {
		if(size == 0) {	// 삭제할 요소가 없을 경우 null 반환 
			return null;
		}
		
		front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
		
		@SuppressWarnings("unchecked")
		E item = (E) array[front];	// 반환할 데이터 임시 저장 
		
		array[front] = null;	// 해당 front의 데이터 삭제
		size--;	// 사이즈 감소 
		
		
		// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
		if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
			
			// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다. 
			resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
		}
		
		return item;
	}
	
	public E remove() {
		return removeFirst();	// 예외는 removeFirst()에서 던져준다.
	}
	
	public E removeFirst() {
		E item = pollFirst();
		
		if(item == null) {
			throw new NoSuchElementException();
		}
		
		return item;
	}
	

	
	public E pollLast() {
		if(size == 0) {	// 삭제할 요소가 없을 경우 null 반환 
			return null;
		}
		
		@SuppressWarnings("unchecked")
		E item = (E) array[rear];	// 반환할 데이터 임시 저장 
		
		array[rear] = null;	// 해당 rear의 데이터 삭제
		
		rear = (rear - 1 + array.length) % array.length; // rear 를 한 칸 옮긴다.
		size--;	// 사이즈 감소 
		
		
		// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
		if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
			
			// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다. 
			resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
		}
		
		return item;
	}
	
	public E removeLast() {
		E item = pollLast();
		
		if(item == null) {
			throw new NoSuchElementException();
		}
		
		return item;
	}

	
	@Override
	public E peek() {
		return peekFirst();
	}
	
	public E peekFirst() {
		// 요소가 없을 경우 null 반환
		if(size == 0) {
			return null;
		}
		
		@SuppressWarnings("unchecked")
		E item = (E) array[(front + 1) % array.length];
		return item;
	}
	
	public E peekLast() {
		// 요소가 없을 경우 null 반환
		if(size == 0) {
			return null;
		}
		
		@SuppressWarnings("unchecked")
		E item = (E) array[(rear)];
		return item;
	}
	
	public E element() {
		return getFirst();
	}
	
	public E getFirst() {
		E item = peek();
		
		// 앞의 원소가 null 이라면(size = 0) 예외를 던진다. 
		if(item == null) {
			throw new NoSuchElementException();
		}
		return item;
	}
	
	public E getLast() {
		E item = peekLast();

		// 앞의 원소가 null 이라면(size = 0) 예외를 던진다.
		if(item == null) {
			throw new NoSuchElementException();
		}
		return item;
	}
	
	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
	
	public boolean contains(Object value) {
		
		int start = (front + 1) % array.length;
		
		/**
		 *  i : 요소 개수만큼만 반복한다. 
		 *  idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신 
		 */
		for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
			if(array[idx].equals(value)) {
				return true;
			}
		}
		return false;
	}
	
	public void clear() {
		
		for(int i = 0; i < array.length; i++) {
			array[i] = null;
		}
		
		front = rear = size = 0;
	}
	
	
	public Object[] toArray() {	
		return toArray(new Object[size]);
	}
	

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		
		final T[] res;
		// 들어오는 배열의 길이가 덱의 요소 개수보다 작은경우
		if(a.length < size) {
			/*
			 * front가 rear보다 뒤에 있을 경우 (또는 요소가 없을 경우 f==r)
			 *  ______________________
			 *  |  |  |  |  |  |  |  |
			 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
			 *    	f        r
			 */
			if(front <= rear) {
				return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
			}
			
			/*
			 * front가 rear보다 앞에 있을 경우
			 *  ______________________
			 *  |  |  |  |  |  |  |  |
			 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
			 *    	r1        f4
			 */
			
			res = (T[]) Arrays.copyOfRange(array, 0, size, a.getClass());
			int rearlength = array.length - 1 - front;	// 뒷 부분의 요소 개수
			
			// 뒷 부분 복사
			if(rearlength > 0) {
				System.arraycopy(array, front + 1, res, 0, rearlength);
			}
			// 앞 부분 복사  
			System.arraycopy(array, 0, res, rearlength, rear + 1);
			
			return res;
		}
		
		
		/*
		 * front가 rear보다 뒤에 있을 경우 (또는 요소가 없을 경우 f==r)
		 *  ______________________
		 *  |  |  |  |  |  |  |  |
		 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
		 *    	f        r
		 */
		if(front <= rear) {
			System.arraycopy(array, front + 1, a, 0, size);
		}
		
		
		/*
		 * front가 rear보다 앞에 있을 경우
		 *  ______________________
		 *  |  |  |  |  |  |  |  |
		 *  ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
		 *    	r        f
		 */
		else {

			int rearlength = array.length - 1 - front;	// 뒷 부분의 요소 개수
			
			// 뒷 부분 복사
			if(rearlength > 0) {
				System.arraycopy(array, front + 1, a, 0, rearlength);
			}
			// 앞 부분 복사  
			System.arraycopy(array, 0, a, rearlength, rear + 1);
		}
		
		return a;
	}
	
	
	@Override
	public Object clone() {
		
		// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다. 
		try {
			
			@SuppressWarnings("unchecked")
			ArrayDeque<E> clone = (ArrayDeque<E>) super.clone();// 새로운 덱 객체 생성 
		
			// 새로운 덱의 배열도 생성해주어야 함 (내부 객체는 깊은 복사가 되지 않기 때문)
			clone.array = Arrays.copyOf(array, array.length);
			return clone;
		}
		catch(CloneNotSupportedException e) {
			throw new Error(e);
		}
	}
	
	
	public void sort() {
		/**
		 *  Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
		 *  정렬 방식을 사용한다.
		 *  만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
		 *  에러가 발생한다.
		 *  만약 구현되어있을 경우 null로 파라미터를 넘기면
		 *  Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
		 */
		sort(null);
	}
	
	@SuppressWarnings("unchecked")
	public void sort(Comparator<? super E> c) {
		
		// null 접근 방지를 위해 toArray로 요소만 있는 배열을 얻어 이를 정렬한뒤 덮어씌운다. 
		Object[] res = toArray();
		
		Arrays.sort((E[]) res, 0, size, c);
		
		clear();
		/*
		 *  정렬된 원소를 다시 array에 0부터 차례대로 채운다. 
		 *  이 때 front = 0 인덱스는 비워야 하므로 사실상 1번째 인덱스부터 채워야 한다.
		 *  
		 */
		System.arraycopy(res, 0, array, 1, res.length);	// res 배열을 array에 복사 
		
		this.rear = this.size = res.length;
	}
}

 

 

 

 

 

 

 

 

 

 

위 코드는 아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.

 

 

 

 

[소스코드 모아보기]

 

github 자료구조 모음

 

kdgyun/Data_Structure

Contribute to kdgyun/Data_Structure development by creating an account on GitHub.

github.com

 

 

 

 

 

 

 







  • 정리



 

ArrayDeque에 대한 기본적인 메소드와 더불어 추가적인 메소드들을 구현해보았다. 

 

기본적으로 Deque는 자바로 구현할 경우 LinkedList로 구현하는게 훨씬 편하다. 원래 필자도 덱은 LinkedList(연결리스트)로만 구현할까 하다가 구글에서 찾아보니 배열로 구현한 글은 거의 없길래 구현했다. (막상 자바에서는 배열로 구현되고 있는데...)

 

심지어 자바뿐만 아니라 대부분 언어들도 구조체를 이용하여 연결리스트처럼 구현했다. 물론 배열로 구현하면 고려해야할 점이 많긴 하나 그래도 막상 원리만 이해한다면 어렵지 않게 구현할 수 있다.

 

이 글을 이해하신다면 LinkedList로 구현한 Deque의 경우 훨씬 쉽게 풀 수 있을 것이라 장담한다.

 

 

 

또한 어렵거나 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.

 

 

 

 

 

 

 

저작자표시 비영리 변경금지

'자료구조 > Java' 카테고리의 다른 글

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기  (52) 2021.02.10
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기  (6) 2020.12.17
자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기  (21) 2020.12.09
자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기  (27) 2020.12.07
자바 [JAVA] - Queue Interface (큐 인터페이스)  (2) 2020.12.01

티스토리툴바