C语言实现双端队列

1.C语言实现

也就是在原来队列的基础上允许在队列两端进行入队和出队操作 因为原来只能够在队列的队尾入队 队头出队

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 双端队列其实就是允许队列在两端进行入队和出队操作 但是原先的队列是只能够在队头出队 队尾入队的
// 节点类
typedef struct Node {
	// 数据域
	int data;
	// 指针域
	struct Node* pre;
	struct Node* next;
}Node;
// 初始化队列
Node* initDeque() {
	Node* deque = (Node*)malloc(sizeof(Node));
	deque->data = 0;
	deque->pre = NULL;
	deque->next = NULL;
	return deque;
}
// 队头入队
void enQueueFront(int data, Node* deque) {
	// 为待插入节点分配内存
	Node* node = (Node*)malloc(sizeof(Node));
	// 设置数据域
	node->data = data;
	Node* pre = deque;
	Node* next = pre->next;
	// 接着就是设置指针
	pre->next = node;
	node->pre = pre;
	node->next = next;
	if (next)
		next->pre = node;
	// 更新队列长度
	deque->data++;
}
// 队尾入队
void enQueueRear(int data, Node* deque) {
	// 为待插入节点分配内存
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	Node* pre = deque;
	while (pre->next) {
		pre = pre->next;
	}
	Node* next = pre->next;
	pre->next = node;
	node->pre = pre;
	node->next = next;
	// 更新队列长度
	deque->data++;
}
// 队头出队
int deQueueFront(Node* deque) {
	// 首先对队列进行判空操作
	if (deque->data == 0)return -1;
	Node* pre = deque;
	Node* node = pre->next;
	int delete = node->data;
	Node* next = node->next;
	pre->next = next;
	if (next)
		next->pre = pre;
	// 更新队列长度
	deque->data--;
	return delete;
}
// 队尾出队
int deQueueRear(Node* deque) {
	// 对队列进行判空操作
	if (deque->data == 0)return -1;
	Node* node = deque->next;
	while (node->next)
		node = node->next;
	int delete = node->data;
	Node* pre = node->pre;
	Node* next = node->next;
	pre->next = next;
	// 更新队列长度
	deque->data--;
	return delete;
}
// 获取队头元素
int front(Node* deque) {
	// 对队列进行判空操作
	if (deque->data == 0)return -1;
	return deque->next->data;
}
// 获取队尾元素
int rear(Node* deque) {
	// 对队列进行判空操作
	if (deque->data == 0)return -1;
	Node* cur = deque->next;
	while (cur->next)
		cur = cur->next;
	return cur->data;
}
// 清空队列
void clear(Node* deque) {
	Node* cur = deque->next;
	Node* next;
	while (cur) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	deque->data = 0;
}
// 获取队列长度
int size(Node* deque) {
	return deque->data;
}
// 判空操作
bool isEmpty(Node* deque) {
	return deque->data == 0;
}
// 打印
void printDeque(Node* deque) {
	Node* cur = deque->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 定义一个主函数
int main() {
	Node* deque = initDeque();
	enQueueFront(0, deque);// 0
	enQueueRear(1, deque);// 0 1
	enQueueFront(2, deque);// 2 0 1
	enQueueRear(3, deque);// 2 0 1 3
	// 打印队列
	printDeque(deque);// 2 0 1 3
	deQueueFront(deque);// 0 1 3
	deQueueRear(deque);// 0 1
	printDeque(deque);// 0 1
	printf("%d\n", isEmpty(deque));// 0
	printf("%d\n", size(deque));// 2
	printf("%d\n", front(deque));// 0
	printf("%d\n", rear(deque));// 1
	clear(deque);
	printf("%d\n", size(deque));// 0
	return 0;
}