linux进阶54——无锁队列的实现

（1）windows下实现（未调用windows API版本）

template
class node
{
public:
 T     pdata;
 node* next;
};

template
class SQueue
{
private:
 node *front;
 node *tear;
public:
 SQueue();
 ~SQueue();
 bool empty();
 T pop();
 void push(T p);
};

template
SQueue::SQueue()
{
 node *pnode = new node();
 front = pnode;
 tear = pnode;
}

template
SQueue::~SQueue()
{
 node *cur = front;
 node *next = nullptr;
 while (cur)
 {
  next = cur->next;
  delete cur->pdata;
  delete cur;
  cur = next;
 }
}

template
bool SQueue::empty()
{
 if (front == tear)
  return true;
 return false;
}

template
void SQueue::push(T p)
{
 node *pnode = new node();
 tear->pdata = p;
 tear->next = pnode;
 tear = pnode;
}

template
T SQueue::pop()
{
 if (empty())
  return NULL;
 node* pnode = front;
 T p = pnode->pdata;
 front = front->next;

 delete pnode;
 return p;
}

（2）linux下实现

template
class LQueue
{
public:
 LQueue();                  //构造函数
 ~LQueue();                 //析构函数
public:
 void push(T elem);         //入队列
 T pop();                   //出队列
 bool empty();       

private:
 struct _qNode             //队列节点
 {
  _qNode() : _next(nullptr) { }
  _qNode(T elem) : _elem(elem), _next(nullptr) { }
  T       _elem;
  struct _qNode *_next;
 };
private:
 _qNode *_head;    //头结点
 _qNode *_tail;    //尾节点
};

template
LQueue::LQueue()
{
 _head = _tail = new _qNode();
}

template
LQueue::~LQueue()
{
 while (_head != nullptr)
 {
  _qNode *tempNode = _head;
  _head = _head->_next;
  delete tempNode;
 }
}

template
void LQueue::push(T elem)
{
 //创建一个新的节点
 _qNode *newNode = new _qNode(elem);

 _qNode *p = _tail;
 _qNode *oldp = _tail;

 do {
  while (p->_next != nullptr)
   p = p->_next;
 } while (__sync_bool_compare_and_swap(&p->_next, NULL, newNode) != true);

	__sync_bool_compare_and_swap(&_tail, oldp, newNode);
}

template
T LQueue::pop()
{
	_qNode *p;
	do {
		p = _head;
		if (p->_next == nullptr)
			return NULL;
	} while (__sync_bool_compare_and_swap(&_head, p, p->_next) != true);

	return p->_next->_elem;
}

template
bool LQueue::empty()
{
	if (_head == _tail)
		return true;
	else
		return false;
}

关于无锁队列的介绍，可以查看：linux进阶50——无锁CAS_www_dong的博客-CSDN博客