数据结构——队列之链式存储

叁歲伎倆 2022-06-17 01:28 260阅读 0赞

# 数据结构——队列之链式存储 #

队列的链式存储道理跟线性表一样，但是需要另外设定两个指针，一个指向队首、一个指向队尾：

![20170412192606752][]

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    /**队列的链式存储**/
    typedef struct Data{
    	char name[10];
    	int age;
    };
    typedef struct Queue{
    	Data data;
    	Queue *front;	//指向队首元素
    	Queue *next;	//指向下一个元素
    	Queue *rear;	//指向队尾元素
    };
    /**初始化空队列**/
    void InitQueue(Queue *Q){
    	Q->front = Q->rear = Q->next = NULL;
    }
    /**判断是否为空队列**/
    int QueueEmpty(Queue Q){
    	//为空返回1否则返回0
    	if(Q.front==NULL) return 1;
    	else return 0;
    }
    /**返回队首元素**/
    int GetFront(Queue Q,Data *d){
    	if(QueueEmpty(Q)==1){
    		printf("It's an empty stack!\n");
    		return 0;
    	}else{
    		strcpy(d->name,Q.front->data.name);
    		d->age = Q.front->data.age;
    		return 1;
    	}
    }
    /**从队尾插入新元素 入队**/
    void PushQueue(Queue *Q,Data d){
    	Queue* p = (Queue *)malloc(sizeof(Queue));
    	strcpy(p->data.name,d.name);
    	p->data.age = d.age;
    	p->rear = NULL;
    	p->next = NULL;
    	if(QueueEmpty(*Q)==1){
    		Q->front = p;
    		Q->rear = p;
    	}else{
    		Q->rear->next = p;
    		Q->rear = p;
    	}
    }
    /**从队首删除元素 出队**/
    void PopQueue(Queue *Q,Data *d){
    	if(QueueEmpty(*Q)==1){
    		printf("It's an empty stack!\n");
    	}else{
    		Queue *p = Q->front;
    		Q->front = p->next;
    		strcpy(d->name,p->data.name);
    		d->age = p->data.age;
    	}
    }
    /**清空队列**/
    void ClearQueue(Queue *Q){
    	if(QueueEmpty(*Q)==1){
    		printf("It's already an empty stack!\n");
    	}else{
    		Q->front = Q->next = Q->rear = NULL;
    	}
    }
    /**打印栈内信息**/
    void PrintQueue(Queue Q){
    	if(QueueEmpty(Q)==1){
    		printf("It's an empty stack!\n");
    	}else{
    		printf("name----age\n");
    		Queue *p = Q.front;
    		printf("%s    %d\n",p->data.name,p->data.age);
    		while(p->next!=NULL){
    			printf("%s    %d\n",p->next->data.name,p->next->data.age);
    			p = p->next;
    		}
    	}
    }
    void main(){
    	Data d;
    	char name[10];
    	int code;
    	int age;
    	int i=1;
    	Queue Q;
    	while(i){
    		printf("1、初始化空队列\t2、入队\t3、出队\t4、队首元素5、清空队6、打印信息\n");
    		scanf("%d",&i);
    		switch (i){
    			case 1:
    				InitQueue(&Q);
    				break;
    			case 2:
    				printf("Input the name: ");
    				scanf("%s",&d.name);
    				printf("Input the age: ");
    				scanf("%d",&d.age);
    				PushQueue(&Q,d);
    				break;
    			case 3:
    				PopQueue(&Q,&d);
    				printf("Deleted (%s,%d)\n",d.name,d.age);
    				break;
    			case 4:
    				code = GetFront(Q,&d);
    				if(code) printf("Top element is (%s,%d)\n",d.name,d.age);
    				break;
    			case 5:
    				ClearQueue(&Q);
    				break;
    			case 6:
    				PrintQueue(Q);
    				break;
    			default:
    				break;
    		}
    	}
    	system("pause");
    }

[20170412192606752]: /images/20220617/28517d95daee46e7bf443a94b61a5355.png