Stacks, queues, and associative arrays: the data shapes your algorithms run on

Stacks, queues, and associative arrays are the three data shapes your algorithms actually use. Trees, graphs, heaps, and tries are built from them or traversed with them. The site’s problems use all three: Two Sum needs an associative array to remember what it has seen, Valid Parentheses is a stack in disguise, and a breadth-first search over a grid (the shape underneath Number of Islands) needs a queue. You have probably used all three today without naming them.

This article gives them names. You will learn the two ordering disciplines - the stack’s last-in-first-out and the queue’s first-in-first-out - plus the lookup structure that ignores order. Lua then supplies the odd case: one structure does all three jobs. The contrast with the other languages makes Lua’s single-table design surprising, so the order matters: the shapes first, the twist after. If the complexity claims in the middle feel unfamiliar, the What O(n) actually promises article fills in the notation.

Stacks: last in, first out

A stack is a list with one rule: you can touch only the top. Insert there. Remove there. Read there. In textbook terms, a stack is an array with restrictions. Those restrictions are the feature:

The truth is that these two structures [stacks and queues] are not entirely new. They’re simply arrays with restrictions. Yet these restrictions are exactly what make them so elegant.

The operations have their own names - you push onto the stack and pop off it - and the discipline has an acronym: LIFO, last in, first out. As the same textbook puts it, “the last item pushed onto a stack is always the first item popped from it.” Think of plates at a buffet. You pick up the last plate placed down. An editor’s undo history works the same way: the most recent action is the first one undone. The call stack of a program - the subject of the site’s recursion article - matters most. Every function call pushes a frame, every return pops one, and a recursion that never returns keeps pushing until the machine says enough.

Algorithms use stacks when the computation needs a history and the newest item controls the next step. Valid Parentheses pushes each opening bracket and pops on each closing one, matching the closing bracket with the most recent opener; a mismatch makes the string invalid. Depth-first search uses a stack to remember which frontier nodes to visit next. Evaluate Reverse Polish Notation pushes operands and pops two when an operator arrives. The shape stays the same: a temporary store where the newest item has priority.

In code, a stack is nearly free because most languages let you add and remove at one end in constant time:

stack = []
stack = [1 | stack]        # push 1
stack = [2 | stack]        # push 2
[top | stack] = stack      # pop -> top is 2, stack is [1]

local stack = {}
table.insert(stack, 1)     -- push 1
table.insert(stack, 2)     -- push 2
local top = table.remove(stack)  -- pop -> 2

const stack = []
stack.push(1)              // push 1
stack.push(2)              // push 2
stack.pop()                // pop -> 2

Push and pop are $O(1)$ in all three: adding to the head of an Elixir list, appending to the end of a Lua sequence, or pushing onto a JS array each touches exactly one element.

Queues: first in, first out

A queue is the stack’s polite sibling: add at one end and remove from the other. First in, first out - FIFO - describes the checkout line, the printer spool, and the task scheduler handing work to the next free worker. The algorithms book calls stacks and queues “elegant tools for handling temporary data. From operating system architecture to printing jobs to traversing data, stacks and queues serve as temporary containers that can be used to form beautiful algorithms.”

The algorithm that depends on a queue is breadth-first search: explore every neighbor of the current node before moving to those neighbors. The first node into the frontier is the first node visited. Level-order traversal of a tree, shortest-path-in-unweighted-graph, and the flood-fill inside Number of Islands all follow one loop: dequeue a node, enqueue its unvisited neighbors, repeat.

Queues expose implementation costs. In JavaScript, queue.shift() removes the first element but also reindexes every remaining element. Popping from the front of an array is $O(n)$, not $O(1)$, so a naive queue that shifts on every dequeue turns a linear algorithm quadratic. Elixir has the opposite problem: lists are cheap to add to at the front and expensive to pop from the back, so a FIFO queue built on a plain list must reverse or use the :queue module. Use the same fix in every language: a queue has two ends, so track both.

Lua’s table-based queue from the Programming in Lua reference shows the idea directly. Do not move elements. Keep two indices - one for the first element and one for the last - and let them move upward:

local function newQueue()
  return {first = 0, last = -1}
end

local function pushLast(list, value)
  local last = list.last + 1
  list.last = last
  list[last] = value
end

local function popFirst(list)
  local first = list.first
  if first > list.last then error("list is empty") end
  local value = list[first]
  list[first] = nil    -- so the garbage collector can reclaim it
  list.first = first + 1
  return value
end

Both operations touch one element and one index - constant time, with no shuffling. The indices drift upward forever, but the book notes that the numbers give you room: “because we represent arrays in Lua with tables, we can index them either from 1 to 20 or from 16777201 to 16777220. With 64-bit integers, such a queue can run for thirty thousand years, doing ten million insertions per second, before it has problems with overflows.” The shape matters: a queue is not a special kind of array. It is a discipline - add at one end and remove at the other.

Associative arrays: lookup by name

The third shape ignores order. An associative array pairs keys with values and answers one question in $O(1)$ on average: what is the value for this key? The naming zoo is a running joke:

Most programming languages include a data structure called a hash table, and it has an amazing superpower: fast reading. Note that hash tables are called by different names in various programming languages. In Python they’re called dictionaries, and other languages call them hashes, maps, hash maps, dictionaries, or associative arrays.

Whatever your language calls it - Elixir’s Map, JavaScript’s Map (or a plain object), Erlang’s map, Lua’s table - the shape stays the same: “a hash table is a list of paired values. The first item in each pair is called the key, and the second item is called the value.” The key determines the location: hash it, jump to the slot, and read the value. No scan. That is why Two Sum works in one pass over the array - store each number as a key with its index as the value, then ask the table for the complement of each new number in constant time instead of rescanning everything. Contains Duplicate and Group Anagrams use the same pattern for different lookups: build a table keyed by what you need later.

Two properties deserve your attention. First, the fast path works in one direction: “the whole premise of the hash table is that the key determines the value’s location. But this premise only works in one direction: we use the key to find the value.” Looking up a value to find its key requires a scan. Second, each key exists exactly once; you cannot store two values under the same key. That is why the structure also works as a set - use “key = element, value = true,” and membership becomes “is this key present?” instead of “is this element in the list?”

The Lua twist: one structure, three jobs

Here is the oddity from the opening. In Elixir, lists and maps are different types with different operations. In JavaScript, arrays and objects/Maps are different types with different behaviors. Lua has exactly one structure - the table - and it does all three jobs. The language’s own reference manual says it plainly:

Tables are the main (in fact, the only) data structuring mechanism in Lua, and a powerful one. We use tables to represent arrays, sets, records, and many other data structures in a simple, uniform, and efficient way.

The data-structures chapter is even more direct: “Tables in Lua are not a data structure; they are the data structure.” A Lua table is a stack when you push with table.insert and pop with table.remove. It is a queue when you use the two-index discipline from the previous section. It is an associative array natively, because that is what a table is:

A table in Lua is essentially an associative array. A table is an array that accepts not only numbers as indices, but also strings or any other value of the language (except nil).

Read that last clause again. It is the part programmers from other languages find strange. Lua table keys can be anything except nil - strings, numbers, other tables, functions, and booleans. An array in Lua is not a separate kind of table; it is a table whose keys happen to be the integers 1, 2, 3… (and, yes, counting starts at 1 - a running gag for every 0-indexed programmer who meets Lua). The same {} can hold a list of items or a phone book. You do not choose list or map up front. The answer is always a table; the discipline comes from how you use it.

That uniformity enables the reverse-table pattern. The reference book’s example translates day names to positions - given days = {"Sunday", "Monday", "Tuesday"} (an array), build revDays = {["Sunday"] = 1, ["Monday"] = 2, ...} (an associative array), and “instead of searching the table, looking for the given name,” index it. The one-directional lookup limitation from the previous section disappears when both structures are tables: flip the table by building another one. Sets are just as simple - “an efficient and simple way to represent such sets is to put the set elements as indices in a table. Then, instead of searching the table for a given element, we just index the table and test whether the result is nil.”

The cost is yours. A table is a queue only if you always add at one end and remove at the other; Lua will not stop you from poking a hole in the middle. Iteration has two flavors for the same reason: ipairs walks the array part (the integer keys in order), while pairs walks every key including the string ones - and the length operator # only reliably measures the sequence part. None of this is a flaw. It is the design: one structure means fewer choices and more decisions. Elixir draws the boundary differently - the type system and pattern matching keep lists and maps distinct, and functions like Enum.map/2 and Map.get/2 each do one job well. Lua takes the older, more trusting approach: here is one box, put anything in it, and handle it carefully. When you solve an algorithm problem on this site in Lua, you work within that contract - the same Two Sum that uses a Map in Elixir uses a plain table in Lua, and it works because the table was built to be both.

Choosing the right shape

The three shapes answer three questions. Name the question first:

Shape	Question it answers	Cost (typical)	Algorithm that lives on it
Stack	“What is the most recent thing?”	push/pop $O(1)$	Valid Parentheses, RPN, DFS
Queue	“What is the oldest thing waiting?”	enqueue/dequeue $O(1)$ (with two ends)	BFS, level-order traversal
Associative array	“What is the value for this key?”	lookup $O(1)$ average	Two Sum, Contains Duplicate, memoization

The table omits one question: “what is the i-th thing in order?” That is an array’s job. Arrays are the familiar baseline that this article’s shapes restrict or generalize - a stack is an array with one door, a queue is an array with two, and an associative array is an array whose indices stopped being numbers. Remember this when an algorithm feels slow: ask which question it is answering by brute force. If it scans for the most recent thing, use a stack; if it scans for an element by key, use a hash table; if it processes things in arrival order, use a queue with two ends to remove the reindexing. These shapes are small, old, and everywhere. Reach for them first.

Where to go next

• Queue with Two Stacks - the exercise that turns this article’s shapes into a constraint: build a FIFO queue from exactly two stacks, transferring between them to get the order back.
• Two Sum, Valid Parentheses, and Contains Duplicate on /problems - the three shapes in their natural habitat, each solvable in Elixir, Erlang, TypeScript, or Lua.
• Recursion: the pattern that calls itself
  • the call stack is the stack your programs push onto whether you ask for one or not.
• What O(n) actually promises - the notation behind “constant time” and why the queue trap turns $O(n)$ into $O(n^2)$.
• Pattern matching: the = you’ve been reading wrong
  • the Elixir-side skill that makes pulling the head off a stack literal.
• Hash tables: the O(1) that has fine print
  • the associative array under the hood: hash functions, collisions, load factor, and why the O(1) needs the fine print.
• Graphs: when the answer is a hop away
  • the queue doing its real job as an algorithm’s backbone: the frontier that makes BFS breadth-first.
• Dijkstra’s algorithm: when every hop costs something
  • the queue promoted to a priority queue, and the algorithm that made the promotion necessary.

Three shapes. Three questions. A stack remembers what you did most recently, a queue remembers what has waited longest, and an associative array remembers what it paired with each key. Every harder problem on the site is a loop over one of those answers. In Lua, one structure quietly plays all three parts.