队列——双端队列的设计思路与实现

总的实现代码：

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

typedef struct{
	char name[100];
	char id[100];
}ElemType;

// 定义双端队列节点结构
typedef struct Node {
    ElemType data;               // 节点数据
    struct Node *next;      // 指向下一个节点的指针
    struct Node *prev;      // 指向前一个节点的指针
} Node;

// 定义双端队列结构
typedef struct Deque {
    Node *front;           // 队头指针
    Node *rear;            // 队尾指针
    int size;              // 队列大小
} Deque;

// 初始化双端队列
void InitDeque(Deque *dq) 
{
    dq->front = NULL;
    dq->rear = NULL;
    dq->size = 0;
}

// 判断双端队列是否为空
bool Empty(Deque *dq) 
{
    return dq->size == 0;
}

// 获取双端队列大小
int Size(Deque *dq) 
{
    return dq->size;
}

// 从队头插入元素
void Push_Front(Deque *dq, ElemType value) 
{
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->data = value;
    newNode->prev = newNode->next = NULL;

    if (Empty(dq))
	{
        dq->rear = newNode; // 如果队列为空，队尾也指向新节点
    } 
	else 
	{
        dq->front->prev = newNode; // 更新原队头节点的前指针
        newNode->next = dq->front;
    }
    dq->front = newNode; // 更新队头指针
    dq->size++; // 更新队列大小
}

// 从队尾插入元素
void Push_Back(Deque *dq, ElemType value) 
{
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->data = value;
    newNode->next = newNode->prev = NULL;

    if (Empty(dq)) 
	{
        dq->front = newNode; // 如果队列为空，队头也指向新节点
    } 
	else 
	{
        dq->rear->next = newNode; // 更新原队尾节点的后指针
        newNode->prev = dq->rear;
    }
    dq->rear = newNode; // 更新队尾指针
    dq->size++; // 更新队列大小
}

// 从队头删除元素
bool Pop_Front(Deque *dq, ElemType *e) 
{
    if (Empty(dq)) 
	{
		e = NULL;
        return false;
    }
    Node* temp = dq->front; // 临时保存队头节点
    if(e != NULL)
        *e = temp->data;
    dq->front = dq->front->next; // 更新队头指针

    if (dq->front != NULL) 
	{
        dq->front->prev = NULL; // 更新新的队头的前指针
    } 
	else 
	{
        dq->rear = NULL; // 如果队列为空，更新队尾指针
    }
    free(temp); // 释放被删除节点的内存
    dq->size--; // 更新队列大小
    return true; // 返回删除的数据
}

// 从队尾删除元素
bool Pop_Back(Deque *dq, ElemType *e) 
{
    if (Empty(dq)) 
	{
        e = NULL;
        return false;
    }
    Node* temp = dq->rear; // 临时保存队尾节点
    if(e != NULL)
        *e = temp->data;  // 获取队尾数据
    dq->rear = dq->rear->prev; // 更新队尾指针

    if (dq->rear != NULL) 
	{
        dq->rear->next = NULL; // 更新新的队尾的后指针
    } 
	else 
	{
        dq->front = NULL; // 如果队列为空，更新队头指针
    }
    free(temp); // 释放被删除节点的内存
    dq->size--; // 更新队列大小
    return true; // 返回删除的数据
}

// 查看队头元素
ElemType *Front(Deque *dq)
{
    if (Empty(dq)) 
	{
        return NULL;
    }
    return &(dq->front->data); // 返回队头元素
}

ElemType *Back(Deque *dq)
{
	if(Empty(dq))
	{
		return NULL;
	}
	return &(dq->rear->data);
}

void Clear(Deque *dq)
{
	while(Size(dq))
	{
		Pop_Back(dq, NULL);
	}
	return;
}

void Print(Deque *dq)
{
	Node *buf = dq->front;
	printf("\n---------------------------------------------\n");
	while(buf->next != NULL)
	{
		printf("元素为：%s  %s\n", buf->data.name, buf->data.id);
		buf = buf->next;
	}
	printf("---------------------------------------------\n");
}

// 主函数示例
int main() 
{
    ElemType arr[20] = {
	    {"张三", "0x001"},
	    {"李四", "0x002"},
	    {"张四", "0x003"},
	    {"李五", "0x004"}
	};
	Deque q;
	InitDeque(&q);
    Push_Back(&q, arr[0]);
    Push_Back(&q, arr[1]);
    Push_Front(&q, arr[2]);
    Push_Front(&q, arr[3]);
    
    ElemType *e = Front(&q);
    printf("队首元素为：%s  %s\n", e->name, e->id);
    printf("队列中元素个数为：%d\n", Size(&q)); 
    
    Pop_Front(&q, e);
    printf("队列中元素个数为：%d\n", Size(&q));
    e = Front(&q);
    if(e != NULL)
        printf("队首元素为：%s  %s\n", e->name, e->id);
        
    Pop_Back(&q, NULL);
    printf("队列中元素个数为：%d\n", Size(&q));
    *e = *(Front(&q));
    if(e != NULL)
        printf("队首元素为：%s  %s\n", e->name, e->id);
        
    printf("队列中元素个数为：%d\n", Size(&q));
    *e = *(Back(&q));
    if(e != NULL)
        printf("队尾元素为：%s  %s\n", e->name, e->id);
    
    if(Empty(&q))
		printf("队列空\n");
    else
    	printf("队列非空\n");
	
    Clear(&q);  // 清空队列 
    printf("队列中元素个数为：%d\n", Size(&q));
    return 0;
}