97

I've built a simple queue in Go. It uses an internal slice to keep track of its elements. Elements are pushed onto the queue by appending to the slice. I'd like to implement .Pop() by removing the first element in elements.

In many other languages, "popping" the first element of a list is a one-liner, which leads me to believe my implementation below is sloppy and verbose. Is there a better way?

type Queue struct {
    elements []interface{}
}

func (queue *Queue) Push(element interface{}) {
    queue.elements = append(queue.elements, element)
}

func (queue *Queue) Pop() interface{} {
    element := queue.elements[0]
    if len(queue.elements) > 1 {
        queue.elements = queue.elements[1:]
    } else {
        queue.elements = make([]interface{}, 0)
    }
    return element
}

Please note that I wish for the Queue to panic if len(queue.elements) == 0. It's not an oversight that I don't check the bounds.

1
  • "Pop" usually refers to removing the last element of a list/slice, acting like a stack. "Shifting" usually refers to removing the first element of a list/slice, acting like a queue. It seems you want the latter here.
    – ggorlen
    Apr 9, 2022 at 23:21

2 Answers 2

269
+500

Did you try these?

Pop from queue

x, a = a[0], a[1:]

Pop from stack

x, a = a[len(a)-1], a[:len(a)-1]

Push

a = append(a, x)

From: https://code.google.com/p/go-wiki/wiki/SliceTricks

5
  • 1
    If efficiency is important, you may want to use a ring-buffer style to avoid excessive re-allocation and garbage collection. Something like github.com/eapache/channels/blob/master/queue.go
    – Evan
    May 8, 2014 at 3:29
  • I'm just wondering if after popping from the queue, the first element will be ever garbaged collected. If I keep popping the first element and appending at the end, will I end with a huge array? the unused elements are also copied if append() copies the array to a new one?
    – siritinga
    May 8, 2014 at 6:57
  • 1
    The first element will only be garbage collected when enough new elements have been added that the slice is reallocated and the removed elements can be discarded. In my ring-buffer sample code, the elements are explicitly niled when removed in order to permit immediate garbage collection. (The unused elements are not copied if append resizes the array).
    – Evan
    May 8, 2014 at 17:56
  • 2
    I think the main problem with this approach is that there is potentially an allocation on every queue insert - playground example May 10, 2014 at 12:46
  • 2
    I extracted my ring-buffer based queue into its own package at github.com/eapache/queue so that other people can import it if they want to use it.
    – Evan
    May 15, 2014 at 3:31
13

If you want a ring buffer or FIFO structure then using a slice as in @Everton's answer will cause garbage collection problems as the underlying array may grow indefinitely.

The easiest way to do this in go, provided you don't mind having a limited size, is to use a channel which is also safe for concurrent access. This is such a common idiom in go that you wouldn't usually bother wrapping it in a type like the below.

Eg (Playground)

package main

import "fmt"

type Queue struct {
    elements chan interface{}
}

func NewQueue(size int) *Queue {
    return &Queue{
        elements: make(chan interface{}, size),
    }
}

func (queue *Queue) Push(element interface{}) {
    select {
    case queue.elements <- element:
    default:
        panic("Queue full")
    }
}

func (queue *Queue) Pop() interface{} {
    select {
    case e := <-queue.elements:
        return e
    default:
        panic("Queue empty")
    }
    return nil
}

func main() {
    q := NewQueue(128)

    q.Push(1)
    q.Push(2)
    q.Push(3)
    fmt.Printf("Pop %d\n", q.Pop())
    fmt.Printf("Pop %d\n", q.Pop())
    fmt.Printf("Pop %d\n", q.Pop())
    fmt.Printf("Pop %d\n", q.Pop())

}
7
  • I'm still new to Go, so I might take me a while to wrap my head around this, but thanks for the answer! I'll come back to it after I learn more about channels. May 8, 2014 at 7:34
  • 2
    Channels happen to provide a useful and efficient tool for making ring buffers like this. As originally conceived by C.A.R.Hoare though, channels are intended to be used between processes (goroutines); this pattern is rather different. Be aware that if the channel buffer becomes full, and the only consuming thread (calling Pop) is also trying to call Push, a deadlock can occur. @Everton's approach doesn't have this drawback; the garbage collection problem could be solved a different way.
    – Rick-777
    May 8, 2014 at 17:42
  • 2
    @Rick-777 the deadlock is easily solved with another select in the Push method. May 8, 2014 at 19:02
  • 2
    @Rick-777 Have updated the answer to show how to detect queue full. May 9, 2014 at 14:56
  • 2
    @modocache I'd say if you are communicating between go routines, just use channels - that is what they are for. You don't need queue empty or full detection - the runtime will pause and unpause the goroutines for you automatically. Otherwise you could use this solution which is type safe but bounded, or you could use the code mentioned by Evan which doesn't have any allocation or garbage collection problems. May 10, 2014 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.