Enqueue Operation in DSA C++ - Time & Space Complexity

Time Complexity: Enqueue Operation

O(1)

Understanding Time Complexity

We want to understand how the time to add an item to a queue changes as the queue grows.

How much work does it take to put a new element at the end?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void enqueue(int value) {
    if (rear == size - 1) {
        // Queue is full
        return;
    }
    rear++;
    arr[rear] = value;
}
    

This code adds a new value to the end of a queue implemented with an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Assigning the new value to the array at the rear index.
• How many times: Exactly once per enqueue call.

How Execution Grows With Input

Adding one item always takes the same steps, no matter how big the queue is.

Input Size (n)	Approx. Operations
10	1 assignment
100	1 assignment
1000	1 assignment

Pattern observation: The work stays the same even if the queue grows larger.

Final Time Complexity

Time Complexity: O(1)

This means adding an item takes a fixed amount of time, no matter how many items are already in the queue.

Common Mistake

[X] Wrong: "Enqueue takes longer as the queue gets bigger because it has to move all items."

[OK] Correct: The enqueue operation just places the new item at the next free spot; it does not move existing items.

Interview Connect

Knowing that enqueue is a quick, constant-time operation helps you explain efficient queue usage in real applications.

Self-Check

"What if we used a linked list instead of an array for the queue? How would the time complexity of enqueue change?"

Practice

1. What does the enqueue operation do in a queue data structure?

easy

A. Returns the size of the queue

B. Removes an element from the front of the queue

C. Checks if the queue is empty

D. Adds an element to the end of the queue

Solution

1. Step 1: Understand the queue structure

   A queue works like a line where elements are added at the back and removed from the front.

2. Step 2: Define the enqueue operation

   Enqueue means adding a new element to the end of the queue to wait its turn.

3. Final Answer:

   Adds an element to the end of the queue -> Option D

4. Quick Check:

   Enqueue = Add at end [OK]

Hint: Enqueue always adds at the back of the queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue (removal)
• Thinking enqueue removes elements
• Mixing enqueue with checking queue size

2. Which of the following is the correct syntax to enqueue an element 5 into a queue named q in C++ STL?

easy

A. q.push(5);

B. q.add(5);

C. q.enqueue(5);

D. q.insert(5);

Solution

1. Step 1: Recall C++ STL queue methods

   The standard queue in C++ uses push() to add elements at the back.

2. Step 2: Match the correct method

   enqueue is not a method in STL queue; push is used instead.

3. Final Answer:

   q.push(5); -> Option A

4. Quick Check:

   STL queue uses push() to enqueue [OK]

Hint: Use push() to add elements in C++ STL queue [OK]

Common Mistakes:

• Using enqueue() which is not in STL queue
• Using add() or insert() which are not queue methods
• Confusing push() with pop()

3. What will be the output of the following C++ code snippet?

std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.pop();
std::cout << q.front();

medium

A. 10

B. Compilation error

C. 20

D. 30

Solution

1. Step 1: Trace the enqueue operations

   Elements 10, 20, 30 are added in order: queue = [10, 20, 30]

2. Step 2: Apply the dequeue operation

   pop() removes the front element 10, so queue = [20, 30]

3. Step 3: Check the front element

   front() now returns 20, the new front.

4. Final Answer:

   20 -> Option C

5. Quick Check:

   After pop, front = 20 [OK]

Hint: pop removes front; front() shows new front [OK]

Common Mistakes:

• Assuming front remains 10 after pop
• Confusing pop with removing from back
• Expecting output 30 instead of 20

4. Identify the error in the following code that tries to enqueue an element into a queue:

std::queue<int> q;
q.enqueue(15);

medium

A. Missing #include <queue>

B. enqueue is not a member function of std::queue

C. Queue must be initialized with size

D. Cannot enqueue integer values

Solution

1. Step 1: Check std::queue methods

   std::queue does not have an enqueue method; it uses push to add elements.

2. Step 2: Identify the error cause

   Calling enqueue causes a compilation error because the method does not exist.

3. Final Answer:

   enqueue is not a member function of std::queue -> Option B

4. Quick Check:

   Use push() not enqueue() in std::queue [OK]

Hint: std::queue uses push(), not enqueue() [OK]

Common Mistakes:

• Assuming enqueue() exists in std::queue
• Thinking queue needs size at initialization
• Believing integers cannot be enqueued

5. You have a queue initially empty. You perform these operations:

enqueue(1)
enqueue(2)
dequeue()
enqueue(3)
dequeue()
enqueue(4)

What is the final state of the queue (front to back)?

hard

A. 3 -> 4 -> null

B. 2 -> 3 -> 4 -> null

C. 1 -> 3 -> 4 -> null

D. 4 -> null

Solution

1. Step 1: Perform operations step-by-step

   Start empty: []
   enqueue(1): [1]
   enqueue(2): [1, 2]
   dequeue(): removes 1 -> [2]
   enqueue(3): [2, 3]
   dequeue(): removes 2 -> [3]
   enqueue(4): [3, 4]

2. Step 2: Write final queue state

   Queue front is 3, then 4, then null (end).

3. Final Answer:

   3 -> 4 -> null -> Option A

4. Quick Check:

   After operations, queue = 3,4 [OK]

Hint: Track each enqueue/dequeue step carefully [OK]

Common Mistakes:

• Forgetting to remove elements on dequeue
• Mixing order of elements after operations
• Assuming dequeue removes from back