Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 146 ยท Collections

Collection Algorithms by Hand

Build a stack, queue, ring-buffer deque and binary heap in Swift on top of Array, learn why removeFirst is slow, and see where swift-collections fits in. Runnable examples.

Swift's standard library gives you Array, Set and Dictionary, and that covers most programs. It deliberately does not include a stack, a queue, a deque or a priority queue. The reason is not an oversight: an Array already is a perfectly good stack, and the other structures are small enough to build on top of arrays in a few dozen lines. Building them yourself is the best way to see what the collection protocols are for, to learn why some obvious code is slow, and to know what to ask for when you do reach for a package.

This lesson builds four structures by hand: a stack, a queue, a ring-buffer deque and a binary heap (a priority queue). Each one is a generic struct with value semantics, as described in Collection Protocols. We finish with a look at the swift-collections package, which ships polished versions of all of these.

A stack is just an Array

A stack is last in, first out: you add and remove at the same end. Swift's Array does that in amortized O(1) with append and popLast, so a stack type is only a thin wrapper that hides the other array methods and makes the intent obvious:

Swift A generic Stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Notice that pop() returns an optional instead of crashing on an empty stack. Callers decide what an empty stack means, and guard open.pop() == expected handles "popped nothing" and "popped the wrong bracket" with one comparison, because nil == "(" is false.

The wrapper is a struct, so a copy of a stack is independent of the original; the array inside copies lazily (copy-on-write, see Value vs. Reference Semantics). It also needs mutating on push and pop, and that matters:

Swift Mutating a let constant (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The compiler stops with error: cannot use mutating member on immutable value: 'stack' is a 'let' constant. Declare it with var. Popping an empty stack with a force-unwrap goes the other way: it compiles and fails at run time.

Swift Force-unwrapping an empty pop (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The first pop prints 1, then about to pop again, and the second pop kills the program: the process dies with Illegal instruction (SIGILL) and a backtrace. A debug build would add the message "Unexpectedly found nil while unwrapping an Optional value". Prefer if let or guard let for results that can legitimately be missing.

Why a naive queue is slow

A queue is first in, first out: add at the back, remove from the front. The tempting implementation is an array with append and removeFirst:

Swift
// Read-only example: correct, but O(n) per dequeue
var queue: [Int] = []
queue.append(1)
queue.append(2)
let next = queue.removeFirst()   // shifts every remaining element one slot left

removeFirst() must move all the other elements down, so it costs O(n). A queue that handles a million items does about a trillion element moves in total. (removeLast is cheap; removeFirst is not.) There are three standard cures.

Cure 1: two stacks

Keep an inbox you append to and an outbox you pop from. When the outbox is empty, pour the inbox into it, reversing the order on the way. Each element is moved at most once, so every operation is O(1) amortized: a single dequeue now and then costs O(n), but averaged over many operations it is constant.

Swift A queue from two arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The breadth-first search is the queue's reason to exist: because the first place put in is the first taken out, places are visited in order of distance, so the first time the goal appears it is reached by a shortest path.

Cure 2: a head index

Keep a single array and a head integer. Dequeue returns items[head] and increments head; every so often (say when more than half the array is dead space) remove the consumed prefix in one go. This is compact and fast, but the consumed slots stay allocated until you compact, so elements are not released promptly.

Cure 3: a ring buffer

Store the elements in a fixed-size array treated as a circle. This is the best general answer, and it also gives you a deque (double-ended queue) for free, so we build it next.

A deque with a ring buffer

A ring buffer keeps head (where the first element lives) and count. Element number i lives at slot (head + i) % capacity. Adding at the back writes after the last element. Adding at the front moves head one step backwards, wrapping to the end of the array if needed. When the array is full, double the capacity and copy the elements into their logical order.

Swift A ring-buffer Deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Study the second printed layout: after pushFront(0) the value 0 sits in the last slot, while head points at it. The logical order is still 0 1 2 3, which is what Array(d) shows. Doubling the buffer when it fills keeps every operation O(1) amortized, the same argument as for Array.append.

One detail in the initializer: it calls Swift.max(...) with the module name. Once Deque conforms to Sequence, it has an instance method called max(), and inside the type a bare max(...) refers to that method instead of the global function; without the prefix the compiler reports use of 'max' refers to instance method rather than global function 'max' in module 'Swift'.

The conformance to RandomAccessCollection took four lines because indices are plain offsets 0..<count; all the cleverness stays inside slot(_:). Here the zero-based indices are fine because Deque is not a slice. A fixed-capacity version (drop growIfFull and overwrite the oldest element) gives you the classic "last N readings" buffer.

Why is there no Deque in the standard library? The designers prefer to keep the library small and let packages evolve faster than the language. Apple's swift-collections package provides Deque, Heap, OrderedSet, OrderedDictionary and more; see the end of this lesson.

A binary heap for priorities

A priority queue hands out the most important item first, whatever order the items arrived in: the next task to run, the nearest unvisited city, the smallest of a stream of numbers. Sorting the array after each insertion costs O(n log n) per push. A binary heap does push and pop in O(log n), and peeking at the top in O(1).

A heap is stored in a plain array, viewed as a tree: the children of index i are 2i + 1 and 2i + 2, and its parent is (i - 1) / 2. The rule (the heap property) is that every parent has at least as much priority as its children, so the best item is always at index 0. Two small operations maintain it:

  • sift up after a push: put the new item at the end and swap it with its parent while it outranks it;
  • sift down after a pop: move the last item to the root (after removing the old top) and swap it with its better child until the rule holds again.
Swift A generic binary Heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The array printed after each push is not sorted: it only obeys the heap property (index 0 is the smallest, and every parent is smaller than its children). Pop all the items in a loop and they come out in sorted order, which is exactly heap sort, O(n log n).

Passing the ordering as a closure (< for a min-heap, > for a max-heap) makes the type reusable for any element, including structs that are not Comparable:

Swift Scheduling tasks with a priority queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

A heap is not stable: items with equal priority may come out in any order. When order among equals matters (as for "deploy" and "hotfix" above), add a tie-breaker such as an arrival counter to the comparison, as the closure does. The same closure style is what a trailing Heap<Task> { ... } call uses.

Heaps are the engine of Dijkstra's shortest-path algorithm, of "top K" queries (keep a min-heap of size K and discard the smallest whenever it grows beyond K), of event simulators and of merge-K-sorted-lists. You will use them again in the graph projects later in the course.

Choosing the structure

Structure Add Remove Backed by Use when
Stack O(1) at end O(1) at end Array undo, parsing, depth-first search, expression evaluation
Queue O(1) at back O(1) amortized at front two arrays or a ring breadth-first search, work lists, buffering
Deque O(1) both ends O(1) both ends ring buffer sliding windows, palindromes, work stealing
Heap O(log n) O(log n) the top Array as a tree scheduling, shortest paths, top-K

Remember that the standard Array is already excellent at one end. If you only ever add and remove at the back, you do not need a custom type.

What swift-collections offers

For production code you normally do not hand-roll these. The swift-collections package, maintained by the Swift project, provides tested and optimized versions: Deque, Heap, OrderedSet, OrderedDictionary, BitSet and TreeSet. It is a package, so it needs the Swift Package Manager, which is not available in this lesson's runner. This is a read-only example:

Swift
// Package.swift (read-only): add the dependency
// .package(url: "https://github.com/apple/swift-collections", from: "1.1.0")
// and in your target: .product(name: "Collections", package: "swift-collections")

import Collections

var line: Deque<String> = ["ana", "ben"]
line.append("cho")          // back
line.prepend("zed")         // front
let first = line.removeFirst()

var heap = Heap<Int>()
heap.insert(3)
heap.insert(1)
let smallest = heap.popMin()

The names differ slightly from ours (prepend, popMin, insert), but the ideas are identical, and having built them once you can reason about their costs. Swift Package Manager shows how packages are declared.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is array.removeFirst() a poor way to dequeue from a large queue?

    Removing at the front forces all other elements to move down one slot. Two stacks, a head index or a ring buffer avoid that.
  2. 2. In a two-stack queue, when are elements moved from the inbox to the outbox?

    Each element is moved at most once, which is why dequeue is O(1) amortized even though an individual dequeue may move many elements.
  3. 3. In a ring buffer with capacity 4 and head at slot 0, where does pushFront write?

    Head steps backwards and wraps around: (0 - 1 + 4) % 4 is 3. The logical order stays correct because every access goes through (head + offset) % capacity.
  4. 4. In a binary heap stored in an array, where are the children of index 2?

    The children of index i are 2i + 1 and 2i + 2, so index 2 has children 5 and 6.
  5. 5. What guarantee does a heap give about its array?

    A heap is only partially ordered. That is enough to find the top in O(1) and to restore the rule after a push or pop in O(log n).

Summary

  • The standard library has no stack, queue, deque or priority queue; each is easy to build on Array with value semantics.
  • A stack is an array used at one end (append and popLast). Return optionals from pop rather than trapping.
  • removeFirst() is O(n). Build queues from two arrays (amortized O(1)), a head index, or a ring buffer.
  • A ring buffer stores elements at (head + i) % capacity, supports pushes and pops at both ends in O(1) amortized, and becomes a RandomAccessCollection with a few lines.
  • A binary heap keeps the best element at index 0 and restores order with sift up and sift down in O(log n); it is not stable, so add a tie-breaker when needed.
  • For production, prefer swift-collections (Deque, Heap, OrderedSet, OrderedDictionary) when package dependencies are available.

Next: Structures