Stacks and queues

Stack<Item> is last-in-first-out and Queue<Item> is first-in-first-out, and each spends the words everybody knows for it: a stack has push, pop and peek on its top, a queue has enqueue at the back and dequeue and peek at the front. Neither has an index; the only way to look further inside one is to take items out of it, or to iterate it.

Example#

var pending = Queue.of 1
pending.enqueue 2
print pending.dequeue()

var brackets = Stack<Char>.of()
brackets.push '('
print brackets.peek()
print brackets.pop()

Syntax#

Stack.of(...items)          the last argument ends up on top
Queue.of(...items)          the first argument ends up at the front

stack.push(value)       stack.pop(): Item?          in place
queue.enqueue(value)    queue.dequeue(): Item?      in place

stack.peek(): Item?     queue.peek(): Item?         look without taking

Rules#

1. Each structure has its own words, so a call says what it does without a look at the receiver's type. On top of a stack and at the back of a queue are different meanings, and push and enqueue say which one it is.

2. A Stack iterates from top to bottom; a Queue iterates front to back. Both iterate in the order they hand items out, so peek() is what the next pop() or dequeue() would answer, without taking anything.

   const stack = Stack.of 1, 2, 3
   print stack.peek()
   print stack.toList()

3. There are no participles on a stack or a queue. Taking an item out answers the item, and a changed copy would have to answer the pair (Item, Self)? beside it. A copy does the same thing without a second word: a stack is a value, so a var copy can be popped while the original keeps every item.

   const stack = Stack.of 1, 2, 3
   var rest = stack
   if const Some(top) = rest.pop() {
     print "top: {top}, remaining: {rest.length()}, before: {stack.length()}"
   }

4. Equals and Hash follow the items, and both are order-dependent like a List's. Two stacks or two queues are equal when they hold equal items in the order they iterate in - top down for a Stack, front to back for a Queue - so two stacks with the same items in a different order are unequal and need not hash alike.

   const stack = Stack.of 1, 2
   print(stack == Stack.of(1, 2))
   print(stack == Stack.of(2, 1))

5. Both traits have two implementations, written in plain TorbScript rather than as a native type. ArrayStack is a List used from the end, and the default; ArrayQueue is a ring buffer on top of a List, so nothing is moved and nothing is allocated until the buffer is full. ConsStack and BankersQueue (items 6 and 7) are the second implementations, whose copies share structure. Unlike List, Map and Set, neither trait has a trie-backed implementation.

6. ConsStack is a stack whose copies share their tail. It is a persistent cons list: push and pop are O(1) and copy nothing, and var rest = stack costs one reference however deep the stack is. Pushing or popping on a copy never changes the original. It fits backtracking, undo and a parser's context; against an ArrayStack it pays one allocation per push and has no contiguous storage. It is chosen where the stack is constructed.

   use ConsStack from "std/collections"
   
   var history = ConsStack.of 1, 2, 3
   const before = history
   history.push 4
   print history.toList()
   print before.toList()

7. BankersQueue is a queue whose copies share their structure. It is two linked lists, a front and a reversed rear: enqueue and peek are O(1), dequeue is amortised O(1), and iterate is O(n). A copy of an ArrayQueue copies the whole ring on its first write; a copy of a BankersQueue costs one reference, so it fits a queue that is kept in many versions. iterate copies both lists into a List, so iterating a large queue repeatedly costs O(n) allocation each time. It is chosen where the queue is constructed.

A priority structure is a Heap, not a Queue#

A Queue gives items back in the order they went in. When the next item should be the one with the smallest key, use a Heap: the order is a function it carries, given where it is built. insert and removeSmallest are O(log n), peekSmallest is O(1), and iterating hands items out smallest first without changing the heap. Items with equal keys come out in no promised order; put the tie-break into the key. A Heap has no trait, because it has no second implementation to share one with.

use Heap from "std/collections"

var jobs: Heap<String> = Heap.by { name => name.byteLength() }
jobs.insert "review"
jobs.insert "build"
jobs.insert "go"
print jobs.peekSmallest()
print jobs.removeSmallest()
print jobs.length()

What this is not#

Neither trait has an index. There is no stack[0]: the only way to see an element below the top is to pop down to it or to iterate the whole collection.

const stack = Stack.of 1, 2, 3
print stack.toList()

const stack = Stack.of 1, 2, 3
print stack[0]
// error: `Stack<Int64>` does not implement `Index`, so `a[key]` has no meaning for it

There is no add on either. add would be one word for "on top" and "at the back", which is what the words of each structure exist to tell apart.

Related#

• The collection traits - Iterate and Length, which both traits sit on top of.
• Lists - the List each default implementation is built from.
• Verbs and participles - where a participle pays for itself, and where it does not.
• Option - the Item? that pop(), dequeue() and peek() all answer.