  In this paper, we describe a novel algorithm to create a con- current
wait-free stack. To the best of our knowledge, this is the first wait-free
algorithm for a general purpose stack. In the past, researchers have proposed
restricted wait-free implementations of stacks, lock-free implementations, and
efficient universal constructions that can support wait-free stacks. The crux
of our wait-free implementation is a fast pop operation that does not modify
the stack top; instead, it walks down the stack till it finds a node that is
unmarked. It marks it but does not delete it. Subsequently, it is lazily
deleted by a cleanup operation. This operation keeps the size of the stack in
check by not allowing the size of the stack to increase beyond a factor of W as
compared to the actual size. All our operations are wait-free and linearizable.
