队列(queue)是一种先进先出(FIFO)的线性表。只允许在一端进行插入，而在另一端删除元素。

允许插入的一端叫做队尾，允许删除的一端叫做队头。

双端队列(deque)：限定插入和删除操作在表两端进行的线性表。

双端队列在一些限定条件下可以退化为：
(1)普通队列(只能在一端插入而另外一端删除)
(2)两个栈底相连的栈

队列 / 双端队列的定义：

由于可以在双端操作，所以肯定得有一个head，一个rear(tail)。我觉得确实用一个多的空头表示比较合适，然后头的data可以表示队列中有多少元素。

注意1：删除队列头时，如果被删除的元素是队列中最后一个元素时，一定要记得更新尾结点为NULL！

注意2：双端队列在队尾删除的时候，由于没有保存前向指针，需要从head从头遍历到tail的前一个，还要注意考虑只有一个结点的特殊情况。

代码如下：

#include <stdio.h>
#include <stdlib.h>

struct Node
{
	struct Node* next;
	int data;
};

struct Deque
{
	struct Node* head;
	struct Node* tail;
};

int deque_init(struct Deque* dq)
{
	dq->head = (struct Node*)malloc(sizeof(struct Node));
	if(!dq->head)
	{
		return -1;
	}
	dq->tail = (struct Node*)malloc(sizeof(struct Node));
	if(!dq->tail)
	{
		return -1;
	}
	dq->head->data = dq->tail->data = 0;
	dq->head->next = dq->tail->next = NULL;
	return 0;
}

void deque_print(struct Deque* dq)
{
	struct Node* ptr = dq->head;
	while(ptr->next!=NULL)
	{
		ptr = ptr->next;
		printf("%d ", ptr->data);
	}
	printf("\n");
}

int deque_length(struct Deque* dq)
{
	if(!dq->head)
	{
		return 0;
	}else
	{
		return dq->head->data;
	}
}

void deque_free(struct Deque* dq)
{
	struct Node* ptr = dq->head;
	struct Node* ptr2 = NULL;
	// Free all except tail
	while(ptr!=NULL)
	{
		ptr2 = ptr->next;
		free(ptr);
		ptr = ptr2;
	}
	// Free tail
	if(dq->tail)
	{
		free(dq->tail);
	}
	dq->head = dq->tail = NULL;
}

int deque_head_enqueue(struct Deque* dq, int data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
	if(!new_node)
	{
		return -1;
	}
	new_node->next = NULL;
	new_node->data = data;
	new_node->next = dq->head->next;
	dq->head->next = new_node;
	dq->head->data++;
	// If new node was also tail
	if(new_node->next==NULL)
	{
		dq->tail->next = new_node;
	}
}

int deque_head_dequeue(struct Deque* dq, int* data)
{
	struct Node* free_node = dq->head->next;
	if(free_node)
	{
		*data = free_node->data;
		dq->head->next = free_node->next;
		// If only one node
		if(free_node->next==NULL)
		{
			dq->tail->next = NULL;
		}
		free(free_node);
		dq->head->data--;
		return 0;
	}else
	{
		return -1;
	}
}

int deque_tail_enqueue(struct Deque* dq, int data)
{
	struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
	if(!new_node)
	{
		return -1;
	}
	new_node->data = data;
	new_node->next = NULL;
	dq->head->data++;
	// if list is empty
	if(dq->tail->next==NULL)
	{
		dq->head->next = new_node;
		dq->tail->next = new_node;
	} else
	{
		dq->tail->next->next = new_node;
		dq->tail->next = new_node;
	}
}

int deque_tail_dequeue(struct Deque* dq, int* data)
{
	struct Node* free_node = dq->tail->next;
	struct Node* ptr = NULL;
	if(!free_node)
	{
		return -1;
	}
	*data = free_node->data;
	// Find node
	ptr = dq->head;
	free_node = dq->tail->next;
	while(ptr->next!=free_node)
	{
		ptr = ptr->next;
	}
	// Only one node
	if(ptr==dq->head)
	{
		free(free_node);
		dq->head->next = dq->tail->next = NULL;
		dq->head->data = 0;
	}else
	{
		free(free_node);
		ptr->next = NULL;
		dq->tail->next = ptr;
		dq->head->data--;
	}
	return 0;
}

int deque_head(struct Deque* dq, int* data)
{
	struct Node* head = dq->head->next;
	if(head!=NULL)
	{
		*data = head->data;
		return 0;
	}else
	{
		return 1;
	}
}

int deque_tail(struct Deque* dq, int* data)
{
	struct Node* tail = dq->tail->next;
	if(tail!=NULL)
	{
		*data = tail->data;
		return 0;
	}else
	{
		return 1;
	}
}

int main()
{
	struct Deque dq;
	int i;
	int data;
	if(deque_init(&dq))
	{
		printf("deque init fail.\n");
		return -1;
	}
	//deque_head_enqueue(&dq, 888);
	//deque_tail_enqueue(&dq, 888);
	//deque_tail_dequeue(&dq, &data);
	// Head
	if(!deque_head(&dq, &data))
	{
		printf("Head:%d\n", data);
	}else
	{
		printf("Deque is empty, no head\n");
	}
	// Tail
	if(!deque_tail(&dq, &data))
	{
		printf("Tail:%d\n", data);
	}else
	{
		printf("Deque is empty, no tail\n");
	}
	// Length
	printf("Length:%d\n", deque_length(&dq));
	// Head Enqueue
	//for(i=0;i<10;i++)
	//{
	//	deque_head_enqueue(&dq, i);
	//}
	//for(i=0;i<8;i++)
	//{
	//	deque_head_dequeue(&dq, &data);
	//}
	// Tail Enqueue
	for(i=0;i<10;i++)
	{
		deque_tail_enqueue(&dq, i);
	}
	for(i=0;i<8;i++)
	{
		deque_tail_dequeue(&dq, &data);
	}
	deque_print(&dq);
	printf("Length:%d\n", deque_length(&dq));
	// Tail
	if(!deque_tail(&dq, &data))
	{
		printf("Tail:%d\n", data);
	}else
	{
		printf("Deque is empty, no tail\n");
	}
	deque_free(&dq);
	return 0;
}