20180328 Queue : Data Structure

개요

FIFO (First In First Out) 의 구조를 가진다. 스택과 더불어서 유명한 자료구조 중 하나이다. 일반적으로 마트의 선입선출을 생각하면 된다. 먼저 들어온 물품은 유통기한 때문에 먼저 빠져나가는 형태로 마트의 물품 진열 또한 FIFO 구조 즉 큐 자료구조를 이용하고 있는 것이다.

• add

• offer

• remove

• poll

• element

• peek

자바 jdk 를 살펴보면, 큐는 인터페이스로 만들어졌다. 따라서 큐를 구현하기 위해서는 실체 구현체인 LinkedList 로 만들어야 한다.

LinkedList 의 내부에는 아래와 같이 필드들이 선언되어 있다.

• int size

• Node<E> first

• Node<E> last

그리고 Node 클래스는 LinkedList 클래스 내부에 스태틱으로 존재한다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
 
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

- Integer Type 으로 Queue 인터페이스 구현체 생성

Queue<Integer> Queue = new LinkedList<Integer>();

- LinkedList Class 의 add() 메소드

public void add(E e) {
    checkForComodification();
    lastReturned = null;
    if (next == null)
        linkLast(e);
    else
        linkBefore(e, next);
    nextIndex++;
    expectedModCount++;
}

- LinkedList Class 의 linkLast() 메소드

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++;
    modCount++;
}

기본적으로 스택의 경우에는 따로 resize() 를 구현해서 해당 내부 필드의 배열 값을 늘리지만 큐는 내부적으로 연결리스트 클래스의 내용을 가지고 있어서 따로 배열 값을 늘리는 것이 아닌 계속해서 해당되는 연결리스트의 주소값을 가지고 있고 그에 따라 움직이고 있다.

clear() 메소드는 연결리스트의 내용 값들을 null 로 바꿔주어 GC의 처리를 받도록 구현되어 있으며 peek() 메소드는 단순 연결리스트의 요소 값을 삭제하지 않은 채 해당 값을 조회하기 위해 해당 헤드 연결리스트에서 첫번째 연결리스트 값을 받아오는 형태로 되어있다.

/**
LinkedList Class 
**/
 
// peek() 메소드
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
 
 
// clear() 메소드
/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

아래는 직접 구현해 본 Queue 이다.

class Queue{
    Object[]array;
    int back;
    int front;
    int elementCount;
    int capacity;
    
    public Queue(){
        this(10);
    }
    
    public Queue(int size){
        this.array = new Object[size];
        
        for(int i = 0; i < array.length; i++)
            array[i] = new Object();
        
        this.capacity = size;
        this.back = 0;
        this.front = 0;
    }
    
    public void push(Object value){
        
        if(back >= capacity){
            // resize
            reSize(capacity << 1);
        }
        
        array[back++] = value;
        elementCount += 1;
    }
    
    public Object pop(){
        if(elementCount <= 0){
            // null
            return -1;
        }
        
        elementCount -= 1;
        Object value = array[front++];
        array[front-1] = null;
        return value;
    }
    
    public Object size(){
        return elementCount;
    }
    
    public Object empty(){
        // 개수가 없는 경우
        if((int)size() <= 0)
            return 1;
        
        return 0;
    }
    
    // 첫번째 요소 값 획득
    public Object front(){
        if((int)empty() == 0)
            return array[(front)];
        
        return -1;
    }
    
    // 마지막 요소 값 획
    public Object back(){
        if((int)empty() == 0)
            return array[(back-1)];
        
        return -1;
    }
    
    // 사이즈 증가
    public void reSize(int newCapacity){
        array = Arrays.copyOf(array, newCapacity);
        capacity = newCapacity;
    }
}

백준 문제

[ 큐 ]