dougaoshang0237
2010-05-12 12:45
浏览 49
已采纳

有队列实现吗?

Can anyone suggest Go container for simple and fast FIF/queue, Go has 3 different containers: heap, list and vector. Which one is more suitable to implement a queue?

图片转代码服务由CSDN问答提供 功能建议

任何人都可以建议使用Go容器来实现简单快速的FIF /队列,Go具有3种不同的容器: heap < / code>,列表 vector 。 哪个更适合实现队列?

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

13条回答 默认 最新

  • doujing5435 2010-05-12 13:56
    已采纳

    Either vector or list should work, but vector is probably the way to go. I say this because vector will probably allocate less often than list and garbage collection (in the current Go implementation) is fairly expensive. In a small program it probably won't matter, though.

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • douhei8633 2012-08-01 10:18

    To expand on the implementation side, Moraes proposes in his gist some struct from queue and stack:

    // Stack is a basic LIFO stack that resizes as needed.
    type Stack struct {
        nodes   []*Node
        count   int
    }
    // Queue is a basic FIFO queue based on a circular list that resizes as needed.
    type Queue struct {
        nodes   []*Node
        head    int
        tail    int
        count   int
    }
    

    You can see it in action in this playground example.

    评论
    解决 无用
    打赏 举报
  • dsjklb0205 2014-11-11 11:22

    In fact, if what you want is a basic and easy to use fifo queue, slice provides all you need.

    queue := make([]int, 0)
    // Push to the queue
    queue = append(queue, 1)
    // Top (just get next element, don't remove it)
    x = queue[0]
    // Discard top element
    queue = queue[1:]
    // Is empty ?
    if len(queue) == 0 {
        fmt.Println("Queue is empty !")
    }
    

    Of course, we suppose that we can trust the inner implementation of append and slicing so that it avoid useless resize and reallocation. For basic usage, this is perfectly sufficient.

    评论
    解决 无用
    打赏 举报
  • drxdai15012937753 2016-09-20 15:46

    Surprised to see no one has suggested buffered channels yet, for size bound FIFO Queue anyways.

    //Or however many you might need + buffer.
    c := make(chan int, 300)
    
    //Push
    c <- value
    
    //Pop
    x <- c
    
    评论
    解决 无用
    打赏 举报
  • duanming7961 2017-04-22 02:16

    Using a slice and an appropriate ("circular") indexing scheme on top still seems to be the way to go. Here's my take on it: https://github.com/phf/go-queue The benchmarks there also confirm that channels are faster, but at the price of more limited functionality.

    评论
    解决 无用
    打赏 举报
  • dongyinglan8707 2017-06-04 09:54

    Slice can be used to implement queue.

    type queue struct {
        values []*int
    }
    
    func New() *queue {
       queue := &queue{}
       return queue
    }
    
    func (q *queue) enqueue(val *int) {
       q.values = append(q.values, val)
    }
    
    //deque function
    

    Update:

    here is complete implementation on my GitHub page https://github.com/raiskumar/algo-ds/blob/master/tree/queue.go

    评论
    解决 无用
    打赏 举报
  • dsbc80836 2017-08-22 02:49

    I also implement the queue from slice as above. However, It's not thread-safe. So I decided to add a lock (mutex lock) to guarantee thread-safe.

    package queue
    
    import (
      "sync"
    )
    
    type Queue struct {
      lock *sync.Mutex
      Values []int
    }
    
    func Init() Queue {
      return Queue{&sync.Mutex{}, make([]int, 0)}
    }
    
    func (q *Queue) Enqueue(x int) {
      for {
        q.lock.Lock()
        q.Values = append(q.Values, x)
        q.lock.Unlock()
        return
      }
    }
    
    func (q *Queue) Dequeue() *int {
      for {
        if (len(q.Values) > 0) {
          q.lock.Lock()
          x := q.Values[0]
          q.Values = q.Values[1:]
          q.lock.Unlock()
          return &x
        }
        return nil
      }
      return nil
    }
    

    You can check my solution on github here simple queue

    评论
    解决 无用
    打赏 举报
  • dqkx69935 2018-05-18 20:27

    Most queue implementations are in one of three flavors: slice-based, linked list-based, and circular-buffer (ring-buffer) based.

    • Slice-based queues tend to waste memory because they do not reuse the memory previously occupied by removed items. Also, slice based queues tend to only be single-ended.
    • Linked list queues can be better about memory reuse, but are generally a little slower and use more memory overall because of the overhead of maintaining links. They can offer the ability to add and remove items from the middle of the queue without moving memory around, but if you are doing much of that a queue is the wrong data structure.
    • Ring-buffer queues offer all the efficiency of slices, with the advantage of not wasting memory. Fewer allocations means better performance. They are just as efficient adding and removing items from either end so you naturally get a double-ended queue. So, as a general recommendation I would recommend a ring-buffer based queue implementation. This is what is discussed in the rest of this post.

    The ring-buffer based queue reuses memory by wrapping its storage around: As the queue grows beyond one end of the underlying slice, it adds additional nodes to the other end of the slice. See deque diagram

    Also, a bit of code to illustrate:

    // PushBack appends an element to the back of the queue.  Implements FIFO when
    // elements are removed with PopFront(), and LIFO when elements are removed
    // with PopBack().
    func (q *Deque) PushBack(elem interface{}) {
        q.growIfFull()
        q.buf[q.tail] = elem
        // Calculate new tail position.
        q.tail = q.next(q.tail)
        q.count++
    }
    
    // next returns the next buffer position wrapping around buffer.
    func (q *Deque) next(i int) int {
        return (i + 1) & (len(q.buf) - 1) // bitwise modulus
    }
    

    This particular implementation always uses a buffer size that is a power of 2, and can therefore compute the bitwise modulus to be a little more efficient.

    This means the slice needs to grow only when all its capacity is used up. With a resizing strategy that avoids growing and shrinking storage on the same boundary, this makes it very memory efficient.

    Here is code that resizes the underlying slice buffer:

    // resize resizes the deque to fit exactly twice its current contents. This is
    // used to grow the queue when it is full, and also to shrink it when it is     
    // only a quarter full.                                                         
    func (q *Deque) resize() {
        newBuf := make([]interface{}, q.count<<1)
        if q.tail > q.head {
            copy(newBuf, q.buf[q.head:q.tail])
        } else {
            n := copy(newBuf, q.buf[q.head:])
            copy(newBuf[n:], q.buf[:q.tail])
        }
        q.head = 0
        q.tail = q.count
        q.buf = newBuf
    }
    

    Another thing to consider is if you want concurrency safety built into the implementation. You may want to avoid this so that you can do whatever works best for your concurrency strategy, and you certainly do not want it if your do not need it; same reason as not wanting a slice that has some built-in serialization.

    There are a number of ring-buffer based queue implementations for Go if you do a search on godoc for deque. Choose one that best suits your tastes.

    评论
    解决 无用
    打赏 举报
  • douyi9787 2018-06-08 11:08

    Unfortunately queues aren't currently part of the go standard library, so you need to write your own / import someone else's solution. It's a shame as containers written outside of the standard library aren't able to use generics.

    A simple example of a fixed capacity queue would be:

    type MyQueueElement struct {
      blah int // whatever you want
    }
    
    const MAX_QUEUE_SIZE = 16
    type Queue struct {
      content  [MAX_QUEUE_SIZE]MyQueueElement
      readHead int
      writeHead int
      len int
    }
    
    func (q *Queue) Push(e MyQueueElement) bool {
      if q.len >= MAX_QUEUE_SIZE {
        return false
      }
      q.content[q.writeHead] = e
      q.writeHead = (q.writeHead + 1) % MAX_QUEUE_SIZE
      q.len++
      return true
    }
    
    func (q *Queue) Pop() (MyQueueElement, bool) {
      if q.len <= 0 {
        return MyQueueElement{}, false
      }
      result := q.content[q.readHead]
      q.content[q.readHead] = MyQueueElement{}
      q.readHead = (q.readHead + 1) % MAX_QUEUE_SIZE
      q.len--
      return result, true
    }
    

    Gotchas avoided here include not having unbounded slice growth (caused by using the slice [1:] operation to discard), and zeroing out popped elements to ensure their contents are available for garbage collection. Note, in the case of a MyQueueElement struct containing only an int like here, it will make no difference, but if struct contained pointers it would.

    The solution could be extended to reallocate and copy should an auto growing queue be desired.

    This solution is not thread safe, but a lock could be added to Push/Pop if that is desired.

    Playground https://play.golang.org/

    评论
    解决 无用
    打赏 举报
  • dongli4711 2018-07-17 06:31

    I implemented a queue that will expand the underlying buffer automatically:

    package types
    
    // Note: this queue does not shrink the underlying buffer.                                                                                                               
    type queue struct {
            buf  [][4]int // change to the element data type that you need                                                                                                   
            head int
            tail int
    }
    
    func (q *queue) extend(need int) {
            if need-(len(q.buf)-q.head) > 0 {
                    if need-len(q.buf) <= 0 {
                            copy(q.buf, q.buf[q.head:q.tail])
                q.tail = q.tail - q.head
                            q.head = 0
                            return
                    }
    
                    newSize := len(q.buf) * 2
                    if newSize == 0 {
                        newSize = 100
                }
                    newBuf := make([][4]int, newSize)
                    copy(newBuf, q.buf[q.head:q.tail])
                    q.buf = newBuf
            q.tail = q.tail - q.head
                    q.head = 0
            }
    }
    
    func (q *queue) push(p [4]int) {
            q.extend(q.tail + 1)
            q.buf[q.tail] = p
            q.tail++
    }
    
    func (q *queue) pop() [4]int {
            r := q.buf[q.head]
            q.head++
            return r
    }
    
    func (q *queue) size() int {
            return q.tail - q.head
    }
    
    
    // put the following into queue_test.go
    package types
    
    import (
            "testing"
    
            "github.com/stretchr/testify/assert"
    )
    
    func TestQueue(t *testing.T) {
            const total = 1000
            q := &queue{}
            for i := 0; i < total; i++ {
                    q.push([4]int{i, i, i, i})
                    assert.Equal(t, i+1, q.size())
            }
    
        for i := 0; i < total; i++ {
                    v := q.pop()
                    assert.Equal(t, [4]int{i, i, i, i}, v)
                    assert.Equal(t, total-1-i, q.size())
            }
    }
    
    评论
    解决 无用
    打赏 举报
  • doubipeng1336 2018-09-16 05:39

    Double stack implementation:

    O(1) Enqueue and Dequeue and uses slices (which tends to be better for cache misses).

    type Queue struct{
        enqueue, dequeue Stack
    }
    
    func (q *Queue) Enqueue(n *Thing){
        q.enqueue.Push(n)
    }
    
    func (q *Queue) Dequeue()(*Thing, bool){
        v, ok := q.dequeue.Pop()
        if ok{
            return v, true
        }
    
        for {
            v, ok := d.enqueue.Pop()
            if !ok{
                break
            }
    
            d.dequeue.Push(v)
        }
    
        return d.dequeue.Pop()
    }
    
    type Stack struct{
        v []*Thing
    }
    
    func (s *Stack)Push(n *Thing){
        s.v=append(s.v, n)
    }
    
    func (s *Stack) Pop()(*Thing, bool){
        if len(s.v) == 0 {
            return nil, false
        }
    
        lastIdx := len(s.v)-1
        v := s.v[lastIdx]
        s.v=s.v[:lastIdx]
        return v, true
    }
    
    评论
    解决 无用
    打赏 举报
  • doufan9395 2019-01-08 00:33

    list is enough for queue and stack, what we shoud do is l.Remove(l.Front()) for queue Poll, l.Remove(l.Back())for stack Poll,PushBack for the Add Operation for stack and queue. there are front and back pointer for list, such that time complexity is O(1)

    评论
    解决 无用
    打赏 举报
  • donglin1192 2019-03-18 05:06

    Just embed a "container/list" inside a simple implementation and expose the interface

    package queue
    
    import "container/list"
    
    // Queue is a queue
    type Queue interface {
        Front() *list.Element
        Len() int
        Add(interface{})
        Remove()
    }
    
    type queueImpl struct {
        *list.List
    }
    
    func (q *queueImpl) Add(v interface{}) {
        q.PushBack(v)
    }
    
    func (q *queueImpl) Remove() {
        e := q.Front()
        q.List.Remove(e)
    }
    
    // New is a new instance of a Queue
    func New() Queue {
        return &queueImpl{list.New()}
    }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题