Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Two Stack Queue (Main Thread)

Here is the interview question prompt, presented for reference.

Can you implement a queue using two stacks?

Many languages have queues modeled using arrays or lists, so we can mimic this constraint by only allowing those data structures to enqueue to the end and dequeue from the start.

The following method should work.

const tsq = new TwoStackQueue();
tsq.push(1);
tsq.push(2);
tsq.pop();  // 1
tsq.pop();  // 2

Constraints

  • The number of operations will be <= 100000
  • The values to be pushed will be between -1000000000 and 1000000000
  • Expected time complexity for push operation : O(1) if pop operation is O(n), else O(n)
  • Expected time complexity for pop operation : O(1) if push operation is O(n), else O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked over 3 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Two Stack Queue.

Aishwarya Das Commented on Apr 01, 2021:

Test case 3 is wrong

Jake from AlgoDaily Commented on Apr 01, 2021:

Hi Aishwarya,

For which language?

Aishwarya Das Commented on Apr 01, 2021:

For python

Aishwarya Das Commented on Apr 02, 2021:

According to test 3
tsq = TwoStackQueue(); tsq.push(1); tsq.push(2); tsq.pop(); tsq.push(3); tsq.pop(); assert tsq.pop() == 1

tsq should pop 1 but it pop 3 since the operation order is push,push,pop,push,pop,pop