[자료구조] 큐(Queue)

위키백과에 따르면 Queue를 다음과같이 정의하고 있다.

Queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.

선형구조에서 한쪽의 끝에서는 데이터가 추가되어지고(Enqueue) 나머지 한쪽의 끝에서는 데이터가 제거된다(Dequeue). 편의상 데이터가 추가되어지는 곳을 큐의 back, tail, 또는 rear라 부르고 데이터가 제거되어진는 곳을 head 또는 front라고 불린다.

---

특징

기본 특징

• 선형 자료구조
• FIFO(First-In-First-Out)
• offer()는 rear에서 poll()은 front에서 이루어진다.

Overflow

Array로 큐를 선형으로 구현하였을때만 발생한다. 배열의 제한된 크기가 꽉차서 더이상 offer를 할 수 없을때 offer를 하게되면 발생하는 에러다. 이를 해결하기 위해서 1차원적으로는 front에서 pop을 한 뒤, offer 하는 방법과 큐의 용량을 늘리는 방법이 있다. 이외에 원형큐 구현 또는 이중 연결리스트를 이용해서 구현할 경우 overflow error를 개선할 수 있다.

Underflow

큐가 비어있을때 isEmpty()를 호출하거나 poll()을 호출하게되면 발생하는 에러다. 근본적인 원인을 해결할수는 없고 비어있는 큐인지 확인하는 방법으로 방지할수는 있다.

복잡도

자료구조	공간복잡도
스택	O(n)
큐	O(n)

기능	시간복잡도
offer()	O(1)
poll()	O(1)
peek()	O(1)
isEmpty()	O(1)
size()	O(1)
search()	O(n)

poll() 같은 경우, 선형 array로 구현한다면 시간복잡도가 O(n)이 나온다. 일반적으로 배열은 가장 뒤에서부터 접근이 가능하기 때문이다.

구현

선형큐

structure LinearQueue:
    maxsize : integer
    firstIndex : integer
    lastIndex : integer
    items : array of item

• 큐의 용량 maxsize
• 원소의 가장 앞 인덱스 정보 firstIndex
• 원소의 가장 뒤 인덱스 정보 lastIndex
• 원소들의 데이터 정보를 가지는 items

인덱스 두개를 사용하는 이유는, 배열로 구현할때 front의 데이터를 poll()하고 firstIndex를 사용하지 않는다면 그 다음부터는 poll()시 매번 front index를 탐색하거나 원소를 한자리씩 매번 당겨야하기 때문이다.

/**
 * 
 * @author junho
 *
 * @param <T>
 * 선형 큐 구현하기
 */
@SuppressWarnings("unchecked")
public class LinearQueue<T> implements IQueue<T>{
	
	private static final int maxSize = 1024;
	private int lastIndex = 0;
	private int firstIndex = 0;
	
	private T[] array = (T[]) new Object[maxSize];

	@Override
	public boolean offer(T value) {
		// overflow
		int size = size();
        if (size >= array.length) {
        	return false;
        }

        array[lastIndex] = value;
        lastIndex++;
        return true;
	}

	@Override
	public T poll() {
		// underflow
		if (isEmpty())
			return null;

		T t = array[firstIndex];
		array[firstIndex] = null;
		firstIndex++;

		size = lastIndex - firstIndex;
		if (size <= 0) {
			clear();
		}

		return t;
	}

	@Override
	public T peek() {
        if (size >= array.length) {
        	return null;
        }
		return array[firstIndex];
	}

	@Override
	public void clear() {
		firstIndex = 0;
		lastIndex = 0;
	}

	@Override
	public boolean isEmpty() {
		if(lastIndex - firstIndex == 0) return true;
		return false;
	}

	@Override
	public int size() {
		return lastIndex - firstIndex;
	}

}

원형큐

선형 큐에서의 단점은 메모리가 남아있어도 overflow error가 발생할수있다는 점이다. 따라서 물리적으로는 선형이나 논리적으로 배열의 처음과 끝을 연결되어 있게 구현하여 해결할 수있다.

structure CircularQueue:
    maxsize : integer
    firstIndex : integer
    lastIndex : integer
    items : array of item

• 큐의 용량 maxsize
• 원소의 가장 앞 인덱스 정보 firstIndex
• 원소의 가장 뒤 인덱스 정보 lastIndex
• 원소들의 데이터 정보를 가지는 items

앞과 뒤가 논리적으로만 이어져있기때문에 물리적인 구조는 동일하다고 본다. 인덱스를 조정하기위해서는 나머지 연산을 이용한다. (lastIndex + 1) % maxSize를 이용하여 관리할 수 있다.

/**
 * 
 * @author junho
 *
 * @param <T>
 * 원형 큐 구현하기
 */
@SuppressWarnings("unchecked")
public class CircularQueue<T> implements IQueue<T> {
	
	private static final int maxSize = 1024;
	private int lastIndex = 0;
	private int firstIndex = 0;
	
	private T[] array = (T[]) new Object[maxSize];

	@Override
	public boolean offer(T value) {
		// 원소가 모두 찼을때 overflow
		if(size() == maxSize) {
			return false;
		}
		else {
			array[lastIndex % array.length] = value;
			lastIndex = (lastIndex + 1) % maxSize;
		}

		if(size() == 0) {
			clear();
		}
		return true;
	}

	@Override
	public T poll() {
		// underflow
		if (isEmpty())
			return null;

		T t = array[firstIndex % array.length];
		array[firstIndex % array.length] = null;
		firstIndex = (firstIndex + 1) % maxSize;

		if (size() == 0) {
			clear();
		}

		return t;
	}

	@Override
	public T peek() {
		return array[firstIndex % array.length];
	}

	@Override
	public void clear() {
		firstIndex = 0;
		lastIndex = 0;
	}

	@Override
	public boolean isEmpty() {
		if(lastIndex - firstIndex == 0) return true;
		return false;
	}

	@Override
	public int size() {
		return Math.abs(firstIndex - lastIndex);
	}

}

이중 연결리스트 큐

structure LinkedListQueue:
	head : Node
    tail : Node
    size : Integer

• head는 첫번째 데이터를 가리키는 노드다
• tail은 마지막 데이터를 가리키는 노드다
• size는 원소의 개수를 저장한다.

이중 연결리스트를 이용해서 구현하면 메모리의 제한에 걸리지 않는이상 overflow error가 발생하지 않는다. poll()시 tail에서 데이터를 추출하고 offer()시 head에 새로운 node를 대입한다.

/**
 * 
 * @author junho
 *
 * @param <T>
 * 이중 연결리스트로 큐 구현하기
 */
class Node<T> {
	T data;
	Node<T> prev;
	Node<T> next;
	
	public Node() {}
	public Node(T data) {
		this.data = data;
	}
}


public class LinkedListQueue<T> implements IQueue<T>{
	
    private Node<T> head = null;
    private Node<T> tail = null;
    private int size = 0;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

	@Override
	public boolean offer(T value) {
		return add(new Node<T>(value));
	}

    /**
     * Enqueue the node in the queue.
     * 
     * @param node to enqueue.
     */
    private boolean add(Node<T> node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            Node<T> oldHead = head;
            head = node;
            node.next = oldHead;
            oldHead.prev = node;
        }
        size++;
        return true;
    }

	@Override
	public T poll() {
        T result = null;
        if (tail != null) {
            result = tail.data;

            Node<T> prev = tail.prev;
            if (prev != null) {
                prev.next = null;
                tail = prev;
            } else {
                head = null;
                tail = null;
            }
            size--;
        }
        return result;
	}

	@Override
	 public T peek() {
        return (tail != null) ? tail.data : null;
    }

	@Override
	public void clear() {
        head = null;
        tail = null;
        size = 0;
	}

	@Override
	public boolean isEmpty() {
		return (head == null) ? true : false;
	}

	@Override
	public int size() {
		return size;
	}
}

큐 활용

큐로 heap 구현하기

deque 구현하기