Double Ended Queue Deque in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Deque operations sequence

What is the printed state of the deque after performing these operations in order?

Operations:
1. Add 10 to the front
2. Add 20 to the back
3. Add 30 to the front
4. Remove from the back
5. Add 40 to the back

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func main() {
	deque := list.New()
	deque.PushFront(10)   // Step 1
	deque.PushBack(20)    // Step 2
	deque.PushFront(30)   // Step 3
	deque.Remove(deque.Back()) // Step 4
	deque.PushBack(40)    // Step 5

	for e := deque.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " -> ")
	}
	fmt.Print("null")
}

A 30 -> 10 -> 40 -> null

B 10 -> 30 -> 40 -> null

C 30 -> 20 -> 40 -> null

D 10 -> 20 -> 40 -> null

💡 Hint

Remember that PushFront adds to the front and PushBack adds to the back. Removing from the back removes the last element.

Step 1 adds 10 front: 10 Step 2 adds 20 back: 10 -> 20 Step 3 adds 30 front: 30 -> 10 -> 20 Step 4 removes back (20): 30 -> 10 Step 5 adds 40 back: 30 -> 10 -> 40

🧠 Conceptual

intermediate

Deque behavior on empty removal

What happens if you try to remove an element from the front of an empty deque implemented using Go's container/list?

A It panics with runtime error

B It returns zero value of the element type

C It returns nil and does nothing, no error is raised

D It blocks until an element is available

💡 Hint

Check the behavior of list.Remove when passed nil.

Calling deque.Remove(deque.Front()) on an empty deque: Front() returns nil, and Remove(nil) panics with a nil pointer dereference when accessing e.list inside Remove.

🔧 Debug

advanced

Identify the bug in this deque implementation snippet

What is the bug in this Go code snippet that tries to remove an element from the front of a deque and print it?

Code:
deque := list.New()
deque.PushBack(5)
front := deque.Front()
deque.Remove(front)
fmt.Println(front.Value)

DSA Go

package main

import (
	"container/list"
	"fmt"
)

func main() {
	deque := list.New()
	deque.PushBack(5)
	front := deque.Front()
	deque.Remove(front)
	fmt.Println(front.Value)
}

A deque.Front() returns nil causing nil pointer dereference

B front.Value is invalid after removal; accessing it causes runtime panic

C deque.Remove(front) removes wrong element; should use deque.PopFront()

D front.Value prints 5 correctly; no bug

💡 Hint

Think about what happens to the element after Remove is called.

front.Value prints 5 correctly; no bug. After Remove, the Element still holds its Value field, which can be safely accessed.

❓ Predict Output

advanced

Output after mixed deque operations

What is the output of the following Go program that uses a deque?

Code:
package main
import ("container/list"; "fmt")
func main() {
d := list.New()
d.PushBack(1)
d.PushBack(2)
d.PushFront(3)
d.Remove(d.Back())
d.PushFront(4)
for e := d.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " -> ")
}
fmt.Print("null")
}

DSA Go

package main
import (
	"container/list"
	"fmt"
)
func main() {
	d := list.New()
	d.PushBack(1)
	d.PushBack(2)
	d.PushFront(3)
	d.Remove(d.Back())
	d.PushFront(4)
	for e := d.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " -> ")
	}
	fmt.Print("null")
}

A 4 -> 1 -> 3 -> null

B 3 -> 4 -> 1 -> null

C 4 -> 3 -> 1 -> null

D 1 -> 3 -> 4 -> null

💡 Hint

Track each operation carefully, especially removals and additions at front and back.

Initial: empty PushBack(1): 1 PushBack(2): 1 -> 2 PushFront(3): 3 -> 1 -> 2 Remove Back (2): 3 -> 1 PushFront(4): 4 -> 3 -> 1

🚀 Application

expert

Deque usage for sliding window maximum problem

Given a sliding window size k=3 and input array [2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], which of the following outputs correctly represents the maximum values in each sliding window using a deque-based approach?

A [2, 1, 3, 4, 6, 3, 8, 9, 10]

B [3, 4, 6, 6, 8, 9, 10, 12, 56]

C [3, 4, 6, 3, 8, 9, 10, 12, 56]

D [2, 3, 4, 6, 8, 9, 10, 12, 56]

💡 Hint

The sliding window maximum moves one step at a time, always picking the max in the current window.

The sliding windows of size 3 are:
[2,1,3] max=3
[1,3,4] max=4
[3,4,6] max=6
[4,6,3] max=6
[6,3,8] max=8
[3,8,9] max=9
[8,9,10] max=10
[9,10,12] max=12
[10,12,56] max=56

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