자료구조

[JAVA] Queue 직접 구현하기

최진영 2021. 4. 20. 13:47

Queue 란

 Stack과는 다르게 데이터가 들어간 순서대로 나오는 즉, FIFO(First In Last Out) 선입선출의 자료구조이다.

First In First Out

선입 선출

먼저 들어간 것이 먼저 나온다.

 데이터를 추출할 때 Stack은 마지막 데이터를 꺼내는 것과 달리 가장 앞에 있는 index를 꺼낸다.


Queue의 기본 구조이다.

 먼저 들어온(push)된 값을 먼저 보낸다(pop)가 기본 베이스로 깔려서 다른 PrioritoyQueue나 Deque로 개념을 연장할 수 있다. Queue는 사실 먼저 들어온게 먼저 나가는 대기열로 생각하면 되고 대학생때 고통받는 수강신청에서 트래픽 대기가 보통 Queue 형태로 구현되어있다.

 

구현

 사실 Queue도 또한 Collection 프레임워크에 포함되어있고, 물론 Stack과 항상 따라오는 개념이긴하다. 근데 포함되어있는 구조가 좀 다르다.

 Stack은 이전에 List 인터페이스에 포함되며, 이를 구현할 때 굳이 다 구현하지 않고 ArrayList(Vector)를 상속받아서 이를 기반으로 Stack 자료구조를 만들었다. 근데 Queue의 경우 List 인터페이스의 자료구조를 사용해서 구현을 하긴 하지만 엄밀히 따지자면 List 인터페이스에 포함되어있진 않다.

Collection에 상속된 List와 별개의 인터페이스이다. (JDK1.5에 업데이트되었다.)

 

 근데 Queue를 주로 사용해봤다면 Queue를 사용할 때 다음처럼 많이 사용했을 것이다.

Queue<E> queue = new LinkedList<E>();

 ?? LinkedList를 받아서 사용했는데 왜 Queue를 굳이 List 인터페이스 안에 포함해서 개발하지 않았을까? 공부를 하면서 생각해보건데 List 인터페이스가 존재하는 목적과 Queue의 목적이 다르기 때문이다.

 List 인터페이스에 존재하는 ArrayList와 LinkedList는 동적인 Array를 구현한다. 하지만 Queue는 물론 그자체로 동적인 배열을 사용하는 자료구조이긴 하지만 선입 선출이라는 별개의 기능을 띄는 인터페이스다. 따라서 동적 Array로써 List 인터페이스를 구성하고, 선입 선출로써 Queue 인터페이스를 구성하였기 때문이라고 생각한다.

 

 그럼 왜 LinkedList를 주로 사용했을까? ArrayList와 LinkedList의 성능차이는 "조회"를 많이 쓰냐, "삽입삭제"를 많이 쓰냐에 따라서 달려있다.

 ArrayList는 배열을 동적으로 사용하여 구현한 List이기 때문에 단순조회는 속도가 빠르지만, 삽입삭제는 배열의 크기를 조정해야하므로 느리다. 하지만 LinkedList는 Node들을 연결해서 구현한 List이기 때문에 삽입삭제는 빠르지만 조회의 경우 모든 Node를 일일히 탐색해야할 수 있어 느리다.

 Queue 자료구조는 삽입삭제가 많이 일어나는 자료구조이기 때문에 결국 LinkedList를 사용하는 것이다.

 

 따라서 우리는 Queue를 따로 구현하지는 않고 Queue의 필요한 기능으로 만든 인터페이스를 만들고, LinkedList를 다형성으로 받아서 사용할 것이다. 따라서 일단 Queue 인터페이스를 구성하고, LinkedList에는 구현하지 않았던 메소드들을 추가로 구현해줄 것이다.

 둘의 연결은 가장 마지막에 연결할 것이다.

 

구현 목록은 다음과 같다.

  • offer()
  • poll()
  • peek()

(코드 가독성을 위해 javadoc는 지우고 코드를 설명했다. 전체코드는 github.com/jinyoungchoi95/DataStructure/blob/master/src/DataStructure/Queue/Queue.java에서 확인할 수 있다.)

 

1. default 세팅

package DataStructure;

public interface Queue<E> {

 인터페이스로 Queue를 구현한다.

 

2. offer()

boolean offer(E e);

 Queue에 특정 요소를 추가하는 메소드이다.

 Queue는 선입선출 구조로 먼저 들어간 값이 먼저 나오는 구조라고 이야기했었다. 그럼 이걸 배열이라고 생각해보자.


 Queue의 선입선출방식으로 값을 넣고 뺄 때 index가 0인 값을 뺄 것이고 List의 가장 마지막에 데이터를 넣으면 선입선출의 구조를 만들 수 있다.

 따라서 offer() 메소드는 요소가 들어올 때마다 List의 마지막에 해당 요소를 더하는 구조가 되어야한다. 이 메소드는 LinkedList에는 없기 때문에 직접 추가해주도록 한다.

 

 LinkedList에는 offer() 메소드가 없지만, add()메소드가 있긴 하다.

@Override
public boolean add(E e) {
    linkLast(e);
    return true;
}

private void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
}

add() 메소드 또한 Queue를 의도하고 만들진 않았지만 List의 가장 마지막 Node에 element를 추가하는 메소드이기 때문에 이를 재사용해서 offer()메소드를 정의한다.

 

public boolean offer(E e) {
    return add(e);
}

 

3. peek()

E peek();

 Queue의 가장 최상단 요소를 반환하는 메소드이다.

 Queue의 가장 첫 값은 뭘까? 선입 선출, 먼저 들어간 것이 먼저 나온다. 즉, index가 0인 값이다. 따라서 이를 고려하여 peek() 메소드를 LinkedList에 구현한다.

 

public E peek() {
    Node<E> node = first;
    return node == null ? null : node.item;
}

 LinkedList에서 가장 첫 요소는 first node에 저장해두었다. 따라서 Node 객체에 first를 먼저 받아온다. 이후 만약에 사용중인 LinkedList가 비어있다면 first node는 당연히 null일 것이므로 first node가 비어있다면 null을, 아니라면 first node의 값을 반환해준다.

 

4. poll()

E poll();

 Queue의 가장 최상단 요소를 반환하면서 제거하는 메소드이다.

 최상단 요소라하면 List의 가장 첫값을 이야기하는 것으로 LinkedList에는 가장 첫 index를 제거하는 removeFirst() 메소드가 존재한다.

public E removeFirst() {
    if (first == null) {
        throw new NoSuchElementException();
    }
    return unlinkFirst();
}

private E unlinkFirst() {
    final E item = first.item;
    final Node<E> next = first.next;

    first = next;
    if (first == null) {
        last = null;
    } else {
        first.prev = null;
    }
    size--;
    return item;
}

 어짜피 first값이 null인 것은 poll()에서 검증해서 Exception이 아닌 null을 내보낼 것이기 때문에 unlinkFirst()메소드를 가져와서 제거하는 용도로 사용한다.

 

public E poll() {
    Node<E> node = first;
    return node == null ? null : unlinkFirst();
}

 LinkedList의 first node를 가져와서 LinkedList가 비어서 first가 null이라면 null을, 존재한다면 unlinkFirst() 메소드를 실행해 first node를 제거하고 나온 first node의 값을 반환한다.

 

 

Queue LinkedList 임시 상속

 Queue는 Collection 프레임워크에서 나온 List와는 별개의 인터페이스지만 우리는 선입선출 Queue라는 자료구조를 동적List인 LinkedList를 가지고 만들었다. 그럼 처음 이야기했던 실제로 Queue를 다형성했을 때 써질까?

캐스팅, 타입 프로모션 둘다 안된다.

 컴파일 에러가 난다. Queue와 LinkedList와의 관계가 지금 아무것도 없기 때문에 casting도 안된다. 그럼 일단 이 둘의 관계를 맺어줘야하는데 어떻게 상속을 해서 사용하도록 할까?

 Collection 프레임워크에서 List 인터페이스와 Queue 인터페이스를 그려보면

Collection 프레임워크 구조 ( Set 인터페이스는 제외하였다)

의 형태로 구현되어있다. (Set 인터페이스는 지금 관계없으므로 포함하지 않았다.)

 위에서 말했던대로 List는 동적 Array로써 그 기능을 담당하고 그 중 "삽입삭제"가 빈번한 Queue가 사용하기 적합한 LinkedList를 사용하기로 하였기 때문에 LinkedList를 Queue 인터페이스에 상속하여도 지금 당장 쓰는데에는 문제가 없다.

 다만, 바로 다음 글에서 Deque와 PriorityQueue 또한 구현을 할 것이기 때문에 미리 Deque를 생성하고 이를 LinkedList가 상속받으며 Deque 또한 Queue를 상속받게끔하려고 한다.

public interface Queue<E>
public interface Deque<E> extends Queue<E>
public class LinkedList<E> extends List<E>, Queue<E>

가 될 것이다.

import DataStructure.Queue;
import DataStructure.LinkedList;

public class Application {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        System.out.println(queue.poll());
        System.out.println(queue.peek());
    }
}
//    [출력]
//    1
//    2

 잘 동작하는 것을 확인할 수 있다.

 

 

앞에서도 말했지만 전체 코드는 깃허브에 전부 저장해두었습니다.

최대한 공식문서와 실제 class 파일을 참고하여 만들었지만 혹시 모를 이탈자나 잘못된 부분은 댓글로 피드백 부탁드립니다.

저작자표시