순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.
The advantage of using an array implementation for a stack is that it is more efficient in terms of time than a linked list implementation. This is because there is none of the work associated with claiming new store as the size of the stack increases and garbage collecting it as it reduces. Rather there is a fixed amount of store set aside from the start for the stack. As stacks are destructive we do not have to copy this store every time we perform a stack operation, and in general in the sort of applications where stacks are used we do not have large numbers of them, so there is not a big issue of waste of store.
http://www.eecs.qmul.ac.uk/~mmh/DCS128/2006/resources/arraystacks.html
Stack st = new Stack();
Queue q = new LinkedList(); //Queue인터페이스의 구현체인 LinkedList사용stack은 vector를 상속하고 있고, vector는 내부적으로 배열을 이용한다
자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐는 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스들을 구현한 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.
PriorityQueue
Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특지잉 있다. 그리고 null은 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다. PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙이라는 자료구조의 형태로 저장한다. 힙은 잠시 후에 배울 이진 트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.
Qyeye pq = new PriorityQueue();
pq.offer(3);
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);
while ((obj = pq.poll()) != null) {
System.out.println(obj);
}