【数据结构】链式队列的一些操作

比眉伴天荒 2022-08-25 09:13 228阅读 0赞

详细见代码：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct ElemType
    {
    	int data;
    	ElemType *next;
    }ElemType;                        // next 是 元素的指针 指向下一个元素的位置
    
    typedef struct
    {
    	ElemType *front;
    	ElemType *rear;
    }Queue,*PsQueue;                  // 队列头指针 和 队列尾指针
    
    
    void initQueue(Queue * sq);       // 初始化
    void DestoryQueue (Queue * sq);   //销毁队列  
    void EnQueue (Queue * sq,int e);  //进队列  
    void DeQueue (Queue * sq);        //出队列  
    void GetHead (Queue * sq);        //取队头元素值  
    bool QueueEmpty (Queue sq);       //判队列空否  
    void DisQueue(Queue * sq);        // 遍历队列中元素  
    
    void main()
    {
    	int size = 0;  
    	char choice = '\0'; 
    	Queue sQueue = {0,};
    	PsQueue PsQueue = &sQueue;
    
    	initQueue(PsQueue);
    
    	while (choice != 'q')  
    	{  
    		printf("******************************\n");  
    		printf("---    1   元素进队       --- \n");  
    		printf("---    2   队头出队       --- \n");  
    		printf("---    3   遍历队中元素   --- \n");  
    		printf("---    4   判队列空否     --- \n");  
    		printf("---    5   取队头元素值   --- \n");  
    		printf("---    6   销毁队列       --- \n");  
    		printf("---    q   退出           --- \n");  
    		printf("******************************\n");  
    
    		scanf("\n%c",&choice);  
    
    		switch (choice)  
    		{  
    		case '1':  
    			printf("输入进栈元素个数:");  
    			scanf("%d",&size);  
    
    			for (int i = 0; i < size; i++)  
    				EnQueue (&sQueue, i+1) ; //进队列   
    			break;  
    		case '2':  
    			DeQueue(&sQueue);  
    			break;  
    		case '3':  
    			DisQueue(&sQueue);  
    			break;  
    		case '4':  
    			QueueEmpty(sQueue);
    			break;  
    		case '5':  
    			GetHead(&sQueue);  
    			break;  
    		case '6':  
    			DestoryQueue(&sQueue);  
    			break;  
    		case 'q':  
    			return;  
    
    		} 
    	}  
    }
    
    void initQueue(Queue * sq)  // 初始化
    {
    	sq->rear = sq->front = (ElemType *)malloc(sizeof(ElemType)); // 指向同一处内存空间
    }
    
    
    void DestoryQueue (Queue * sq) //销毁队列
    {
    	while (sq->front->next != NULL)
    	{
    		ElemType *p = sq->front->next;
    		sq->front->next = sq->front->next->next;
    		free(p);
    	}
    
    	free(sq->front);
    }
    
    
    void EnQueue (Queue * sq,int e) //进队列
    {
    	sq->rear->next = (ElemType *)malloc(sizeof(ElemType));
    	sq->rear = sq->rear->next;
    
    	sq->rear->data = e;
    	sq->rear->next = NULL;
    }
    
    
    void DeQueue (Queue * sq) //出队列
    {
    	// 队头出队
    	if (sq->front == sq->rear)
    	{
    		printf("队列为空，不能出队~\n");
    		return;
    	}
    	else
    	{
    		ElemType *p =sq->front->next;
    		printf("出队元素为 %d\n",p->data);
    
    		sq->front->next = sq->front->next->next;
    		free(p);
    	}
    }
    
    
    void GetHead (Queue * sq) //取队头元素值
    {
    	printf("队头元素为 %d\n",sq->front->next->data);
    }
    
    
    bool QueueEmpty (Queue sq) //判队列空否
    {
    	if (sq.front == sq.rear)
    	{
    		printf("队列为空~\n");
    		return true;
    	}
    	else
    	{
    		printf("队列不为空~\n");
    		return false;
    	}
    }
    
    
    void DisQueue(Queue * sq)  // 遍历队列中元素
    {
    	ElemType * p = sq->front;
    
    	while (p->next != NULL)
    	{
    		p = p->next;
    		printf("%d\t",p->data);	
    	}
    
    	printf("\n");	
    }