Implement Queue using Stacks Easy 0 attempts
LeetCode ↗

Implement Queue using Stacks

Easy Stack&Queue LeetCode

Build a first-in-first-out (FIFO) queue using nothing but two stacks as the underlying storage. It needs to support push(x) (add an element to the back), pop() (remove the element at the front), peek() (look at the front element without removing it), and empty() (report whether the queue has anything left). The only moves allowed on the underlying stacks are the usual ones — pushing to the top, popping or peeking the top, checking the size, and checking if a stack is empty.

Calls to pop() and peek() occur only when the queue is non-empty.

Input Format
Implement the factory function implementQueueUsingStacks. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = []
operations = [["push",1],["push",2],["peek"],["pop"],["empty"],["pop"],["empty"]]
Output
[null,null,1,1,false,2,true]

Example 2

Input
constructorArgs = []
operations = [["empty"],["push",3],["pop"],["push",4],["peek"]]
Output
[true,null,3,null,4]
Constraints
  • 1 <= x <= 9
  • At most 100 calls to push, pop, peek, empty
Test Cases (2)
Case 1
Args: [[],[["push",1],["push",2],["peek"],["pop"],["empty"],["pop"],["empty"]]] Expected: [null,null,1,1,false,2,true]
Case 2
Args: [[],[["empty"],["push",3],["pop"],["push",4],["peek"]]] Expected: [true,null,3,null,4]
Topics
Stack&Queue

Approach: Two Stacks (Amortized)

Use an input stack for pushes and an output stack for pops. When the output stack is empty and a pop/peek is needed, transfer all elements from the input stack to the output stack, reversing the order. This gives amortized O(1) per operation.

javascript
function implementQueueUsingStacks() {
  const inStack = [], outStack = [];
  return {
    push(x) { inStack.push(x); },
    pop() {
      if (!outStack.length) while (inStack.length) outStack.push(inStack.pop());
      return outStack.pop();
    },
    peek() {
      if (!outStack.length) while (inStack.length) outStack.push(inStack.pop());
      return outStack[outStack.length - 1];
    },
    empty() { return !inStack.length && !outStack.length; }
  };
}

Time Complexity: Amortized O(1) per operation

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript