Java 응용 프로그램의 경우 item1이 queue2의 "item2"앞에 있는지 알아내는 방법이 필요합니다. 물론 iterator를 사용하여 목록을 탐색하기 시작할 수 있습니다. 그러나 이것을 발견하는 또 다른 방법이 있을까요?대기열 항목이 다른 항목보다 "전에"있는지 여부를 확인하는 효율적인 방법이 있습니까?
내 특정 응용 프로그램의 경우 하나의 개체가 다른 개체보다 먼저 있는지 확인하기 위해 색인을 제공하는 LinkedList를 사용할 수 없습니다.
아니요, 없습니다. 정의에 따라 대기열의 유일한 작업은 대기열에 포함 및 대기열에서 제외되기 때문에 애플리케이션에 다른 작업이 필요한 경우 대기열이 올바른 구조가 아닙니다.
LinkedList는 그런 기본 클래스이므로 대안으로 제안 할 수있는 것을 상상하기가 어렵습니다. 무작위 액세스를 지원하며 인덱싱 된 액세스를 훨씬 빠르게 수행 할 수있는 ArrayList를 제외하고는 그러나 ArrayList는 큐만큼 효율적이지 않습니다.
일반적으로 큐는 큐를 제거하지 않고 큐 상단에있는 것을 볼 수있는 "peek"조작을 제공하지만 다른 것은 다른 데이터 구조를 필요로합니다. 그렇지 않으면 큐에서 벗어난 큐를 다른 큐에 놓을 때까지 기다렸다가 그 값을 다시 큐에 넣어야합니다.
item2가 대기열에 이미 있는지 알아야하는 경우 삽입 순서를 유지하고 LIFO 대기열로 사용할 수있는 java.util.LinkedHashMap을 사용할 수 있습니다.
* LIFO 대기열로 사용할 수 있습니다 * 어떻게? 대기열에 필요한 peek(), poll() 등의 메소드가 없습니다. 내가 생각할 수있는 유일한 방법은'map.entrySet(). iterator(). next()'를 사용하는 것입니다. 그러나 이것은 매우 비효율적입니다! –
끔찍하게 비효율적 인 것은 실제로 내가 사용하는 용어가 아닙니다. 대부분의 경우, 이것은 괜찮습니다. 얼마나 많은 항목이 목록에 있고 얼마나 자주 작업이 필요합니까? 'map.entrySet(). iterator(). next()'가 코드에서 문제가되는 것을 측정하지 않았다면, 신경 쓰지 마라. –
Queue은 Collection입니다. 따라서 해당 요소를 항상 Collection에 복사하면 주문을 검색 할 수 있습니다.
List<YourType> copy = new ArrayList<YourType>(yourQueue);
if(copy.indexOf(obj1)<copy.indexOf(obj2)){
// some code here
}
물론 이것은 매우 비효율적이지만 작동합니다. 그래서, 물론
/**
* Returns -1 if a occurs in the collection before b, 1 if b occurs before a
* and 0 otherwise.
*/
public static <T> int comparePositionInCollection(final T a,
final T b,
final Collection<T> collection){
// todo: check for a==null, b==null, a.equals(b)
final Iterator<T> iterator = collection.iterator();
boolean foundA = false;
boolean foundB = false;
int result = 0;
while(iterator.hasNext()){
final T t = iterator.next();
if(a.equals(t)){
if(foundB){
result = 1;
break;
}
foundA = true;
} else if(b.equals(t)){
if(foundA){
result = -1;
break;
}
foundB = true;
}
}
return result;
}
당신이 반복자를 액세스하기 전에 큐를 동기화 할 것이다 : A는 iterator()을 통해 그것을 할 것
또 다른 방법은 (이 일을하는 동안 당신은 아마 큐를 동기화해야합니다) 이것은 또한 비효율적이다.
나는 룩업 테이블을 참조 할 수있는 우선 순위 대기열을 권합니다. 그렇게하면 얻고 자하는 요소에 대한 지속적인 성능과 다항식 삽입 비용이 발생합니다. 그러나 이것은 최상의 또는 최우선 순위 항목을 찾는 것이 아니라 단순히 비교를 시도하는 경우 사용자의 용도에 맞게 특수화 될 수 있습니다. 그러나 지속적인 성능은 언제나 좋습니다. 그리고 나서 배열을 반복적으로 반복하지 않고 찾고 있습니다.
큐 개체를 Integers 개체와 별도로 HashMap을 유지하고 큐에 추가 한 개체의 총 개수를 계산합니다. 따라서 개체 X를 삽입하면 개체 X가 N 번째 개체가 삽입 됨). 객체를 큐에 추가 할 때마다 HashMap에 키를 추가하십시오. 값은 카운터의 현재 값입니다.
두 개의 객체 중 첫 번째 객체를 물어볼 필요가있을 때 HashMap에서 객체를 찾아서 서수를 비교하십시오. 어느 쪽이 먼저 낮은 가치를 지녔습니다.
큐가 아닌 다른 데이터 구조를 사용할 수 있습니까? – Bernard
효율성 때문에 대기열을 사용하고 싶습니다. http://stackoverflow.com/questions/4724995/lock-free-concurrent-linked-list-in-java – ptikobj
을 참조하십시오. 아마도이 경우 사용하는 것이 더 좋습니다. List list = Collections.synchronizedList (new LinkedList