Enqueue Operation in DSA Go - 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 item at the end?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Enqueue adds an element to the end of the queue
func (q *Queue) Enqueue(value int) {
    q.items = append(q.items, value)
}
    

This code adds a new value to the end of a slice representing the queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Appending an element to the slice backing the queue.
• How many times: Once per enqueue call.

How Execution Grows With Input

Appending usually takes the same small amount of work, but sometimes it needs extra steps to grow the slice.

Input Size (n)	Approx. Operations
10	About 1 operation per enqueue
100	Mostly 1 operation, occasionally more when resizing
1000	Mostly 1 operation, occasionally more when resizing

Pattern observation: Most enqueues are quick, but some take longer due to resizing the underlying array.

Final Time Complexity

Time Complexity: O(1) amortized

This means each enqueue usually takes the same small time, but sometimes a bit longer when the queue grows.

Common Mistake

[X] Wrong: "Every enqueue takes longer as the queue gets bigger because it copies all elements each time."

[OK] Correct: The slice only resizes occasionally, so most enqueues are fast. The extra copying happens rarely, spreading the cost over many operations.

Interview Connect

Understanding enqueue time helps you explain how queues work efficiently in real programs and shows you know how dynamic arrays behave under the hood.

Self-Check

"What if we used a linked list instead of a slice 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. Removes an element from the front of the queue

B. Checks if the queue is empty

C. Adds an element to the end of the queue

D. Returns the size of the queue

Solution

1. Step 1: Understand the queue structure

   A queue works like a line where new elements join at the end.

2. Step 2: Define enqueue operation

   Enqueue means adding a new element to the back of the queue.

3. Final Answer:

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

4. Quick Check:

   Enqueue = Add at end [OK]

Hint: Enqueue means add at the back of the queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue
• Thinking enqueue removes elements
• Mixing enqueue with checking size

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

easy

A. q.Enqueue(5)

B. q.enqueue(5)

C. enqueue(q, 5)

D. q.add(5)

Solution

1. Step 1: Identify method naming conventions in Go

   Methods in Go are usually capitalized if exported, so Enqueue is correct.

2. Step 2: Check method call on queue instance

   Calling q.Enqueue(5) means calling method Enqueue on queue q with argument 5.

3. Final Answer:

   q.Enqueue(5) -> Option A

4. Quick Check:

   Method call with capital Enqueue = q.Enqueue(5) [OK]

Hint: Use capitalized method names for exported functions in Go [OK]

Common Mistakes:

• Using lowercase method names incorrectly
• Calling enqueue as a standalone function
• Using wrong method name like add

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

package main

import "fmt"

type Queue struct {
    items []int
}

func (q *Queue) Enqueue(val int) {
    q.items = append(q.items, val)
}

func (q *Queue) Print() {
    for _, v := range q.items {
        fmt.Print(v, " -> ")
    }
    fmt.Println("null")
}

func main() {
    q := Queue{}
    q.Enqueue(10)
    q.Enqueue(20)
    q.Enqueue(30)
    q.Print()
}

medium

A. Compilation error

B. 10 -> 20 -> 30 -> null

C. null

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Understand enqueue implementation

   Enqueue appends new values at the end of the slice, so order is preserved as inserted.

2. Step 2: Trace the Print method output

   Print prints all items in order separated by ' -> ' and ends with 'null'.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option B

4. Quick Check:

   Enqueue appends, so output is 10 -> 20 -> 30 -> null [OK]

Hint: Enqueue appends at end, print shows order inserted [OK]

Common Mistakes:

• Thinking enqueue adds at front
• Confusing print order
• Assuming code has errors

4. Identify the error in the following Go code for enqueue operation:

package main

import "fmt"

type Queue struct {
    items []int
}

func (q Queue) Enqueue(val int) {
    q.items = append(q.items, val)
}

func main() {
    q := Queue{}
    q.Enqueue(5)
    fmt.Println(q.items)
}

medium

A. Enqueue method should have pointer receiver to modify queue

B. items slice should be initialized with make

C. fmt.Println is not imported

D. Append cannot be used on slices

Solution

1. Step 1: Check method receiver type

   The Enqueue method uses a value receiver, so changes to q.items do not affect original queue.

2. Step 2: Understand pointer receiver necessity

   To modify the original queue, Enqueue must have pointer receiver (q *Queue).

3. Final Answer:

   Enqueue method should have pointer receiver to modify queue -> Option A

4. Quick Check:

   Pointer receiver needed to modify struct [OK]

Hint: Use pointer receiver to modify struct fields [OK]

Common Mistakes:

• Using value receiver and expecting changes
• Forgetting to import fmt (not main error here)
• Thinking append can't be used on slices

5. You want to implement a queue using a linked list in Go. Which step is essential in the Enqueue operation to maintain the queue correctly?

hard

A. Add new node at the head and do not update head pointer

B. Add new node at the head and update tail pointer

C. Add new node at the tail but do not update tail pointer

D. Add new node at the tail and update tail pointer

Solution

1. Step 1: Understand linked list queue structure

   Queue adds new elements at the tail (end) and removes from head (front).

2. Step 2: Enqueue operation details

   To enqueue, add new node at tail and update tail pointer to new node to keep track.

3. Final Answer:

   Add new node at the tail and update tail pointer -> Option D

4. Quick Check:

   Enqueue adds at tail and updates tail pointer [OK]

Hint: Enqueue adds at tail and updates tail pointer [OK]

Common Mistakes:

• Adding at head instead of tail
• Not updating tail pointer after enqueue
• Confusing head and tail roles