The Stack algorithm, which is a best-first search algorithm widely used in speech recognition, is modified for application to the problem of recognizing machine printed text in the Document Image Decoding (DID) framework. An iterative scheme is described wherein successively more stringent Stack searches are performed, each time using a model of the image that is updated on the basis of what was discovered on the previous iteration. In this way, the algorithm can adapt to realistic degradation patterns that are irregular and perhaps not well described by stationary models. The contribution of this work is twofold: (1) it represents a reliable method of estimating suitable parameter values for Stack decoding in DID, and (2) as a means of handling nonstationary degradation, it presents an alternative to another recently developed approach that is described elsewhere, the Iterated Complete Path algorithm, at potentially lower computational cost. Preliminary results are presented on text line images with simulated nonstationary noise.