AlgoDaily - Two Stack Queue

Two Stack Queue (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Salesforce, Slack, Square, Spotify, Hashicorp, Toast, Airtable, Segment, C3 Ai, Opendoor, Zynga, Proofpoint, Sonos, Zuora, and New Relic.

Building a Queue with Two Stacks: A Challenge in Engineering Elegance

The Objective: Queue with Stacks

In this challenge, your task is to implement a queue using two stacks. While many programming languages offer queues through arrays or lists, we're restricting our approach to only utilize stacks.

The end result should behave like this:

JAVASCRIPT

1const tsq = new TwoStackQueue();
2tsq.push(1);
3tsq.push(2);
4tsq.pop();  // Should return 1
5tsq.pop();  // Should return 2

The Blueprint: Visualizing the Mechanics

Imagine having two stacks that work in harmony to simulate a queue. These stacks are like two components of a complex machine, each with its own specific role.

Constraints and Expectations

Let's clarify the rules of the game:

Number of Operations: The maximum number of operations won't exceed 100,000.
Value Ranges: The elements you push onto the stack will range between -1,000,000,000 and 1,000,000,000.
Time Complexity for Push: If the pop operation has a time complexity of O(n), then the push operation should be O(1). Otherwise, the time complexity for push should be O(n).
Time Complexity for Pop: If the push operation has a time complexity of O(n), then the pop operation should be O(1). Otherwise, it should be O(n).
Space Complexity: Expected to be O(n).

xxxxxxxxxx
​
 
var assert = require('assert');
​
class TwoStackQueue {
  /**
   * @param {*} value The value to push.
   */
  push(value) {}
​
  /**
   * @return {*} The popped value.
   */
  pop() {}
}
​
const tsq = new TwoStackQueue();
tsq.push(1);
tsq.push(2);
console.log(tsq.pop()); // 1
console.log(tsq.pop()); // 2
​
try {
  const tsq = new TwoStackQueue();
  tsq.push(1);
  tsq.push(2);
  tsq.pop();
  assert.equal(tsq.pop(), 2);
​

OUTPUT

Results will appear here.