Distributed queuing is a fundamental problem in distributed computing, arising in a variety of applications. In a distributed queuing protocol, each participating process informs its predecessor of its identity, and (when appropriate) learns the identity ofits successor.This paper presents a new, self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the Arrow distributed queuing protocol, a simple path-reversal protocol that runs on a network spanning tree.The protocol is structured as a layer that runs on top ofan y selfstabilizing spanning tree protocol. This additional layer stabilizes in constant time, establishing that self-stabilizing distributed queuing is no more difficult than self-stabilizing spanning tree maintenance. The key idea is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree.