Implement Stack using two Queues with multithreading
Filed under Salesforce
Free read 3 of 3Determine whether push or pop should be the expensive operation, and confirm the concurrency requirements for the multithreading discussion.
The question
Implement a Last-In-First-Out (LIFO) stack using only two queues. Additionally, discuss how to ensure thread-safety and concurrency when multiple threads access the stack.
Constraints
- Use only standard Queue operations (enqueue, dequeue, isEmpty, size).
- Operations should be either push-heavy or pop-heavy depending on the design.
- Thread safety must prevent race conditions during concurrent modifications.
Examples
- Input
- push(1), push(2), top(), pop(), top()
- Output
- 2, 2, 1
- Why
- Elements are pushed sequentially. The second element 2 is at the top of the stack, so top() returns 2, pop() removes 2, and the new top becomes 1.
Approach
Determine whether push or pop should be the expensive operation, and confirm the concurrency requirements for the multithreading discussion.
Use standard queue structures without synchronization, focusing solely on the single-threaded algorithmic translation of stack operations.
Make push $O(1)$ by pushing to the active queue, or make pop $O(1)$ by transferring elements. For multithreading, wrap queue references inside thread-safe mutex locks or use thread-safe queue wrappers.
Empty stack pop/top calls, single element operations, and high contention under heavy concurrent thread access.
Tips
- What they are testing: Tests verify correct LIFO ordering across multiple pushes and pops, and handling of underflow when popping from an empty stack. Multithreading tests check for deadlocks and race conditions.
- Common mistake: A common mistake is forgetting to synchronize queue operations using locks or concurrent queue structures, leading to data corruption in a multithreaded environment.
Related Salesforce questions
Collected from public candidate posts and coding forums. Updated Nov 2026.