数据结构和算法--队列的链式实现

迈不过友情╰ 2022-07-15 08:00 195阅读 0赞

//队列链式队列的实现
    
    #include <stdio.h>
    #include <stdlib.h>
    
    //定义数据类型
    typedef int datatype_t;
    
    //定义结构体
    typedef struct node{
    	datatype_t data;
    	struct node *next;
    }linknode_t;
    
    typedef struct{
    	linknode_t *front;
    	linknode_t *rear;
    }linkqueue_t;
    
    //创建一个空的队列
    linkqueue_t *linkqueue_create()
    {
    	linkqueue_t *lq = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    	lq->front = lq->rear = (linknode_t *)malloc(sizeof(linknode_t));
    
    	lq->front->next = NULL;
    
    	return lq;
    }
    
    //入队
    int linkqueue_input(linkqueue_t *lq, datatype_t value)
    {
    	linknode_t *temp = (linknode_t *)malloc(sizeof(linknode_t));
    	temp->data = value;
    	temp->next = NULL;
    	
    	lq->rear->next = temp; //将入队的结点插入到rear后面
    	lq->rear = temp;    //将raer后移
    	//lq->rear = lq->rear->next;
    	
    	return 0;
    }
    
    //判断队列是否为空
    int linkqueue_empty(linkqueue_t *lq)
    {
    	return lq->front == lq->rear ? 1 : 0;
    }
    
    //出队（删除头结点）
    datatype_t linkqueue_output_del(linkqueue_t *lq)
    {
    	linknode_t *temp = NULL;
    	datatype_t value;
    
    	if(linkqueue_empty(lq))
    	{
    		printf("linkqueue is empty\n");
    		return (datatype_t)-1;
    	}
    
    	temp = lq->front;  //将要删除的头结点的地址赋值给temp
    	lq->front = lq->front->next; //front往后移，并且获取数据
    	value = lq->front->data;
    
    	free(temp);
    	temp = NULL;
    	
    	return value;
    }
    
    //出队（保留头结点）
    datatype_t linkqueue_output_undel(linkqueue_t *lq)
    {
    	linknode_t *temp = NULL;
    	datatype_t value;
    
    	if(linkqueue_empty(lq))
    	{
    		printf("linkqueue is empty\n");
    		return (datatype_t)-1;
    	}
    
    	temp = lq->front->next;
    	lq->front->next = temp->next;
    
    	value = temp->data;
    
    	free(temp);
    	temp = NULL;
    
    	if(lq->front->next == NULL)
    	{
    		lq->rear = lq->front;
    	}
    
    	return value;
    }
    
    int main(int argc, const char *argv[])
    {
    	linkqueue_t *lq = linkqueue_create();
    
    	linkqueue_input(lq, 10);
    	linkqueue_input(lq, 20);
    	linkqueue_input(lq, 30);
    	linkqueue_input(lq, 40);
    	linkqueue_input(lq, 50);
    
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	
    	linkqueue_input(lq, 10);
    	linkqueue_input(lq, 20);
    	linkqueue_input(lq, 30);
    	linkqueue_input(lq, 40);
    	linkqueue_input(lq, 50);
    
    	printf("del = %d\n", linkqueue_output_del(lq));
    	printf("del = %d\n", linkqueue_output_del(lq));
    	printf("del = %d\n", linkqueue_output_del(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    	printf("del = %d\n", linkqueue_output_undel(lq));
    
    	return 0;
    }