Do you know when we should use two stacks to implement a queue?


  • 9

    I was asked in the internship interview of a company two years ago.

    The application for this implementation is to separate read & write of a queue in multi-processing. One of the stack is for read, and another is for write. They only interfere each other when the former one is full or latter is empty.

    This is not only a trick. :)


  • 0
    L

    ??Can you explain how the two stacks work? In fact, i don't understand.Because in my solution for this problem, there is always one stack is empty, so how can realize what you said about"one stack is for read, and another one is for write"?


  • 2

    When there's only one thread doing the read/write operation to the stack, there will always one stack empty. However, in a multi-thread application, if we have only one queue, for thread-safety, either read or write will lock the whole queue. In the two stack implementation, as long as the second stack is not empty, push operation will not lock the stack for pop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.