Dequeue Operation in DSA Typescript - Time & Space Complexity

Time Complexity: Dequeue Operation

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove an item from a dequeue (double-ended queue).

Specifically, how the time changes as the number of items grows.

Scenario Under Consideration

Analyze the time complexity of the dequeue operation removing from the front.

class Dequeue {
  items: number[] = [];

  dequeueFront(): number | undefined {
    if (this.items.length === 0) return undefined;
    return this.items.shift();
  }
}
    

This code removes the first item from the dequeue array.

Identify Repeating Operations

Look for loops or repeated steps inside the dequeueFront method.

• Primary operation: Removing the first item using shift().
• How many times: Each call removes one item, but internally shift() moves all other items one step forward.

How Execution Grows With Input

When the dequeue has more items, shift() moves more elements.

Input Size (n)	Approx. Operations
10	About 9 moves
100	About 99 moves
1000	About 999 moves

Pattern observation: The number of moves grows roughly the same as the number of items.

Final Time Complexity

Time Complexity: O(n)

This means removing from the front takes longer as the dequeue grows because items must shift.

Common Mistake

[X] Wrong: "Removing from the front is always fast and constant time like popping from the end."

[OK] Correct: In arrays, removing the first item shifts all others, so it takes time proportional to the number of items.

Interview Connect

Understanding this helps you choose the right data structure for fast front removals, a key skill in coding interviews.

Self-Check

"What if we used a linked list instead of an array for the dequeue? How would the time complexity of removing from the front change?"

Practice

1. What is the main difference between a dequeue and a queue?

easy

A. A dequeue allows insertion and deletion from both ends.

B. A dequeue only allows insertion at the rear.

C. A dequeue only allows deletion from the front.

D. A dequeue is a fixed size data structure.

Solution

1. Step 1: Understand queue operations

   A queue allows insertion at the rear and deletion from the front only.

2. Step 2: Understand dequeue operations

   A dequeue allows insertion and deletion at both front and rear ends.

3. Final Answer:

   A dequeue allows insertion and deletion from both ends. -> Option A

4. Quick Check:

   Dequeue = Both ends operations [OK]

Hint: Dequeue = Double-ended queue, both ends allowed [OK]

Common Mistakes:

• Thinking dequeue is same as queue
• Assuming insertion only at rear
• Confusing dequeue with stack

2. Which of the following is the correct TypeScript method to add an element at the front of a dequeue implemented as an array?

easy

A. dequeue.pushFront(element);

B. dequeue.unshift(element);

C. dequeue.addFirst(element);

D. dequeue.insertFront(element);

Solution

1. Step 1: Recall array methods for front insertion

   In TypeScript/JavaScript, unshift() adds element at the front of an array.

2. Step 2: Check other options

   Methods like pushFront, addFirst, insertFront do not exist in standard arrays.

3. Final Answer:

   dequeue.unshift(element); -> Option B

4. Quick Check:

   Array front insert = unshift() [OK]

Hint: Use unshift() to add at front in arrays [OK]

Common Mistakes:

• Using push() instead of unshift()
• Assuming pushFront() exists
• Confusing with linked list methods

3. Consider this TypeScript code using an array as a dequeue:

let dequeue = [10, 20, 30];
dequeue.pop();
dequeue.unshift(5);
console.log(dequeue);

What is the output?

medium

A. [5, 10, 20]

B. [5, 10, 20, 30]

C. [10, 20, 30, 5]

D. [10, 20]

Solution

1. Step 1: Execute pop()

   pop() removes last element 30, so array becomes [10, 20].

2. Step 2: Execute unshift(5)

   unshift(5) adds 5 at front, array becomes [5, 10, 20].

3. Final Answer:

   [5, 10, 20] -> Option A

4. Quick Check:

   pop removes last, unshift adds front [OK]

Hint: pop removes last, unshift adds front [OK]

Common Mistakes:

• Assuming pop removes front
• Thinking unshift adds at end
• Confusing array order after operations

4. The following TypeScript code tries to remove an element from the front of a dequeue implemented as an array:

let dequeue = [1, 2, 3];
dequeue.removeFront();
console.log(dequeue);

What is the issue and how to fix it?

medium

A. removeFront() works only on linked lists; convert array to linked list.

B. removeFront() removes last element; use pop() instead.

C. removeFront() is not a valid method; use shift() instead.

D. No issue; code runs correctly.

Solution

1. Step 1: Identify invalid method

   Arrays in TypeScript do not have removeFront() method; this causes a runtime error.

2. Step 2: Use correct method for front removal

   shift() removes the first element from an array correctly.

3. Final Answer:

   removeFront() is not a valid method; use shift() instead. -> Option C

4. Quick Check:

   Front removal in arrays = shift() [OK]

Hint: Use shift() to remove front element in arrays [OK]

Common Mistakes:

• Using non-existent removeFront() method
• Confusing pop() with front removal
• Thinking arrays have linked list methods

5. You have a dequeue implemented as an array: let dq = [1, 2, 3, 4];. You perform these operations:

dq.pop();
dq.unshift(0);
dq.push(5);
dq.shift();
console.log(dq);

What is the final state of the dequeue?

hard

A. [0, 1, 2, 3, 5]

B. [2, 3, 4, 5]

C. [1, 2, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Execute pop()

   pop() removes last element 4, dq becomes [1, 2, 3].

2. Step 2: Execute unshift(0)

   unshift(0) adds 0 at front, dq becomes [0, 1, 2, 3].

3. Step 3: Execute push(5)

   push(5) adds 5 at end, dq becomes [0, 1, 2, 3, 5].

4. Step 4: Execute shift()

   shift() removes first element 0, dq becomes [1, 2, 3, 5].

5. Final Answer:

   [1, 2, 3, 5] -> Option D

6. Quick Check:

   pop removes end, unshift adds front, push adds end, shift removes front [OK]

Hint: Track each operation stepwise on array [OK]

Common Mistakes:

• Forgetting shift removes front element
• Mixing order of operations
• Assuming unshift adds at end