use NSOperationQueue as a LIFO stack?

You can set the priority of operations in an operation queue using -[NSOperation setQueuePriority:]. You'll have to rejigger the priorities of existing operations each time you add an operation, but you can achieve something like what you're looking for. You'd essentially demote all of the old ones and give the newest one highest priority.

Sadly I think NSOperationQueues are, as the name suggests, only usable as queues — not as stacks. To avoid having to do a whole bunch of manual marshalling of tasks, probably the easiest thing is to treat your queues as though they were immutable and mutate by copying. E.g.

- (NSOperationQueue *)addOperation:(NSOperation *)operation toHeadOfQueue:(NSOperationQueue *)queue
{
    // suspending a queue prevents it from issuing new operations; it doesn't
    // pause any already ongoing operations. So we do this to prevent a race
    // condition as we copy operations from the queue
    queue.suspended = YES;

    // create a new queue
    NSOperationQueue *mutatedQueue = [[NSOperationQueue alloc] init];

    // add the new operation at the head
    [mutatedQueue addOperation:operation];

    // copy in all the preexisting operations that haven't yet started
    for(NSOperation *operation in [queue operations])
    {
        if(!operation.isExecuting)
            [mutatedQueue addOperation:operation];
    }

    // the caller should now ensure the original queue is disposed of...
}

/* ... elsewhere ... */

NSOperationQueue *newQueue = [self addOperation:newOperation toHeadOfQueue:operationQueue];
[operationQueue release];
operationQueue = newQueue;

It seems at present that releasing a queue that is still working (as will happen to the old operation queue) doesn't cause it to cancel all operations, but that's not documented behaviour so probably not trustworthy. If you want to be really safe, key-value observe the operationCount property on the old queue and release it when it goes to zero.