Implement Stack using Queues Easy 0 attempts
LeetCode ↗

Implement Stack using Queues

Easy Stack&Queue LeetCode

Using only standard queue operations (with one or two queues), construct a stack that behaves in last-in-first-out order. It must expose push(x) (place x on top), pop() (remove and hand back the top value), top() (peek at the top value and leave it in place), and empty() (check whether anything remains). Only the standard queue operations are available to you under the hood.

Calls to pop() and top() occur only when the stack is non-empty.

Input Format
Implement the factory function implementStackUsingQueues. 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],["top"],["pop"],["empty"],["pop"],["empty"]]
Output
[null,null,2,2,false,1,true]

Example 2

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

Rotate a Single Queue

After enqueuing a new value, rotate the previous values behind it. The newest value is then at the front. The linked queue below supplies constant-time enqueue, dequeue, and front operations; push performs n-1 rotations.

javascript
function implementStackUsingQueues() {
  let head = null, tail = null, size = 0;
  function enqueue(value) {
    const node = {value, next:null};
    if (tail) tail.next = node; else head = node;
    tail = node; size++;
  }
  function dequeue() {
    const value = head.value; head = head.next; size--;
    if (!head) tail = null;
    return value;
  }
  return {
    push(x) { const oldSize = size; enqueue(x); for(let i=0;i<oldSize;i++)enqueue(dequeue()); },
    pop() { return dequeue(); },
    top() { return head.value; },
    empty() { return size === 0; }
  };
}

Time: O(n) push, O(1) pop/top/empty | Space: O(n)

Saved in this browser only. Private to you.

JavaScript