title: How to implement a queue in Go?
body: <p>The current Go library doesn't provide the queue container.
  To implement a simple queue, I use circle array as the underlying data structure.
  It follows algorithms mentioned in TAOCP:</p>
  
  <pre><code>Insert Y into queue X: X[R]&lt;-Y; R&lt;-(R+1)%M; if R=F then OVERFLOW.
  Delete Y from queue X: if F=R then UNDERFLOW; Y&lt;-X[F]; F&lt;-(F+1) % M.
  F: Front, R: Rear, M: Array length.
  </code></pre>
  
  <p>Following is the code:</p>
  
  <pre><code>package main
  
  import (
      "fmt"
  )
  
  type Queue struct {
      len        int 
      head, tail int 
      q          []int
  }
  
  func New(n int) *Queue {
      return &amp;Queue{n, 0, 0, make([]int, n)} 
  }
  
  func (p *Queue) Enqueue(x int) bool {
      p.q[p.tail] = x 
      p.tail = (p.tail + 1) % p.len
      return p.head != p.tail
  }
  
  func (p *Queue) Dequeue() (int, bool) {
      if p.head == p.tail {
          return 0, false
      }   
      x := p.q[p.head]
      p.head = (p.head + 1) % p.len
      return x, true
  }
  
  func main() {
      q := New(10)
      for i := 1; i &lt; 13; i++ {
          fmt.Println(i, q.Enqueue(i))
      }   
      fmt.Println()
      for i := 1; i &lt; 13; i++ {
          fmt.Println(q.Dequeue())
      }   
  }
  </code></pre>
  
  <p>But the output is obviously wrong:</p>
  
  <p>1 true
  2 true
  3 true
  4 true
  5 true
  6 true
  7 true
  8 true
  9 true
  10 false
  11 true
  12 true</p>
  
  <p>11 true
  12 true
  0 false
  0 false
  0 false
  0 false
  0 false
  0 false
  0 false
  0 false
  0 false
  0 false</p>
  
  <p>I think I need one more field to make the code work properly.
  What do you suggest?</p>
  
  <p>The improved code has a small shortcoming: an array of size n can contain only n-1 elements.</p>
  
  <pre><code>package main
  
  import (
      "fmt"
  )
  
  type Queue struct {
      len        int 
      head, tail int 
      q          []int
  }
  
  func New(n int) *Queue {
      return &amp;Queue{n, 0, 0, make([]int, n)} 
  }
  
  func (p *Queue) Enqueue(x int) bool {
      p.q[p.tail] = x 
      ntail := (p.tail + 1) % p.len
      ok := false
      if ntail != p.head {
          p.tail = ntail
          ok = true
      }   
      return ok
  }
  
  func (p *Queue) Dequeue() (int, bool) {
      if p.head == p.tail {
          return 0, false
      }   
      x := p.q[p.head]
      p.head = (p.head + 1) % p.len
      return x, true
  }
  
  func main() {
      q := New(10)
      for i := 1; i &lt; 13; i++ {
          fmt.Println(i, q.Enqueue(i))
      }   
      fmt.Println()
      for i := 1; i &lt; 13; i++ {
          fmt.Println(q.Dequeue())
      }   
  }
  </code></pre>