队列是常用的数据结构，采用的FIFO(first in firstout)原则，新元素（等待进入队列的元素）总是被插入到尾部，而读取的时候总是从头部开始读取。在计算中队列一般用来做排队(如线程池的等待排队，锁的等待排队)，用来做解耦（生产者消费者模式），异步等等。在java多线程应用中，队列的使用率很高，多数生产消费模型的首选数据结构就是队列。队列在现实生活中也很常见，例如去超市买东西排队付钱，先来的先付账走人回家，后来的要等前面的人付完钱才能付账。
首先我们看一段队列代码：
type Queue struct {
head unsafe.Pointer
tail unsafe.Pointer
Reset func(interface{})
New func() interface{}
}
// one node in queue
type Node struct {
val interface{}
next unsafe.Pointer
}
func QueueNew()(*Queue){
queue := new(Queue)
queue.head = unsafe.Pointer(new(Node))
queue.tail = queue.head
return queue
}
func (self *Queue) EnQueue(val interface{}) {
if self.Reset!= nil{
self.Reset(val)
}
newNode := unsafe.Pointer(&Node{val: val, next: nil})
var tail, next unsafe.Pointer
tail = self.tail
((*Node)(tail)).next = newNode
self.tail = newNode
}
func (self *Queue) DeQueue() (val interface{}) {
var head, tail, next unsafe.Pointer
head = self.head
tail = self.tail
next = ((*Node)(head)).next
if head == tail {
// There's no data in the queue.
return nil
}
val = ((*Node)(next)).val
self.head = next
return val
}这是一般的队列实现方法，适用于单线程但如果是多线程操作就麻烦了。例如在超市柜台结账，大家都按规则进行排队没有问题，但是如果有两个人张大妈和李大妈都着急结账回家接孙子，同时跑到了同一个队列的队尾，她们两都说自己应该排在队尾。那么问题就来了。那么对于多线程操作同一个队列，可以用锁的方法来实现，在入队和出队前加上锁即可：
type Queue struct {
sync.RWMutex
head unsafe.Pointer
tail unsafe.Pointer
Reset func(interface{})
New func() interface{}
}
func (self *Queue) EnQueue(val interface{}) {
self.Lock()
defer self.Unlock()
if self.Reset != nil {
self.Reset(val)
}
newNode := unsafe.Pointer(&Node{val: val, next: nil})
var tail, next unsafe.Pointer
tail = self.tail
((*Node)(tail)).next = newNode
self.tail = newNode
}
func (self *Queue) DeQueue() (val interface{}) {
var head, tail, next unsafe.Pointer
self.Lock()
defer self.Unlock()
head = self.head
tail = self.tail
next = ((*Node)(head)).next
if head == tail {
// There's no data in the queue.
return nil
}
val = ((*Node)(next)).val
self.head = next
return val
}但是，这种加锁的方法在多进程的操作中会消耗很多系统资源，使用不当还会造成死锁，下面推荐一种CAS的方法来实现队列的安全出队和入队。CAS（Compare and Swap），比较并交换，在大多数处理器架构，CAS的具体是判断一个内存上的数据是否是所判断的值，如果是，那么执行修改；如果不是，那么将不做操作并返回当前值。CAS是一种乐观锁，多线程执行过程中，多个线程去修改内存中的数据，有且只有一个能修改成功，但是失败的线程不会中断或者挂起。具体代码如下：
func (self *Queue) EnQueue(val interface{}) {
if self.Reset!= nil{
self.Reset(val)
}
newNode := unsafe.Pointer(&Node{val: val, next: nil})
var tail, next unsafe.Pointer
for {
tail = self.tail
next = ((*Node)(tail)).next
if tail != self.tail{
runtime.Gosched()
continue
} //[PositionA]-----------A new node may already enqueue-------------
if next != nil {
atomic.CompareAndSwapPointer(&(self.tail), tail, next)
continue
}
if atomic.CompareAndSwapPointer(&((*Node)(tail).next), nil,newNode ) {
break
}
runtime.Gosched()
}
atomic.CompareAndSwapPointer(&(self.tail),tail, newNode)
}
func (self *Queue) DeQueue() (val interface{}) {
var head, tail, next unsafe.Pointer
for {
head = self.head
tail = self.tail
next = ((*Node)(head)).next
if head != self.head{
runtime.Gosched()
continue
}
if next == nil{
if self.New != nil{
return self.New()
}else{
return nil
}
}
if head == tail {
atomic.CompareAndSwapPointer(&(self.tail), tail, next)
}else{
val = ((*Node)(next)).val //[PositionB]---------The head node may already Dequeue---------
if atomic.CompareAndSwapPointer(&(self.head), head, next) {
return val
}
}
runtime.Gosched()
}
}
多线程在运行这段代码的过程中可能在位置A和位置B发生抢占，所以要先进行比较，如果一样再进行操作，这样就能保证一致性。