双端循环队列

typedef struct QueElemTag{
	QueElemTypeAlias* next;
	QueElemTypeAlias* prev;
	int value;
}QueElemTypeAlias;

#define QUEUEREMOVE(elem){\
	((QueElemTypeAlias*)elem)->prev->next = ((QueElemTypeAlias*)elem)->next;\
	((QueElemTypeAlias*)elem)->next->prev = ((QueElemTypeAlias*)elem)->prev;\
	((QueElemTypeAlias*)elem)->next = (QueElemTypeAlias*)(elem);\
	((QueElemTypeAlias*)elem)->prev = (QueElemTypeAlias*)(elem);\
}

#define QUEUEINSERT(qelem,elem){\
	QueueEnqueue((QueElemTypeAlias*)qelem,((QueElemTypeAlias*)elem))\
}

#define ISQUEUEEMPTY(queue) ((queue)->next == (QueElemTypeAlias*)(queue)) //队列是否空
#define QUEUEHEAD(queue) ((void*)(((QueElemTypeAlias*)(queue))->next)) //访问队列第一个元素
#define QUEUETAIL(tail)  ((void*)(((QueElemTypeAlias*)(queue))->next)) //访问队列最后一个元素
#define QUEUENEW(elem) (elem)->next = (elem)->prev = (elem)


/*
 *  ======== QueueEnqueue ========
 *
 *  put "elem" at end of "queue".
 *               _______        _______        _______
 *  Before:     |_______|----->|_______|----->|_______|--->
 *              |_______|<-----|_______|<-----|_______|<---
 *               prev           queue          next
 *               _______
 *      elem -->|___x___|       * = modified
 *              |___x___|       x = undefined
 *
 *  ================ =============
 *               _______        _______        _______      _______
 *  After:      |___*___|----->|___*___|----->|_______|--->|_______|--->
 *              |_______|<-----|___*___|<-----|___*___|<---|_______|<---
 *               prev           elem          queue         next
 *
 *  ================ =============
 */

//对于双端循环队列，相当于插入队尾。(PS:handle节点是dummy)
QueElemTypeAlias* QueueEnqueue(QueElemTypeAlias* queue,QueElemTypeAlias* elem){
	QueElemTypeAlias* prev = queue->prev;
	((QueElemTypeAlias*)elem)->next = (QueElemTypeAlias*)queue;
	((QueElemTypeAlias*)elem)->prev = prev;
	prev->next = (QueElemTypeAlias*)elem;
	queue->prev = (QueElemTypeAlias*)elem;
}

/*
*  ======== QueueCreate ========
*  ,------>|_______|------->,
*  | ,<----|_______|<-----, |
*  | |       queue        | |
*  | |____________________| |
*  |________________________|
*/

QueElemTypeAlias* QueueCreate(QueElemTypeAlias* queue){
	queue->next = (QueElemTypeAlias*)queue;
	queue->prev = (QueElemTypeAlias*)queue;
	return queue;
}

//没明白这个方法是用来做什么的，可以看出来的是它剔除了handle(dummy)之后的节点
/*
 *  ======== QueueDequeue ========
 *               _______        _______        _______      _______
 *  Before:     |_______|----->|_______|----->|_______|--->|_______|--->
 *              |_______|<-----|_______|<-----|_______|<---|_______|<---
 *               prev           queue          elem         next
 *
 *
 *               _______        _______        _______
 *  After:      |_______|----->|___*___|----->|_______|--->
 *              |_______|<-----|_______|<-----|___*___|<---
 *               prev           queue          next
 *               _______
 *      elem -->|___x___|       * = modified
 *              |___x___|       x = undefined
 *
 */
QueElemTypeAlias* QueueDequeue(QueElemTypeAlias* queue){
	QueElemTypeAlias* elem = queue->next;
	QueElemTypeAlias* next = elem->next;
	queue->next = next;
	next->prev = (QueElemTypeAlias*)queue;
	return (elem);
}

QueElemTypeAlias* QueueContains(QueElemTypeAlias* queue, QueElemTypeAlias* elem){
	QueElemTypeAlias* next = queue->next;
	while(next != (QueElemTypeAlias*)queue){
		if(next == elem){
			return true;
		}
		next = next->next;
	}
	return false;
}

int QueSize(QueElemTypeAlias* queue){
    QueElemTypeAlias* tElem;
	int qSize = 0;
	//tElem = queue->next ,handle即head不存数据，不计入队列长度
	for(tElem = queue->next; tElem != queue; tELem = tElem->next){
		++qSize;
	}
	return qSize;
}



void DequeByBubbleSort(QueElemTypeAlias* queue){
	int qSize = QueSize(queue);
	int sorttime = 0, n = qSize;
	QueElemTypeAlias* fist = NULL;
	QueElemTypeAlias* tmp = NULL, elem = NULL, elemNext = NULL;
	while(n > 1)
		fist = queue->next;
		tmp = first;
		while(tmp != queue){
			if(sorttime >= n - 1){
				break;
			}
			elem = tmp;
			elemNext = elem->next;
			if(tmp->next = queue){
				break;
			}
			if(SwapByValue(elem, elem->next)){
				sorttime += 1;
				tmp = elem;
			}else{
				tmp = elemNext;
			}
		}
		sorttime = 0;
		n -= 1;
	}
}

BOOL SwapByValue(QueElemTypeAlias* first, QueElemTypeAlias* second){
	BOOL swaped = false;
	if(fisrt->value < second->value){
		QUEUEREMOVE(first);
		QUEUEINSERT(second->next, first);
		swaped = true;
	}
	return swaped;
}

/* 含有dummy节点的插入排序 */
void InsertSort(QueElemTypeAlias* queue){
	QueElemTypeAlias* ptElem = queue->next;
	while(ptElem != queue){
		QueElemTypeAlias* ptElemPrev = ptElem->prev;
		while(ptElemPrev != queue){
			if(ptElemPrev->value > ptElem->value){
				Swap(ptElemPrev,ptElemPrev->prev);
			}
			ptElemPrev = ptElemPrev->prev;
		}
		/* insert */
		ptElem = ptElem->next;
	}
}