现在我有一个队列(JS数组),用于存储等待游戏的玩家。我需要队列的FIFO属性,以便先加入队列的玩家首先进入新游戏。队列的问题在于它没有恒定时间的查找。如果我能够拥有一个跟踪插入顺序的映射表就好了(我知道在JS中依赖于map是不可靠的)。如果我为其插入顺序给定一个值,则需要在有人离开队列时更新它,因此这也不是有用的。是否有解决方案?保持插入顺序并实现常量查找的方法?
现在我有一个队列(JS数组),用于存储等待游戏的玩家。我需要队列的FIFO属性,以便先加入队列的玩家首先进入新游戏。队列的问题在于它没有恒定时间的查找。如果我能够拥有一个跟踪插入顺序的映射表就好了(我知道在JS中依赖于map是不可靠的)。如果我为其插入顺序给定一个值,则需要在有人离开队列时更新它,因此这也不是有用的。是否有解决方案?保持插入顺序并实现常量查找的方法?
如果没有内存限制,也许你可以使用双向链表实现队列,并将其维护在一个映射中。以下是一个示例实现:
function Queue() {
var oldestRequest,
newestRequest,
map = {};
this.addUser = function(userID) {
var newRequest = { userID: userID };
map[userID] = newRequest;
// Set this as the oldest request if it is the first request
if (!oldestRequest) {
oldestRequest = newRequest;
}
// If this isn't the first request, add it to the end of the list
if (newestRequest) {
newestRequest.next = newRequest;
newRequest.previous = newestRequest;
}
newestRequest = newRequest;
};
this.nextUser = function() {
// If we don't have any requests, undefined is returned
if (oldestRequest) {
var request = oldestRequest;
oldestRequest = request.next;
delete map[request.userID];
// Make sure we don't hang on to references to users
// that are out of the queue
if (oldestRequest) {
delete oldestRequest.previous;
}
// This is the last request in the queue so "empty" it
if (request === newestRequest) {
newestRequest = undefined;
}
return request;
}
};
this.removeUser = function(userID) {
var request = map[userID];
delete map[userID];
if (request.previous) {
request.previous.next = request.next;
}
if (request.next) {
request.next.previous = request.previous;
}
};
return this;
}
Map
代替Object
用于在添加和删除值时提供更好的性能。// TypeScript typing
export type KeyValuePair<K, V> = [ K, V ]
interface ValueData<V> {
value: V
refCount: number
}
// Public classes
export class MapQueue<K, V> {
readonly #queue: Array<KeyValuePair<K, V>>
readonly #map: Map<K, ValueData<V>>
constructor () {
this.#queue = []
this.#map = new Map()
}
get length (): number {
return this.#queue.length
}
unshiftOne (pair: KeyValuePair<K, V>): number {
const [key, value] = pair
const valueData = this.#map.get(key)
if (valueData !== undefined) {
if (valueData.value !== value) {
throw new Error(`Key ${String(key)} with different value already exists`)
}
valueData.refCount++
} else {
this.#map.set(key, {
value,
refCount: 1
})
}
return this.#queue.unshift(pair)
}
pop (): KeyValuePair<K, V> | undefined {
const result = this.#queue.pop()
if (result !== undefined) {
const valueData = this.#map.get(result[0])
if (valueData !== undefined) {
valueData.refCount--
if (valueData.refCount === 0) {
this.#map.delete(result[0])
}
}
}
return result
}
get (key: K): V | undefined {
return this.#map.get(key)?.value
}
}