JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

1. Queue 란

---

• 먼저 들어오는 것이 먼저 처리되는 구조를 가진 자료구조(FIFO) ex) 줄 서기
• 데이터가 삽입되는 쪽을 rear, 반대로 데이터가 삭제되는 front
• 데이터 추가/삭제는 O(1), 탐색은 O(n)

 

 

---

 

2. Java에서는 어떻게 구현되어 있을까?

---

LinkedList로 구현하고 있고 내부는 node의 연결로 구성되어 있다. (LinkedList를 공부하면서 이 개념 그대로 Queue로 쓰이겠는데? 라고 생각했는데 역시나 그랬다.) 당연히 LinkedList의 성능을 보여준다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;

...

}

//Queue 선언
Queue<Integer> queue = new LinkedList<>();

 

---

 

3. List에는 없지만 Queue(LinkedList)에는 있는 메서드(offer, poll , peek)

---

자바 API에 보면 LinkedList는 ArrayList와 다르게 Deque(Queue)를 상속한다.

/*
 * @author  Josh Bloch
 * @see     List
 * @see     ArrayList
 * @since 1.2
 * @param <E> the type of elements held in this collection
 */

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, **Deque<E>**, Cloneable, java.io.Serializable{

	...

}

Queue에 있는 데이터 추가 삭제 확인하는 메서드가 각각 2개씩 있다.

자바 컬랙션 프레임워크의 Queue 인터페이스에서 각기능을 하는 메서드의 차이를 잘 요약하였다.

Summary of Queue methods

Throws exception  / Returns special value
-----------------------------------------
Insert | add(e)   / offer(e)         
Remove | remove() / poll()
Examine| element()/ peek()

add, remove, element는 해당 매서드에서 오류를 발생할 수 있고

offer, poll, peek는 값이 없을 땐 null, 없을 땐 해당 값을 반환한다는 것이다.

구현체인 LinkedList의 내부 코드를 보며 무슨 말인지 하나씩 살펴보자.

 

3.1 offer와 add

반환 타입이 boolean 인 offer와 add는 내부적으로 동일하다.

add는 index를 설정해줄 수 있고 이 과정에서 에러가 발생할 수 있다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{

	...

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

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

	public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
  }

	private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

	...

}

 

3.2 poll와 remove

poll은 값이 없다면 null

remove는 값이 없다면 NoSuchElementException 예외처리

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{

	...

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

	public E remove() {
    return removeFirst();
  }

	public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
  }

	...

}

 

3.3 peek와 element

peek는 값이 없다면 null

element는 값이 없다면 NoSuchElementException 예외처리

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable	...

	...

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

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

	public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
  }

	...

}

 

 

---

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3) 

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)