자바 큐 인덱스 - jaba kyu indegseu

자바(Java)로 구현한 큐(Queue) 예제

큐(Queue) 컨셉

큐(Queue)란 무었인가?

큐는 직선형 자료 구조로써, 같은 타입의 데이터를 "하나 다음 하나" 라는 컨셉으로 순차적으로 저장하는 자료형이다. 스택(Stack)과는 달리, 큐(Queue)는 구조의 양 끝 모두에 접근이 가능하다. 맥도날드나 카페에서 줄을 서서 기다리는 걸 머리속에 그려보자. 줄은 새로운 사람이 끝에 섬으로써 길어지고, 가장 앞에선 사람이 주문을 함으로써 짧아진다. 이게 바로 큐(Queue)이다. 이렇한 이유로, 큐(Queue)는 보통 "FIFO(First In First Out) Structure"(먼져 들어간게 먼져 나오는 구조)라 영어권에서 표현된다.

큐(Queue) 실제로 어디에 쓰일까?

• Operating System
• 시스템 스케줄링, 인풋 버퍼(Input Buffer), 그리고 프린터 작업 관리 등

큐(Queue)는 어떻게 구현될까?

큐(Queue)는 스택(Stack)처럼 추상 자료형(Abstract Data Type)이므로, 다양한 방법으로 구현될 수 있다. 자바(Java)로 구현할 때 가장 많이 쓰이는 두가지 방법은 배열(Array)와 링크드 리스트(Linked List)를 이용하는 것이다. 큐(Queue)는 몇가지 필수적인 메소드들을 가지고 있는데 그것들은 아래와 같다

• Enqueue(삽입)
• 큐(Queue)의 끝에 새로운 자료를 삽입한다
• 이 작업은 O(1)의 복잡도를 가진다
• Dequeue(제거)
• 큐(Queue)의 가장 첫 위치에 존재하는 자료를 반환하고 제거한다.
• 이 작업은 O(1)의 복잡도를 가진다
• Peek
• 큐(Queue)의 처음에 존재하는 자료를 반환한다
• Dequeue 메소드와는 달리, 처음에 존재하는 자료를 제거하지는 않는다.
• isEmpty
• 큐(Queue) 가 Empty 상태인지 확인한다.
• clear
• 큐(Queue) 내부의 모든 자료들을 삭제한다

아래는 자바(Java) 배열(Array)로 구현한 큐(Queue)의 예제이다

public class QueueWithArray {
 private Object[] queue;
 int first, last, size;
  public QueueWithArray(int size) {
  queue = new Object[size];// 주어진 인터져 size 값으로 size의 크기를 가진 오브젝트 어레이를 생성한다.
  first = last = -1;
  // 우선 아무것도 없는 배열에서, 우리의 마지막, 첫번째 데이터를 가리키는 first, last 인스턴스는 -1인덱스를 가리킨다.       
  this.size = size;// clear 메소드를 위해 사이즈 값을 저장해두자.
 }

 public boolean isEmpty() {
  return first == -1;
  // 만약 first 포인터 인스턴스가 -1 의 인덱스를 가리킨다면 그건 큐(Queue)가 empty 상태라는 뜻이다
 }

 public void clear() {
  queue = new Object[size]; // 새로운 배열(Array)를 생성하면서 원래 큐를 지워버리자
  first = last = -1;// 포인터 인스턴스를 리셋해준다.
 }

 public boolean isFull() {
   // 큐(Queue)가 꽉 찾는지를 확인한다.
   if ((first == 0 && last == size - 1) || first == last + 1) {
   // first 포인터가 인덱스 0, last 포인터가 배열의 마지막 인덱스(size - 1)를 가리키거나
   // first 포인터가 가리키는 인덱스가 last 포인터가 가리키는 인덱스보다 1이 크다면
   // 이는 큐(Queue)에 쓰는 배열이 꽉 찾음을 의미한다.
   return true;
  } else {
   return false;
  }

 }

 public void enQueue(Object e) {
  if (isFull()) {
   throw new FullQueueException();// 큐가 꽉 찾다면 Exception을 던져주자
  } else {
   //아니라면 삽입을 시작한다.
   if (first == -1) {// 만약 first 인스턴스가 -1값을 가지고 있다면, 이는 큐가 empty 상태인걸 의미한다.
    first = last = 0;// 그렇니 first 와 last 값을 0으로 바꿔주자
   } else {
    last = (last + 1) % size;
    // 이 메소드에서 새로운 object e 는 어레이의 가장 끝 인덱스의 위치로 삽입된다.
    // (last + 1) % size 는 배열(Array)의 중간에 last 인덱스가 위치할 경우를 생각한다.
   }
   queue[last] = e;
  }
 }

 public Object dequeue() {
  if (isEmpty()) {
   // 큐(Queue)가 Empty 인지 확인한다
   throw new EmptyQueueException();
  } else {
   Object toReturn = queue[first];
   if (first == last) {
    // first 와 last 가 같은 인덱스를 가리킨다면
    // 이는 큐(Queue)에 데이터가 1개밖에 없음을 의미한다.
    // 그렇니 그냥 포인터를 리셋해주자
    first = last = -1;
   } else {
    first = (first + 1) % size;
    // 만약 first 포인터가 배열(Array)의 마지막 인덱스를 가리키고 있다면
     // first + 1 은 ArrayOutOfBound Exception 을 낳을 것이다
     // first = (first + 1) % size; 은 그럴경우에는 0 이란 수가 계산되어
     // 옭바른 인덱스를 계산 할 수 있다.
   }
   return toReturn;
  }
 }

 public Object peek() {
  if (isEmpty()) {
   throw new EmptyQueueException();
  } else {
   return queue[first];
  }
 }
}

아래는 자바(Java) Linked List 로 구현한 큐(Queue)의 예제이다

import java.util.LinkedList;
public class QueueWithLinkedList {
 private LinkedList queue;

 public QueueWithLinkedList() {
  queue = new LinkedList();
 }

 public boolean isEmpty() {
  return queue.isEmpty();
 }

 public void enQueue(Object e) {
  queue.addLast(e);
 }

 public Object deQueue() {
  return queue.removeFirst();
 }

 public Object peek() {
  return queue.getFirst();
 }
}

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

First In First Out

선입 선출

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

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

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

구현

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

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

 근데 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 인터페이스를 그려보면

의 형태로 구현되어있다. (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 파일을 참고하여 만들었지만 혹시 모를 이탈자나 잘못된 부분은 댓글로 피드백 부탁드립니다.