Double Ended Queue Deque in DSA Go

Mental Model

A deque lets you add or remove items from both ends easily, like a line where you can join or leave from front or back.

Analogy: Imagine a train with doors at both front and back. Passengers can get on or off from either end without walking through the whole train.

front -> [ ] -> [ ] -> [ ] -> back

Dry Run Walkthrough

Input: Start with empty deque, then add 1 at front, add 2 at back, add 3 at front, remove from back

Goal: Show how elements are added and removed from both ends and how the deque changes

Step 1: Add 1 at front

front -> [1] -> back

Why: Adding first element sets the deque with one item

Step 2: Add 2 at back

front -> [1] -> [2] -> back

Why: Adding at back appends element after the last

Step 3: Add 3 at front

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

Why: Adding at front inserts element before the first

Step 4: Remove from back

front -> [3] -> [1] -> back

Why: Removing from back deletes the last element

Result:

front -> [3] -> [1] -> back

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Deque struct {
	items []int
}

func (d *Deque) AddFront(val int) {
	d.items = append([]int{val}, d.items...)
}

func (d *Deque) AddBack(val int) {
	d.items = append(d.items, val)
}

func (d *Deque) RemoveFront() (int, bool) {
	if len(d.items) == 0 {
		return 0, false
	}
	val := d.items[0]
	d.items = d.items[1:]
	return val, true
}

func (d *Deque) RemoveBack() (int, bool) {
	if len(d.items) == 0 {
		return 0, false
	}
	val := d.items[len(d.items)-1]
	d.items = d.items[:len(d.items)-1]
	return val, true
}

func (d *Deque) String() string {
	if len(d.items) == 0 {
		return "front -> back"
	}
	res := "front -> "
	for i, v := range d.items {
		res += fmt.Sprintf("[%d]", v)
		if i != len(d.items)-1 {
			res += " -> "
		}
	}
	res += " -> back"
	return res
}

func main() {
	d := Deque{}
	d.AddFront(1) // add 1 at front
	fmt.Println(d.String())
	d.AddBack(2) // add 2 at back
	fmt.Println(d.String())
	d.AddFront(3) // add 3 at front
	fmt.Println(d.String())
	removed, ok := d.RemoveBack() // remove from back
	if ok {
		fmt.Printf("Removed from back: %d\n", removed)
	}
	fmt.Println(d.String())
}

d.items = append([]int{val}, d.items...)

insert new value at front by creating new slice with val first

d.items = append(d.items, val)

append new value at back by adding to end of slice

val := d.items[0] d.items = d.items[1:]

remove front element by slicing off first item

val := d.items[len(d.items)-1] d.items = d.items[:len(d.items)-1]

remove back element by slicing off last item

Output

front -> [1] -> back

front -> [1] -> [2] -> back

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

Removed from back: 2

front -> [3] -> [1] -> back

Complexity Analysis

Time: O(n) for AddFront because inserting at front requires shifting all elements; O(1) for AddBack and removals because they operate at slice ends

Space: O(n) because the deque stores all elements in a slice

vs Alternative: Compared to linked list deque, slice AddFront is slower due to shifting, but AddBack and removals are fast; linked list has O(1) for both ends but more memory overhead

Edge Cases

empty deque removal

RemoveFront or RemoveBack returns false and zero value without error

DSA Go

if len(d.items) == 0 {
	return 0, false
}

single element deque

Removing front or back empties the deque correctly

DSA Go

d.items = d.items[1:] or d.items = d.items[:len(d.items)-1]

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, use a deque to handle front and back operations cleanly.

Common Mistakes

Mistake: Using append at front without creating a new slice causes wrong order or overwriting
Fix: Always create a new slice with the new element first, then append the old slice

Mistake: Not checking for empty deque before removing causes runtime errors
Fix: Check length before removing and return safe values if empty

Summary

A deque lets you add or remove items from both front and back ends.

Use it when you need flexible queue behavior from both ends.

Remember adding at front in slices costs shifting, so be mindful of performance.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A data structure where elements can be added or removed from both ends

B. A queue where elements can only be added at the rear

C. A stack where elements can only be added or removed from the top

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion from both front and rear ends, unlike a queue or stack.

2. Step 2: Compare with other data structures

   Queue allows insertion at rear and deletion at front; stack allows insertion and deletion only at one end.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque allows random access
• Assuming insertion only at one end

2. Which of the following is the correct way to declare a deque using Go's container/list package?

easy

A. var d []int

B. d := list.New()

C. d := make(deque, 0)

D. var d map[int]int

Solution

1. Step 1: Recall Go's deque implementation

   Go does not have a built-in deque type but container/list can be used as a double-ended queue.

2. Step 2: Check syntax for creating a new list

   list.New() returns a pointer to a new doubly linked list, suitable for deque operations.

3. Final Answer:

   d := list.New() -> Option B

4. Quick Check:

   Use list.New() for deque in Go [OK]

Hint: Use list.New() to create a deque in Go [OK]

Common Mistakes:

• Using slice instead of list for deque
• Trying to make a deque type directly
• Confusing map with deque

3. What will be the output of the following Go code using container/list as a deque?

package main
import (
  "container/list"
  "fmt"
)
func main() {
  d := list.New()
  d.PushBack(10)
  d.PushFront(20)
  d.PushBack(30)
  for e := d.Front(); e != nil; e = e.Next() {
    fmt.Print(e.Value, " ")
  }
}

medium

A. 30 10 20

B. 10 20 30

C. 20 10 30

D. 20 30 10

Solution

1. Step 1: Trace the Push operations on deque

   PushBack(10) adds 10 at rear; PushFront(20) adds 20 at front; PushBack(30) adds 30 at rear.

2. Step 2: Traverse from front to back

   Elements order: 20 (front), 10 (middle), 30 (rear).

3. Final Answer:

   20 10 30 -> Option C

4. Quick Check:

   Front to back traversal = 20 10 30 [OK]

Hint: PushFront adds front, PushBack adds rear [OK]

Common Mistakes:

• Mixing order of PushFront and PushBack
• Assuming PushBack adds to front
• Confusing traversal direction

4. Identify the error in this Go code snippet using container/list as a deque:

package main
import (
  "container/list"
  "fmt"
)
func main() {
  d := list.New()
  d.PushFront(1)
  d.Remove(d.Back())
  fmt.Println(d.Back().Value)
}

medium

A. Using PushFront instead of PushBack

B. Not initializing the list with make()

C. Printing d.Back().Value without converting to string

D. Calling Remove on d.Back() before checking if d.Back() is nil

Solution

1. Step 1: Understand Remove and Back usage

   d.Remove(d.Back()) removes the last element; after removal, d.Back() may be nil if list is empty.

2. Step 2: Check the print statement

   fmt.Println(d.Back().Value) accesses Value of d.Back() without checking if d.Back() is nil, causing runtime panic if nil.

3. Final Answer:

   Calling Remove on d.Back() before checking if d.Back() is nil -> Option D

4. Quick Check:

   Check nil before accessing Back() after Remove [OK]

Hint: Check nil after Remove before accessing Back() [OK]

Common Mistakes:

• Ignoring nil check after removal
• Confusing PushFront and PushBack
• Thinking fmt.Println needs string conversion

5. You want to implement a sliding window maximum using a deque in Go. Which deque operation sequence correctly maintains the window elements in decreasing order from front to rear?

// Assume d is a deque of indices
for i := 0; i < len(nums); i++ {
  for d.Len() > 0 && nums[d.Back().Value.(int)] <= nums[i] {
    d.Remove(d.Back())
  }
  d.PushBack(i)
  if d.Front().Value.(int) <= i - k {
    d.Remove(d.Front())
  }
}

hard

A. Remove from back while current element is greater or equal, then add current index at back

B. Remove from front while current element is smaller, then add current index at front

C. Add current index at front without removals

D. Remove from back while current element is smaller, then add current index at front

Solution

1. Step 1: Understand sliding window max logic

   We remove smaller or equal elements from back to keep deque decreasing, then add current index at back.

2. Step 2: Remove indices out of window from front

   If front index is out of current window (i - k), remove it from front to maintain window size.

3. Final Answer:

   Remove from back while current element is greater or equal, then add current index at back -> Option A

4. Quick Check:

   Sliding window max uses back removals and back insertions [OK]

Hint: Remove smaller from back, add new at back for max window [OK]

Common Mistakes:

• Removing from front instead of back for smaller elements
• Adding new elements at front incorrectly
• Not removing out-of-window indices