Implement Stack and Queue using Deque Easy 0 attempts
GeeksforGeeks ↗

Implement Stack and Queue using Deque

Easy Stack&Queue GeeksforGeeks

A deque (double-ended queue) lets you add or remove elements from either end, giving you addFront, addBack, removeFront, and removeBack. Using only these operations, build both a LIFO stack (with push and pop) and a FIFO queue (with enqueue and dequeue) using two independent instances of the deque structure, showing how a single double-ended container can efficiently power either behavior.

Input Format
Implement the factory function implementStackAndQueueUsingDeque. 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 = [["stack.push",1],["stack.push",2],["stack.pop"],["queue.enqueue",1],["queue.enqueue",2],["queue.dequeue"]]
Output
[null,null,2,null,null,1]

Example 2

Input
constructorArgs = []
operations = [["stack.empty"],["queue.empty"],["queue.enqueue",3],["queue.peek"],["stack.empty"]]
Output
[true,true,null,3,true]
Constraints
  • 1 <= N <= 100
  • 1 <= value <= 10^5
Test Cases (2)
Case 1
Args: [[],[["stack.push",1],["stack.push",2],["stack.pop"],["queue.enqueue",1],["queue.enqueue",2],["queue.dequeue"]]] Expected: [null,null,2,null,null,1]
Case 2
Args: [[],[["stack.empty"],["queue.empty"],["queue.enqueue",3],["queue.peek"],["stack.empty"]]] Expected: [true,true,null,3,true]
Topics
Stack&Queue

Map Stack and Queue Operations to a Deque

Use an independent deque for each structure. A stack adds and removes at the back; a queue adds at the back and removes at the front. This linked deque keeps all those operations constant-time.

javascript
function implementStackAndQueueUsingDeque() {
  function deque() {
    let head = null, tail = null;
    return {
      addBack(value) { const n={value,prev:tail,next:null}; if(tail)tail.next=n;else head=n;tail=n; },
      removeBack() { if(!tail)return undefined;const v=tail.value;tail=tail.prev;if(tail)tail.next=null;else head=null;return v; },
      removeFront() { if(!head)return undefined;const v=head.value;head=head.next;if(head)head.prev=null;else tail=null;return v; },
      front() { return head?.value; },
      back() { return tail?.value; },
      empty() { return head === null; }
    };
  }
  const s=deque(),q=deque();
  return {
    stack: { push(x){s.addBack(x);},pop(){return s.removeBack();},peek(){return s.back();},empty(){return s.empty();} },
    queue: { enqueue(x){q.addBack(x);},dequeue(){return q.removeFront();},peek(){return q.front();},empty(){return q.empty();} }
  };
}

Time: O(1) per operation | Space: O(n) for stored elements

Saved in this browser only. Private to you.

JavaScript