Dequeue Operation in DSA Go

Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway where people can enter or exit from either door at the front or the back.

front -> [1] -> [2] -> [3] -> back
↑ dequeue ends at both sides

Dry Run Walkthrough

Input: dequeue with elements 1 -> 2 -> 3, perform dequeue from front and then from back

Goal: Remove one element from the front and one from the back, showing the structure after each removal

Step 1: remove element from front

front -> [2] -> [3] -> back

Why: Removing from front updates the front pointer to the next element

Step 2: remove element from back

front -> [2] -> back

Why: Removing from back updates the back pointer to the previous element

Result:

front -> [2] -> back

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
	prev  *Node
}

type Dequeue struct {
	front *Node
	back  *Node
}

func (d *Dequeue) EnqueueBack(val int) {
	node := &Node{value: val}
	if d.back == nil {
		d.front = node
		d.back = node
		return
	}
	d.back.next = node
	node.prev = d.back
	d.back = node
}

func (d *Dequeue) DequeueFront() (int, bool) {
	if d.front == nil {
		return 0, false
	}
	val := d.front.value
	if d.front == d.back {
		d.front = nil
		d.back = nil
	} else {
		d.front = d.front.next
		d.front.prev = nil
	}
	return val, true
}

func (d *Dequeue) DequeueBack() (int, bool) {
	if d.back == nil {
		return 0, false
	}
	val := d.back.value
	if d.front == d.back {
		d.front = nil
		d.back = nil
	} else {
		d.back = d.back.prev
		d.back.next = nil
	}
	return val, true
}

func (d *Dequeue) Print() {
	curr := d.front
	for curr != nil {
		fmt.Printf("%d", curr.value)
		if curr.next != nil {
			fmt.Print(" -> ")
		}
		curr = curr.next
	}
	fmt.Println(" -> null")
}

func main() {
	d := &Dequeue{}
	d.EnqueueBack(1)
	d.EnqueueBack(2)
	d.EnqueueBack(3)

	fmt.Print("Initial dequeue: ")
	d.Print()

	valFront, okFront := d.DequeueFront()
	if okFront {
		fmt.Printf("Removed from front: %d\n", valFront)
		fmt.Print("After removing front: ")
		d.Print()
	}

	valBack, okBack := d.DequeueBack()
	if okBack {
		fmt.Printf("Removed from back: %d\n", valBack)
		fmt.Print("After removing back: ")
		d.Print()
	}
}

if d.front == nil { return 0, false }

check if dequeue is empty before removing front

if d.front == d.back { d.front = nil; d.back = nil } else { d.front = d.front.next; d.front.prev = nil }

update front pointer and disconnect old front node

if d.back == nil { return 0, false }

check if dequeue is empty before removing back

if d.front == d.back { d.front = nil; d.back = nil } else { d.back = d.back.prev; d.back.next = nil }

update back pointer and disconnect old back node

Output

Initial dequeue: 1 -> 2 -> 3 -> null

Removed from front: 1

After removing front: 2 -> 3 -> null

Removed from back: 3

After removing back: 2 -> null

Complexity Analysis

Time: O(1) because removing from front or back only changes a few pointers without traversal

Space: O(n) for storing n elements in the dequeue nodes

vs Alternative: Compared to arrays where removing front requires shifting all elements O(n), dequeue removal is faster O(1)

Edge Cases

empty dequeue

removal returns false and no change happens

DSA Go

if d.front == nil { return 0, false }

single element dequeue

removal empties the dequeue by setting front and back to nil

DSA Go

if d.front == d.back { d.front = nil; d.back = nil }

When to Use This Pattern

When a problem needs fast removal or addition from both ends, use dequeue operations because they allow O(1) insertions and deletions at front and back.

Common Mistakes

Mistake: Not updating the prev pointer of the new front node after removing from front
Fix: Set d.front.prev = nil after moving front pointer forward

Mistake: Not updating the next pointer of the new back node after removing from back
Fix: Set d.back.next = nil after moving back pointer backward

Summary

Removes elements from either the front or back of a dequeue efficiently.

Use when you need to remove items quickly from both ends without shifting elements.

The key is updating pointers carefully to keep the structure connected and consistent.

Practice

1. What is a dequeue in data structures?

easy

A. A double-ended queue allowing insertion and deletion at both ends

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

C. A stack that allows insertion and deletion only at one end

D. A list that only supports random access

Solution

1. Step 1: Understand the definition of dequeue

   A dequeue is a data structure where elements can be added or removed from both the front and the rear ends.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, which restrict operations to one end, dequeue supports both ends.

3. Final Answer:

   A double-ended queue allowing insertion and deletion at both ends -> Option A

4. Quick Check:

   Dequeue = double-ended queue [OK]

Hint: Remember: Dequeue means double-ended queue [OK]

Common Mistakes:

• Confusing dequeue with stack or simple queue
• Thinking dequeue only allows operations at one end
• Mixing dequeue with random access lists

2. Which of the following is the correct Go syntax to create an empty dequeue using a slice?

easy

A. var dq []int = make([]int, 0)

B. dq := []int{nil}

C. var dq int = []{}

D. dq := make([]int, -1)

Solution

1. Step 1: Understand slice creation in Go

   To create an empty slice, use make with length 0, like make([]int, 0).

2. Step 2: Check each option

   var dq []int = make([]int, 0) correctly creates an empty int slice. dq := []int{nil} uses nil inside slice literal which is invalid. var dq int = []{} has wrong type assignment. dq := make([]int, -1) tries negative length which is invalid.

3. Final Answer:

   var dq []int = make([]int, 0) -> Option A

4. Quick Check:

   Empty slice = make([]int, 0) [OK]

Hint: Use make([]type, 0) for empty slices in Go [OK]

Common Mistakes:

• Using nil inside slice literal
• Assigning wrong types
• Using negative length in make

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

package main
import "fmt"
func main() {
  dq := []int{10, 20, 30}
  // Remove from front
  dq = dq[1:]
  // Add 40 at rear
  dq = append(dq, 40)
  fmt.Println(dq)
}

medium

A. [40 20 30]

B. [10 20 30 40]

C. [20 30 40]

D. [30 40]

Solution

1. Step 1: Remove element from front

   dq = dq[1:] removes the first element (10), so dq becomes [20, 30].

2. Step 2: Add element at rear

   append(dq, 40) adds 40 at the end, so dq becomes [20, 30, 40].

3. Final Answer:

   [20 30 40] -> Option C

4. Quick Check:

   Remove front + append rear = [20 30 40] [OK]

Hint: Slice from 1 removes front; append adds rear [OK]

Common Mistakes:

• Forgetting slice removes front element
• Appending at wrong position
• Misreading slice syntax

4. Identify the error in the following Go code that tries to remove an element from the rear of a dequeue represented by a slice:

package main
import "fmt"
func main() {
  dq := []int{5, 10, 15}
  dq = dq[:len(dq)]
  fmt.Println(dq)
}

medium

A. No error; code correctly removes rear element

B. Runtime panic due to invalid slice bounds

C. Syntax error in slice expression

D. Slice operation does not remove last element; length unchanged

Solution

1. Step 1: Analyze slice operation dq[:len(dq)]

   This slice keeps all elements from start to length, so no element is removed.

2. Step 2: Understand how to remove last element

   To remove last element, slice should be dq[:len(dq)-1].

3. Final Answer:

   Slice operation does not remove last element; length unchanged -> Option D

4. Quick Check:

   dq[:len(dq)] keeps all elements [OK]

Hint: Use dq[:len(dq)-1] to remove last element [OK]

Common Mistakes:

• Using dq[:len(dq)] expecting removal
• Off-by-one errors in slicing
• Confusing slice length with index

5. Given a dequeue implemented as a slice in Go, which sequence of operations will correctly remove an element from the front and add an element at the front, resulting in [99 30 40] from initial [20 30 40]? Choose the correct code snippet:

package main
import "fmt"
func main() {
  dq := []int{20, 30, 40}
  // Your code here
  fmt.Println(dq)
}

hard

A. dq = append(dq, 99)
dq = dq[1:]

B. dq = dq[1:]
dq = append([]int{99}, dq...)

C. dq = append(dq, 99)
dq = append([]int{99}, dq...)

D. dq = dq[:len(dq)-1]
dq = append([]int{99}, dq...)

Solution

1. Step 1: Remove element from front

   dq = dq[1:] removes the first element (20), so dq becomes [30, 40].

2. Step 2: Add 99 at front

   dq = append([]int{99}, dq...) adds 99 at the front, resulting in [99, 30, 40].

3. Step 3: Verify final slice

   After these operations, dq is [99, 30, 40], which matches the expected result.

4. Final Answer:

   dq = dq[1:] dq = append([]int{99}, dq...) -> Option B

5. Quick Check:

   Remove front + add front = dq = dq[1:] dq = append([]int{99}, dq...) [OK]

Hint: Add front with append([]int{val}, dq...) [OK]

Common Mistakes:

• Removing wrong element before adding front
• Appending at rear instead of front
• Confusing slice operations order