title: Fast implementation of queues in Lua?
body: <p>I am making a game using Lua and I need to use Breadth-first search to implement a fast path-finding algorithm which finds the shortest path between the enemy AI and the player. </p>
  
  <p>I will have up to 3 enemies using this algorithm at once and map is a 2-dimensional tile-based maze. I have already implemented collision detection so now all that is left to do is get a way for the enemies to find the shortest path to the player in a way that can be done quickly and and preferably about 80-90 times per second per enemy.</p>
  
  <p>When I previously implemented breadth-first search, I used a queue in C++. From what I have read about Lua, stack implementations using tables are very efficient since the elements don't need to be shifted after <code>push()</code> (AKA table.insert) and <code>pop()</code> (table.remove) operations. However, I have theorized that queues with large sizes can be very inefficient in Lua, because if you want to insert/remove something from index 1 of a table, all other elements in the table must be shifted either upward or downward in the table.</p>
  
  <p>Thus, I would like to ask some simple questions for those experienced in Lua. What is the simplest and/or fastest implementation of a queue in this language? Is it even possible to have a fast queue in Lua or is it just generally accepted that Lua will always be forced to "shift" all elements for a queue operation such as <code>pop()</code> or <code>append()</code>? </p>
  
  <p>EDIT: I understand that the underlying implementation of "shifting elements" in Lua tables is written in C and is therefore quite optimized. I just would like to know if I have any better options for queues before I begin to write a simple table implementation.</p>