Please explain. Without maintaining that ordering, you're going to have to iterate over the entire stack after every pop, no? One of their requirements was to keep pop() at O(1) rather than O(n).