Question:

How would you implement a stack and a queue in Go? Explain and provide code examples.

Answer:

You use slices to implement a stack or queue by yourself:

type Stack []int
func (s Stack) Empty() bool { return len(s) == 0 }
func (s *Stack) Push(v int) { (*s) = append((*s), v) }
func (s *Stack) Pop() int {
	v := (*s)[len(*s)-1]
	(*s) = (*s)[:len(*s)-1]
	return v
}

type Queue []int
func (q Queue) Empty() bool    { return len(q) == 0 }
func (q *Queue) Enqueue(v int) { (*q) = append((*q), v) }
func (q *Queue) Dequeue() int {
	v := (*q)[0]
	(*q) = (*q)[1:len(*q)]
	return v
}

func main() {
	s := Stack{}
	s.Push(1)
	s.Push(2)
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
	fmt.Println(s.Empty())
	// Output:
	// 2
	// 1
	// true

	q := Queue{}
	q.Enqueue(1)
	q.Enqueue(2)
	fmt.Println(q.Dequeue())
	fmt.Println(q.Dequeue())
	fmt.Println(q.Empty())
	// Output:
	// 1
	// 2
	// true
}

The queue implementation above is correct, but it is suboptimal. There are better but lengthier implementations, like this one.

Occasionally, you would prefer the Go standard library’s container/list to implement them for their conciseness, genericity, and extra list data structure related operations:

stack := list.New()
stack.PushBack(1)
stack.PushBack(2)
fmt.Println(stack.Remove(stack.Back()))
fmt.Println(stack.Remove(stack.Back()))
fmt.Println(stack.Len() == 0)
// Output:
// 2
// 1
// true

queue := list.New()
queue.PushBack(1)
queue.PushBack(2)
fmt.Println(queue.Remove(queue.Front()))
fmt.Println(queue.Remove(queue.Front()))
fmt.Println(queue.Len() == 0)
// Output:
// 1
// 2
// true

Although, their usage is generally discouraged for their slower performance, compared to slices iteration pattern. Let’s compare the two following examples:

// Iterate through a list and print its contents.
for e := queue.Front(); e != nil; e = e.Next() {
    fmt.Println(e.Value)
}
for _, e := range queue {
    fmt.Println(e)
}

“Always use a slice.”, Dave Cheney

Another possibility to implement a queue is to use buffered channels, but this is never a good idea, because:

  1. The buffer size is determined at the channel creation and cannot be increased.
  2. It is impossible to peek at the next queue element without retrieving it from the queue.
  3. There is a risk of deadlock: “Novices are sometimes tempted to use buffered channels within a single goroutine as a queue, lured by their pleasingly simple syntax, but this is a mistake. Channels are deeply connected to goroutine scheduling, and without another goroutine receiving from the channel, a sender—and perhaps the whole program—risks becoming blocked forever. If all you need is a simple queue, make one using a slice.”, Brian Kernighan.

Keywords:

© 2017 QuizBucket.org