We consider upper Hessenberg unitary-plus-rank-one matrices, that is, matrices of the form $A = \tilde{U} + \tilde{x}\tilde{y}^{T}$, where $\tilde{U}$ is unitary, and $A$ is upper Hessenberg. This includes the class of Frobenius companion matrices, so methods for this type of matrix can be applied to the problem of finding the zeros of a polynomial. The unitary-plus-rank-one structure is preserved by any method that performs unitary similarity transformations, including Francis's implicitly-shifted $QR$ algorithm. We present a new implementation of Francis's algorithm that acts on a data structure that stores the matrix in $O(n)$ space and performs each iteration in $O(n)$ time. This is joint work with Jared Aurentz, Thomas Mach, and Raf Vandebril. Ours is not the first fast algorithm that has been proposed for this problem, but it is the first that has been shown to be backward stable, and it is faster than other fast algorithms that have been proposed previously.