javascript 队列
I have recently been solving LeetCode problems to get more comfortable with data structures. Knowing which data structure to use for a particular problem comes with practice. Therefore, I think that a good way to understand queues better is to look at the solution to the Keys and Rooms LeetCode problem. Before we do that, let’s review what a queue is.
我最近一直在解决LeetCode问题，以更熟悉数据结构。 实践中知道要使用哪种数据结构。 因此，我认为更好地了解队列的一种好方法是查看Keys and Rooms LeetCode问题的解决方案。 在此之前，让我们回顾一下队列是什么。
The queue data structure follows the same concept as a real-life queue. Imagine a queue of people in a coffee shop for example, the person who gets served first would be the person who arrived on the queue first, save for someone skipping ahead in line. We can represent this in Javascript using arrays. If an array of items is our queue, then to dequeue items, we would need to start from the first item in the queue.
队列数据结构遵循与实际队列相同的概念。 想象一下，例如，在咖啡店里有人排队，首先得到服务的人将是首先到达队列的人，除非有人排队等候。 我们可以使用数组在Javascript中表示它。 如果一个项目数组是我们的队列，那么要使项目出队，我们需要从队列中的第一个项目开始。
For example, in the array [a,b,c,d,e] the first item to be dequeued would be a. We can perform this dequeuing using the inbuilt array.shift() method.
例如，在数组[a,b,c,d,e]中，要出队的第一项将是a 。 我们可以使用内置的array.shift()方法执行此出队操作。
Now, let’s take a look at the LeetCode Keys and Rooms Question:
现在，让我们看一下LeetCode钥匙和房间问题 ：
There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.
有N个房间，您从房间0开始。每个房间在0、1、2，…，N-1中都有不同的编号，每个房间可能都有一些用于访问下一房间的钥匙。
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
形式上，每个房间i都有一个钥匙房间[i]的列表，每个钥匙房间[i] [j]是[0，1，…，N-1]中的整数，其中N = rooms.length。 关键房间[i] [j] = v打开数字为v的房间。
Initially, all the rooms start locked (except for room 0).
最初，所有房间开始上锁(房间0除外)。
You can walk back and forth between rooms freely.
您可以在房间之间自由地来回走动。
Return true if and only if you can enter every room.
当且仅当您可以进入每个房间时，才返回true。
The input to the solution function would be an array of arrays where each array represents a room and the values in the array represent keys. So the input [[1], [3], [2]] would mean that there are 2 rooms (counting from index 0). In the zeroth room, we find the key for room one so we can unlock room one. After unlocking room one, we find the key for room 3 in room one. The next room after one is 2, so since we don’t have key 2 yet, we cannot enter room 2. Therefore if given this input, our function should return false.
解决方案函数的输入将是一个数组数组，其中每个数组代表一个房间，而数组中的值代表键。 因此，输入[[1], [3], [2]]表示有2个房间(从索引0开始计数)。 在第零个房间中，我们找到了第一个房间的钥匙，因此我们可以解锁第一个房间。 解锁第一房间后，我们在第一房间找到了第三房间的钥匙。 一个房间之后的下一个房间是2，因此，由于我们还没有键2，因此我们无法进入房间2。因此，如果输入此内容，则函数应返回false 。
Let’s try to figure out the solution using another example. Assuming we have the input [[1,3],[2,0,1],[0,3],[0]]. We need to visit each room sequentially and keep track of the key(s) that we have. How do we do this? We can queue each array (visit each room) and then sequentially dequeue each array, loop through the array and store all the keys in that array in a separate array. If that sounds confusing, it will get clearer in a bit. First of all, we initialize our queue that “visits” each room starting from room zero.
让我们尝试使用另一个示例找出解决方案。 假设我们有输入[[1,3],[2,0,1],[0,3],[0]]. 我们需要顺序访问每个房间，并跟踪我们拥有的钥匙。 我们如何做到这一点？ 我们可以将每个数组排队(访问每个房间)，然后依次使每个数组出队，遍历该数组并将该数组中的所有键存储在单独的数组中。 如果这听起来令人困惑，那一点会变得更加清晰。 首先，我们初始化从“零”房间开始“访问”每个房间的队列。
rooms = [[1,3],[2,0,1],[0,3], [0]] q = []; keys = [0];q.push(rooms[0]);keys will initially contain the key for room zero because that is where we are starting. We now have room zero in the queue.
keys最初将包含零房间的键，因为这是我们开始的地方。 现在，队列中的房间为零。
q = [[1,3]]
q = [[1,3]]
Now in room zero, we have to collect the keys and store them in the keys array. To do this, we retrieve the first item (room) in q , loop through all the keys in that room and store each key (that is not already in keys) in keys.
现在在零房间，我们必须收集密钥并将它们存储在keys数组中。 为此，我们检索q的第一项(房间)，循环访问该房间中的所有键，并将每个键(尚未在keys)在keys 。
let room = q.shift();room.forEach(function(item){ if(!keys.includes(item)){ keys.push(item) q.push(rooms[item]) } })As we retrieve each key, we are also adding the room that the key opens to the queue. So following our example, q and keys will now look like this:
在检索每个密钥时，我们还将密钥打开的空间添加到队列中。 因此，按照我们的示例， q和键现在将如下所示：
q = [[2,0,1], [0]];keys = [0,1,3]If we repeat the code above, q and keys will become:
如果我们重复上面的代码，则q和keys将变为：
q = [[0],[0,3]];keys = [0,1,3,2]We would need to use a while loop to repeat the code above until we run out of rooms to enter. Note that we keep taking out the first item in the queue and putting a new room in the queue only when we have not visited that room previously. So when our queue is empty, we have run out of rooms to enter and we need to exit out of the while loop.
我们将需要使用while循环来重复上面的代码，直到用尽所有空间进入。 请注意，只有当我们之前没有访问过该房间时，我们才会继续取出队列中的第一项并将新房间放入队列中。 因此，当队列为空时，我们已经没有足够的空间进入，并且需要退出while循环。
while(q.length > 0){ let room = q.shift(); room.forEach(function(item){ if(!keys.includes(item)){ keys.push(item) q.push(rooms[item]) } })}When we have exited the while loop, if we were able to visit all the rooms, we should have all the keys stored in keys. So we can use a for loop to check if the key to each room is contained in keys.
退出while循环后，如果我们能够访问所有房间，则应将所有密钥存储在keys 。 因此，我们可以使用for循环来检查每个房间的钥匙是否包含在keys 。
The complete solution will look something like this:
完整的解决方案如下所示：
var canVisitAllRooms = function(rooms) { let q = []; q.push(rooms[0]) let keys = [0] while(q.length > 0){ let room = q.shift(); room.forEach(function(item){ if(!keys.includes(item)){ keys.push(item) q.push(rooms[item]) } })} for(let i = 1; i<rooms.length; i++){ if(!keys.includes(i)){ return false } } return true;};翻译自: https://medium.com/swlh/understanding-data-structures-in-javascript-queues-4a29966b227d
javascript 队列
