자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기
자료구조 관련 목록 링크 펼치기
0. 자바 컬렉션 프레임워크 (Java Collections Framework)
3. 단일 연결리스트 (Singly LinkedList)
4. 이중 연결리스트 (Doubly LinkedList)
6. 스택 (Stack)
9. 연결리스트 큐 (LinkdedList Queue) - [현재 페이지]
11. 연결리스트 덱 (LinkedList Deque)
12. 힙 (Heap)
15. 해시 셋 (Hash Set)
17. 이진 탐색 트리 (Binary Search Tree)
- Queue (using LinkedList)
만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글과 큐 인터페이스 (Queue Interface)을 먼저 보고 오셨으면 한다. (필자가 앞서 언급했지만, Stack 인터페이스를 만들어 두고 이를 implements 하여 구체적으로 구현하고자 한다고 했다. 그러니 꼭 스택 인터페이스 글도 읽어오시길 바란다.)
또한 추가로 단순히 int형식에 한정한 구현이 아닌 제네릭을 사용하여 구현을 할 것이라 최소한의 제네릭에 대한 이해를 필요로 하니 필요하다면 다음 글도 읽어오는 것을 추천드린다.
그리고 '반드시' LinkedList 구현과 배열 큐 글을 읽고 오시길 바란다.
이 번에 구현 할 큐는 LinkedList 즉, 연결리스트를 기반으로 구현하기 때문에 기본적인 LinkedList에 대한 이해가 필요하고, 배열 큐의 경우 해당 포스팅에서 큐에대한 기본적인 지식도 담겨있으니 메커니즘을 최소한 이해하고 넘어가고 보면 좋겠다.
보통은 자바에서 Queue라고 한다면 다음과 같이 썼을 것이다.
Queue<Integer> q = new LinkedList<>();
자바에서는 큐의 경우 LinkedList로 구현한 큐가 쓰이는 만큼 가장 대중적이고, 배열로 구현하는 큐에 비해 쉽다. (적어도 필자는 그렇게 생각한다..)
이유가 뭔가하면 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고있고, 요소가 배열에 들어있는 양에 따라 용적(배열 크기)을 줄이거나 늘려주어야 하고, 큐를 선형적인 큐로 구현했을 경우 요소들이 뒤로 쏠리기 때문에 이러한 문제를 효율적으로 극복하고자 원형 형태로 구현하는데 이 구현이 고려해야 할 점도 많고 조금 복잡하다.
하지만 배열 대신 연결리스트로 구현하게 될 경우 위와같은 단점들이 해결된다. 각 데이터들을 노드(node) 객체에 담고 노드 간 서로 연결해주기 때문에 배열처럼 요소 개수에 따라 늘려주거나 줄여줄 필요도 없고 삽입, 삭제 때는 연결 된 링크만 끊어주거나 이어주면 되기 때문에 관리면에서도 편하다.
그럼 큐는 무엇인가. 큐는 기본 원칙이 '선입선출(FIFO : First in First out)' 이다.
선입선출.. 한자로 先入先出 이다. 말 그대로 '먼저 들어온 것이 먼저 나오는 방식'이다.
그림으로 보면 이렇다.
우리가 흔히 '줄을 서서 대기하는 모습'을 상상하면 된다.
그럼 연결리스트로 구현 된 큐는 어떻게 생겼을까? 이번 큐에서 쓰이는 연결리스트는 단일 연결리스트로 구현 하게 되는데, 먼저 데이터를 담는 객체는 Node(노드)라는 객체는 다음과 같은 구성을 갖고 있다.
그리고 위 노드들을 연결한 형식이 LinkedList(연결리스트)가 되고, 좀 더 세밀하게 말하자면 Singly Linked List(단일 연결리스트)가 된다. 그리고 그 자체를 갖고 큐의 기능을 넣는 것이다. 그림으로 보면 이렇다.
위에서 만약 offer() 메소드를 통해 데이터를 추가 한다고 하면 다음과 같을 것이다.
반대로 poll() 메소드를 통해 선입되었던 데이터를 삭제한다고 한다면 다음과 같을 것이다.
위와 같은 형식으로 연결 리스트를 통해 큐(Queue)를 구현하면 되는 것이다. 이러한 큐를 보통 'Linked Queue', LinkedList-Queue' 라고 불린다. 해석하자면 '연결형 큐' 또는 '연결리스트 큐' 라고 하는데, 어느쪽으로 부르 건 상관은 없다. 연결형인 것도 맞고 큐를 연결형 자료구조로 LinkedList를 쓰는 것도 맞고, LinkedList가 연결형인 것도 맞기 때문에..
참고로 보통은 linked list implementation of queue 정도로 말하는데, 일단 포스팅에서는 '연결리스트 큐'로 통일하여 말하겠다.
구현 방식은 단일 연결리스트(단방향 연결리스트)와 진짜 거의 다를게 없기 때문에 연결리스트를 구현해보셨다면 쉽게 구현할 수 있을 것이다.
- Node 구현
그러면 우리가 LinkedList를 기반으로 Queue를 구현하기에 앞서 가장 기본적인 데이터를 담을 Node 클래스를 먼저 구현하고자 한다. 이 때 Node 클래스는 앞으로 구현 할 LinkedListQueue와 같은 패키지에 생성할 것이다. 만약 다른 패키지에 생성하면 LinkedListQueue 구현 할 때 'import Node클래스가 있는 패키지 경로.Node;' 를 해주면 된다.
[Node.java]
class Node<E> {
E data;
Node<E> next; // 다음 노드를 가리키는 역할을 하는 변수
Node(E data) {
this.data = data;
this.next = null;
}
}
- LinkedList Queue 구현
- 사전 준비
[Queue Interface 소스]
[Queue.java]
package Interface_form;
/**
*
* 자바 Queue Interface입니다. <br>
* Queue는 ArrayQueue, LinkedQueue,
* Deque, 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();
}
[구현 바로가기]
<필수 목록>
◦ size, isEmpty, contains ,clear 메소드 구현
<부가 목록>
◦ 전체 코드
[Queue 클래스 및 생성자 구성하기]
이 번에 구현 할 큐는 연결리스트를 기반으로 구현되기 때문에 클래스 이름을 LinkedListQueue 라는 이름으로 생성한다. 그리고 앞선 Queue Interface 포스팅에서 작성했던 Queue 인터페이스를 implements 해준다. (필자의 경우 인터페이스는 Interface_form 이라는 패키지에 생성해두었다.)
implements 를 하면 class 옆에 경고표시가 뜰 텐데 인터페이스에 있는 메소드들을 구현하라는 것이다. 어차피 모두 구현해나갈 것이기 때문에 일단은 무시한다.
[LinkedListQueue.java]
public class LinkedListQueue<E> implements Queue<E> {
private Node<E> head;
private Node<E> tail;
private int size;
public LinkedListQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
변수부터 먼저 차례대로 설명해주도록 하겠다.
head : 큐에서 가장 앞에있는 노드 객체를 가리키는 변수
tail : 큐에서 가장 뒤에있는 노드 객체를 가리키는 변수
size : 큐에 담긴 요소의 개수
너무나 당연하겠지만 처음 큐를 생성할 때는 아무런 데이터가 없으므로 head와 tail은 가리킬 노드가 없는상태이므로 null로 초기화해주고, size 또한 0으로 초기화 해준다.
메인 클래스에서 객체를 생성한다면 다음과 같이 생성하게 된다.
LinkedListQueue<Integer> q = new LinkedListQueue<>();
그럼 이제 본격적으로 하나씩 구현해보자.
[offer 메소드 구현]
Queue에 데이터를 추가하는 메소드다.
Queue는 기본적으로 offer는 후방(맨 뒤)에 데이터를 추가해야한다. 리스트로 치면 add(E value)와 같은 역할이다.
- 가장 마지막 부분에 추가 - offer(E item)
그림으로 과정을 보면 이렇다.
이를 토대로 구현해보자.
1. 기본 삽입 : offer(E item)
구현 자체는 그리 어렵지 않다. offer() 메소드를 구현하자면 이렇다.
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<E>(value);
// 비어있을 경우
if(size == 0) {
head = newNode;
}
// 그 외의 경우 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 한다.
else {
tail.next = newNode;
}
/**
* tail이 가리키는 노드를 새 노드로 바꿔준다.
*/
tail = newNode;
size++;
return true;
}
또한 중요한 점은 큐에 아무 요소들이 없을 때. 즉 size가 0일 때는 새 요소가 head이자 tail이 된다. 그렇기 때문에 큐가 비어있을 경우에는 head를 새 노드를 가리키도록 해야하고 그 외에는 이미 요소가 있다는 의미이므로 tail이 가리키는 요소의 다음 노드(tail.next)를 새 노드를 가리키도록 한 뒤 tail이 가리키는 노드를 새 노드를 가리키도록 한다.
[offer 메소드 묶어보기]
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<E>(value);
if(size == 0) {
head = newNode;
}
else {
tail.next = newNode;
}
tail = newNode;
size++;
return true;
}
[poll 메소드 구현]
poll 메소드 또한 그리 어렵지 않게 만들 수 있다. 리스트에서의 remove()와 같은 역할로 가장 앞에있는 위치에 있는 요소인 head 요소를 삭제하면 된다.
다만 중요한 점은 '삭제할 요소가 없는 경우' 다.
자바의 Queue에 관한 API 문서를 보면 알겠지만, add() - offer(), remove() - poll(), element() - peek() 이 각각 대응되는데, 자바에서 둘 다 제공하는 이유는 다음과 같다.
참고 문서 링크 : docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html
(add()의 경우 만약 용적이 제한되어있는데 용적보다 더 많은 요소를 추가 할 경우 예외를 던지는데, 지금 구현하는 것에서는 최대 제한을 걸지 않아 넘어갔다.)
삭제의 경우 remove() 같은 경우 삭제 할 요소가 없으면 NoSuchElementException() 예외를 던진다. 반대로 poll()의 경우는 삭제 할 요소가 없다면 null을 반환한다는 차이점이 있다.
일단 poll() 메소드를 구현하고 이를 remove() 메소드에 응용하여 적용해보도록 하자.
poll의 구조 또한 매우 쉬우니 그림을 다시 한 번 보고 구현해보도록 하자.
1. poll() 메소드
@Override
public E poll() {
// 삭제할 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
// 삭제될 요소의 데이터를 반환하기 위한 임시 변수
E element = head.data;
// head 노드의 다음노드
Node<E> nextNode = head.next;
// head의 모든 데이터들을 삭제
head.data = null;
head.next = null;
// head 가 가리키는 노드를 삭제된 head노드의 다음노드를 가리키도록 변경
head = nextNode;
size--;
return element;
}
과정 자체는 그리 어렵지 않다. 위 그림 순서 그대로 구현되었기 때문에 아마 이해하기는 쉬울 것이다. 그리고 앞서 말했듯 poll() 은 삭제할 요소가 없을 경우 예외를 던지는 것이 아닌 null을 반환해야하므로 size가 0일 때 null을 반환한다.
.
2. remove() 메소드
public E remove() {
E element = poll();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
remove() 메소드는 poll() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.
[poll / remove 메소드 묶어보기]
@Override
public E poll() {
if(size == 0) {
return null;
}
E element = head.data;
Node<E> nextNode = head.next;
head.data = null;
head.next = null;
head = nextNode;
size--;
return element;
}
public E remove() {
E element = poll();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
[peek() 메소드 구현]
가장 앞에 있는 데이터(head.data)를 삭제하지 않고 확인만 하고싶을 때가 있다. 그럴 때 쓰는 것이 peek() 메소드다. 한마디로 poll() 메소드에서 삭제과정만 없는 것이 peek() 이다.
그래서 삭제과정만 빼고 그대로 반환하면 되기 때문에 설명 할 것이 없다.
참고로 큐에 데이터가 없는 경우는 null을 던진다. 반대로 이와 유사한 element() 메소드는 큐에 요소가 없을 경우 remove() 메소드와 마찬가지로 NoSuchElementException 예외를 던진다. 위 처럼 두 가지 모두 구현해보도록 해보자.
1. peek() 메소드
@Override
public E peek() {
// 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
return head.data;
}
head의 데이터를 그대로 반환하기만 하면 되기 때문에 그리 어렵지 않다.
2. element() 메소드
public E element() {
E element = peek();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
위에서 만든 peek()메소드로 데이터를 얻은 뒤, 얻은 요소가 null 이라면 예외를 던진다.
[peek / element 메소드 묶어보기]
@Override
public E peek() {
if(size == 0) {
return null;
}
return head.data;
}
public E element() {
E element = peek();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
[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) {
/**
* head 데이터부터 x가 null이 될 때까지 value랑 x의 데이터(x.data)랑
* 같은지를 비교하고 같을 경우 true를 반환한다.
*/
for(Node<E> x = head; x != null; x = x.next) {
if(value.equals(x.data)) {
return true;
}
}
return false;
}
.
4. clear() 메소드
clear() 메소드는 단어 그대로 Queue의 모든 요소를 비워버린다.
public void clear() {
for(Node<E> x = head; x != null; ) {
Node<E> next = x.next;
x.data = null;
x.next = null;
x = next;
}
size = 0;
head = tail = null;
}
이 때는 모든 데이터를 명시적으로 null 처리를 해주는 것이 좋다.
그리고 빈 공간은 초기 상태와 마찬가지로 head 와 tail와 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) {
for(Node<E> x = head; x != null; x = x.next) {
if(value.equals(x.data)) {
return true;
}
}
return false;
}
public void clear() {
for(Node<E> x = head; x != null; ) {
Node<E> next = x.next;
x.data = null;
x.next = null;
x = next;
}
size = 0;
head = tail = null;
}
<부가 목록>
[toArray, clone, sort 메소드 구현]
이 부분은 굳이 구현하는데 중요한 부분은 아니라 넘어가도 된다. 다만 조금 더 많은 기능을 원할 경우 추가해주면 좋은 메소드들이긴 하다. toArray는 사용자가 main 함수에서 특정 배열로 반환받고싶다거나 복사하고 싶을 때 Queue에 저장된 데이터들을 배열로 반환해주는 역할을 하기 위해 만들었다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 만드는 것이다.
마지막으로 sort()메소드는 말 그대로 정렬해주는 메소드다.
(참고로 이 구현은 필자가 전에 포스팅 했던 Singly LinkedList의 구현부랑 구조가 똑같다.)
1. toArray() 메소드
toArray()는 크게 두 가지가 있다.
하나는 아무런 인자 없이 현재 있는 큐의 요소들을 객체배열(Object[]) 로 반환해주는 Object[] toArray() 메소드가 있고,
다른 하나는 큐를 이미 생성 된 다른 배열에 복사해주고자 할 때 쓰는 T[] toArray(T[] a) 메소드가 있다.
즉 차이는 이런 것이다.
LinkedListQueue<Integer> listqueue = new LinkedListQueue<>();
// get LinkedListQueue to array (using toArray())
Object[] q1 = listqueue.toArray();
// get LinkedListQueue to array (using toArray(T[] a)
Integer[] q2 = new Integer[10];
q2 = listqueue.toArray(q2);
1번의 장점이라면 큐에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점이다.
2번의 장점이라면 객체 클래스로 상속관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다. 또한 큐에 원소 5개가 있고, q2 배열에 10개의 원소가 있다면 q2에 0~4 index에 원소가 복사되고, 그 외의 원소는 기존 q2배열에 초기화 되어있던 원소가 그대로 남는다.
두 메소드 모두 구현해보자면 다음과 같다.
public Object[] toArray() {
Object[] array = new Object[size];
int idx = 0;
for (Node<E> x = head; x != null; x = x.next) {
array[idx++] = (E) x.data;
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
// Array.newInstance(컴포넌트 타입, 생성할 크기)
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
// 얕은 복사를 위한 s 배열
Object[] result = a;
for (Node<E> x = head; x != null; x = x.next) {
result[i++] = x.data;
}
return a;
}
첫 번째 toArray()는 쉽게 구현 할 수 있다.
각 노드를 방문하면서 노드의 데이터들을 array 배열에 담고 반환하면 된다.
문제는 toArray(T[] a) 메소드다. ArrayQueue에서는 내부에서 데이터를 Object[] 배열에 담았기 때문에 데이터 복사가 쉬웠으나, LinkedListQueue는 '노드'라는 객체에 데이터를 담고있는 연결리스트이기 때문에 노드 자체가 Integer, String 처럼 래퍼클래스나, 사용자가 만든 클래스 같은 데이터를 갖을 수가 없다. 한 마디로 노드의 data 변수가 객체 타입 변수인 것이지 노드 자체가 변환하고자 하는 제네릭 타입을 갖지 못한다. 그래서 이전처럼 Arrays.copyOf() 메소드나 System.arraycopy를 쓰기 어렵다.
이럴 때 바로 쓸 수 있는 것이 lang.reflect 패키지에 있는 Array 클래스의 도움을 받을 수 있다. 이에 대한 API는 아래 링크로 남겨둘 것이니 참고해보시길 바란다.
docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/reflect/Array.html
Array (Java SE 11 & JDK 11 )
docs.oracle.com
여기서 우리가 사용 할 메소드는 이 것이다.
두 번째 T[] toArray(T[] a) 메소드를 보자.
이 부분은 제네릭 메소드로, 우리가 만들었던 LinkedListQueue의 E타입하고는 다른 제네릭이다. 예로들어 E Type이 Integer라고 가정하고, T타입은 Object 라고 해보자.
Object는 Integer보다 상위 타입으로, Object 안에 Integer 타입의 데이터를 담을 수도 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.
즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성하는 것이다. 하위 타입, 즉 축소할 경우 Array 클래스에서 예외를 던지기 때문에 이에 대한 별다른 예외를 처리해줄 필요 없다.
그리고 크게 두 가지 경우의 수가 있다.
첫 번째는 파라미터로 주어지는 배열 a가 현재 리스트의 요소보다 작은 경우와, 그 반대의 경우 이렇게 있다.
먼저 들어오는 배열(a)가 현재 리스트의 요소 개수(size)보다 작으면 size에 맞게 a의 공간을 재할당 하면서 리스트에 있던 모든 요소를 복사한다.
쉽게 이해해보면 LinkedListQueue의 요소(데이터)가 4개 {1, 2, 3, 4} 있다고 치자. 그리고 Object[] copy = new Object[1]라는 배열을 하나 만들었는데, 공간이 한 개 밖에 없다.
그러면 리스트의 요소 1개만 복사하는 것이 아니라 copy 배열의 사이즈가 1에서 4로 증가하여 copy배열에 {1, 2, 3, 4}가 모두 담기게 되는 것이다.
또한 a에 대한 타입을 알기 위해 먼저 getClass().getComponentType() 을 통해 객체가 어떤 유형의 배열인지를 파라미터를 넣고, 배열의 크기를 설정해준다.
그런 다음 a를 얕은 복사을 통한 Object[] 배열을 하나 만들어 해당 배열을 통해 데이터를 넣어준다음 a를 반환한다. 얕은 복사이기 때문에 s 배열에 담으면 자동으로 a배열에도 영향을 미치는 것을 활용한 방법이다.
조금 복잡해보일 수는 있으나, 최대한 이해할 수 있도록 주석을 달아놓았으니 참고해보고 이해가 안된다면 댓글은 남겨주시면 답변드리도록 하겠다.
2. clone() 메소드
만약 사용자가 사용하고 있던 Queue를 새로 하나 복제하고 싶을 때 쓰는 메소드다. 즉, 얕은 복사가 아닌 깊은 복사로 아예 다른 하나의 클론을 만드는 것이다.
단순히 = 연산자로 객체를 복사하게 되면 '주소'를 복사하는 것이기 때문에 복사한 객체에서 데이터를 조작할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(shallow copy)가 된다는 것이다.
LinkedListQueue<Integer> original = new LinkedListQueue<>();
original.offer(10); // original에 10추가
LinkedListQueue<Integer> copy = original;
copy.offer(20); // copy에 20추가
System.out.println("original LinkedListQueue");
int i = 0;
for(Object a : original.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\ncopy LinkedListQueue");
i = 0;
for(Object a : copy.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\noriginal LinkedListQueue reference : " + original);
System.out.println("copy LinkedListQueue reference : " + copy);
[결과]
보다시피 객체의 주소가 복사되는 것이기 때문에 주소와 데이터 모두 같아져버리는 문제가 발생한다.
이러한 것을 방지하기 위해서 깊은 복사를 하는데, 이 때 필요한 것이 바로 clone()이다. Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 구현해야 할 경우 반드시 Cloneable 인터페이스를 implement 해야한다.
즉, public class LinkedListQueue<E> implements Queue<E> 에 Cloneable도 추가해주어야 한다.
그리고나서 clone()을 구현하면 되는데, 다음과 같이 재정의를 하면 된다.
@Override
public Object clone() {
// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다.
try {
@SuppressWarnings("unchecked")
LinkedListQueue<E> clone = (LinkedListQueue<E>) super.clone(); // 새로운 큐 객체 생성
clone.head = null;
clone.tail = null;
clone.size = 0;
// 내부까지 복사되는 것이 아니기 때문에 내부 데이터들을 모두 복사해준다.
for(Node<E> x = head; x != null; x = x.next) {
clone.offer(x.data);
}
return clone;
} catch (CloneNotSupportedException e) {
throw new Error(e); // 예외처리는 여러분들이 자유롭게 구성하면 된다.
}
}
조금 어려워 보일 수 있는데, 이해하지 못해도 된다. 자료구조에서 중요한 부분은 아니니...
설명을 덧붙이자면, super.clone() 자체가 생성자 비슷한 역할이고 shallow copy를 통해 사실상 new LinkedListQueue() 를 호출하는 격이라 제대로 완벽하게 복제하려면 clone한 큐의 array 또한 새로 생성해서 해당 배열에 copy를 해주어야 한다.
위와같이 만들고 나서 clone()한 것 까지 포함해서 테스트를 해보자.
LinkedListQueue<Integer> original = new LinkedListQueue<>();
original.offer(10); // original에 10추가
LinkedListQueue<Integer> copy = original;
LinkedListQueue<Integer> clone = (LinkedListQueue<Integer>) original.clone();
copy.offer(20); // copy에 20추가
clone.offer(30); // clone에 30추가
System.out.println("original LinkedListQueue");
int i = 0;
for (Object a : original.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\ncopy LinkedListQueue");
i = 0;
for (Object a : copy.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\nclone LinkedListQueue");
i = 0;
for (Object a : clone.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\noriginal LinkedListQueue reference : " + original);
System.out.println("copy LinkedListQueue reference : " + copy);
System.out.println("clone LinkedListQueue reference : " + clone);
[결과]
결과적으로 clone으로 복사한 ArrayQueue는 원본 ArrayQueue에 영향을 주지 않는다.
3. sort() 메소드
LinkedListQueue의 경우는 Node 객체들이 연결된 형태이기 때문에 정렬을 이용하고자 한다면 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", "rawtypes" })
public void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
int i = 0;
// 정렬 된 a 배열을 큐로 복사한다.
for (Node<E> x = head; x != null; x = x.next, i++) {
x.data = (E) a[i];
}
}
위 코드에서 보듯이 어떠한 형태로든 결국 sort((Comparator<? super E> c) 로 간다. (참고로 상속관계이면서 부모 클래스에서 정렬 방식을 따르는 경우도 생각하여 <? super E>로 하였다. 이러한 경우를 고려하지 않는다면 Comparator<E>로 해주어도 종속관계 영향을 안받는 객체의 경우는 괜찮다.)
그런다음 Object[] 배열로 우리가 만들었던 toArray()를 통해 만들어 주어 Arrays.sort() 메소드를 통해 정렬해준다.
실제로도 Collections.sort() 또한 Arrays.sort()로 보낸다. 잠깐 내부 구현을 들여다보면 이렇다.
[Collections.sort()] - Comparator() 파라미터가 없는 경우
[Collections.sort()] - Comparator() 파라미터가 주어지는 경우
그리고 두 메소드 모두 List 인터페이스의 default 메소드인 sort() 메소드로 보낸다. 해당 내부 구현은 이렇다.
[List.sort()]
다만 필자가 올린 코드와 차이가 있다면, Iterator을 구현하지 않았기 때문에 대신 반복문을 통해 현재 클래스의 노드 데이터를 직접 바꾼다는 것 뿐이다.
그럼 한 번 테스트를 해보자.
Student 클래스를 통해 이름과 성적을 입력받고, 이를 정렬하는 테스트를 해보도록 한다.
<Student 클래스가 Comparable을 구현하지 않았을 경우>
[TEST.java]
public class TEST {
public static void main(String[] args) {
LinkedListQueue<Student> q = new LinkedListQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort();
for(Object a : q.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) {
LinkedListQueue<Student> q = new LinkedListQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort(customComp);
for(Object a : q.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) {
LinkedListQueue<Student> q = new LinkedListQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort(); // Comparator 인자가 필요하지 않음
for(Object a : q.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() 을 구현한 내용을 찾아 작성한대로 정렬을 해준다.
[결과]
참고로 ArrayList 구현 할 때에도 sort() 메소드를 구현하고 싶다면 위와 같은 방법으로 구현하면 된다.
[toArray, clone, sort 메소드 묶어보기]
public Object[] toArray() {
Object[] array = new Object[size];
int idx = 0;
for (Node<E> x = head; x != null; x = x.next) {
array[idx++] = (E) x.data;
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
Object[] s = a;
for (Node<E> x = head; x != null; x = x.next)
s[i++] = x.data;
return a;
}
@Override
public Object clone() {
try {
@SuppressWarnings("unchecked")
LinkedListQueue<E> clone = (LinkedListQueue<E>) super.clone();
clone.head = null;
clone.tail = null;
clone.size = 0;
for (Node<E> x = head; x != null; x = x.next) {
clone.offer(x.data);
}
return clone;
} catch (CloneNotSupportedException e) {
throw new Error(e);
}
}
public void sort() {
sort(null);
}
@SuppressWarnings({ "unchecked", "rawtypes" })
public void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
int i = 0;
for (Node<E> x = head; x != null; x = x.next, i++) {
x.data = (E) a[i];
}
}
- 전체 코드
package _05_LinkedListQueue;
import Interface_form.Queue;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
*
* @param <E> the type of elements in this Queue
*
* @author st-lab.tistory.com
* @version 1.0
* @see Queue
*
*/
public class LinkedListQueue<E> implements Queue<E>, Cloneable {
private Node<E> head;
private Node<E> tail;
private int size = 0;
public LinkedListQueue() {
this.head = null;
this.tail = null;
}
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<E>(value);
// 비어있을 경우
if(size == 0) {
head = newNode;
}
// 그 외의 경우 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 한다.
else {
tail.next = newNode;
}
/**
* tail이 가리키는 노드를 새 노드로 바꿔준다.
*/
tail = newNode;
size++;
return true;
}
@Override
public E poll() {
// 삭제할 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
// 삭제될 요소의 데이터를 반환하기 위한 임시 변수
E element = head.data;
// head 노드의 다음노드
Node<E> nextNode = head.next;
// head의 모든 데이터들을 삭제
head.data = null;
head.next = null;
// head 가 가리키는 노드를 삭제된 head노드의 다음노드를 가리키도록 변경
head = nextNode;
size--;
return element;
}
public E remove() {
E element = poll();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
@Override
public E peek() {
// 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
return head.data;
}
public E element() {
E element = peek();
if(element == null) {
throw new NoSuchElementException();
}
return element;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
/**
* head 데이터부터 x가 null 이 될 때까지 value랑 x의 데이터(x.data)랑
* 같은지를 비교하고 같을 경우 true를 반환한다.
*/
for(Node<E> x = head; x != null; x = x.next) {
if(value.equals(x.data)) {
return true;
}
}
return false;
}
public void clear() {
for(Node<E> x = head; x != null; ) {
Node<E> next = x.next;
x.data = null;
x.next = null;
x = next;
}
size = 0;
head = tail = null;
}
public Object[] toArray() {
Object[] array = new Object[size];
int idx = 0;
for (Node<E> x = head; x != null; x = x.next) {
array[idx++] = (E) x.data;
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
// Array.newInstance(컴포넌트 타입, 생성할 크기)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
// 얕은 복사를 위한 s 배열
Object[] s = a;
for (Node<E> x = head; x != null; x = x.next)
s[i++] = x.data;
return a;
}
@Override
public Object clone() {
// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다.
try {
@SuppressWarnings("unchecked")
LinkedListQueue<E> clone = (LinkedListQueue<E>) super.clone(); // 새로운 큐 객체 생성
clone.head = null;
clone.tail = null;
clone.size = 0;
// 내부까지 복사되는 것이 아니기 때문에 내부 데이터들을 모두 복사해준다.
for(Node<E> x = head; x != null; x = x.next) {
clone.offer(x.data);
}
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", "rawtypes" })
public void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
int i = 0;
// 정렬 된 a 배열을 큐로 복사한다.
for (Node<E> x = head; x != null; x = x.next, i++) {
x.data = (E) a[i];
}
}
}
위 코드는 아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.
[소스코드 모아보기]
kdgyun/Data_Structure
Contribute to kdgyun/Data_Structure development by creating an account on GitHub.
github.com
- 정리
LinkedListQueue에 대한 기본적인 메소드와 더불어 추가적인 메소드들을 구현해보았다.
객체를 잘 다룰 줄 안다면 Queue는 자바로 구현할 경우 LinkedList로 구현하는게 훨씬 편하다는 것을 느끼실 수 있을 것이다. 만약에 기존에 LinkedList를 구현해놓았다면 이를 상속받아 LinkedList의 메소드를 사용해도 된다.
다음에 구현 할 것은 Deque다. 흔히 '덱' 이라고 부르는데, Double Ended Queue의 줄임말이다. 단일 연결리스트와 이중 연결리스트가 있듯, 큐도 단방향 큐와 양방향 큐가 있는데 이 양방향 큐를 덱이라고 한다. 이 부분은 다음 포스팅에서 자세히 다루도록 하자.
일단 최대한 이해하기 쉬우면서 실제 쓰이는 용도와 비슷하게 구현하려고 노력했는데 아무래도 자바만 배웠다가 자료구조로 넘어오면 처음에는 다들 어려우실 것 같아 조금 걱정이 되긴 한다만.. 혹여 어렵거나 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.
'자료구조 > Java' 카테고리의 다른 글
| 자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기 (6) | 2020.12.17 |
|---|---|
| 자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기 (6) | 2020.12.12 |
| 자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기 (27) | 2020.12.07 |
| 자바 [JAVA] - Queue Interface (큐 인터페이스) (2) | 2020.12.01 |
| 자바 [JAVA] - Stack (스택) 구현하기 (20) | 2020.11.20 |