C语言-数据结构-链队列

以你之姓@ 2022-05-11 02:52 232阅读 0赞

\*\*

## **链式队列** ##

\*\*

使用两种不同的方式作为初始化,  
特点:  
一种是传递 Init(&Q);  
一种是直接P Q = create(); 我觉得还是这种的方式比较灵活,对比见程序

注:我的习惯是直接写成头文件,方便调用

这个程序使用的 是InitQueue(PQueue Q)  
\#ifndef \_*QUEUECHAIN*  
\#define \_*QUEUECHAIN*  
//声明头文件  
\#include “stdio.h”  
\#include “malloc.h”  
\#include “stdbool.h”  
\#include “stdlib.h”

/* 声明结构体 */ 
    typedef struct Node{
    	int data;
    	struct Node *next;
    }Node,*PNode;
    
    typedef struct Stack{
    	PNode front, rear; //指向Node的front和rear 
    }Queue,*PQueue;
    
    
    //队列
    //创建创建队列 Q->front = Q->rear; next = NULL;
    //判断队列为空 Q->front = Q->rear;
    //入队 新建结点,插入到链尾,尾指针指向该结点 Node给rear 
    //出队 判断队空; 直接出队,释放		输出front->next 
    
    
    void InitQueue(PQueue Q)  //这里传的是指针 
    {
    	Q->front = Q->rear = (PNode)malloc(sizeof(Node));
    	Q->front->next = NULL;
    	return; 
    }
    
    bool IsEmpty(PQueue Q)
    {
    //	printf("dsg\n");
    	if(Q->front == Q->rear)
    	{
    		return true;
    	}
    	return false;
    }
    
    
    void QueuePosh(PQueue Q, int val)
    {
    	PNode N = (PNode)malloc(sizeof(Node)); //create temp node
    	N->data = val;
    	N->next = NULL;
    	
    	Q->rear->next = N;	//rear to next
    	Q->rear = N;	//rear->N
    //	printf("%d\n",Q->front->next->data); 
    //	printf("%d\n",Q->rear->data);
    	return;
    }
    
    void QueuePop(PQueue Q,int *val)
    {
    	if(IsEmpty(Q))
    	{
    		printf("Queue is Empty!\n");return;
    	}
    	
     	PNode N = Q->front->next;
     	*val = N->data;
     	Q->front->next = N->next; 
     	if(Q->rear == N) Q->rear = Q->front; //原队列只有一个结点,删除后为空 
     	free(N);
     	return;		
    }
    
    
     //头文件 
    //void main()
    //{
    //	Queue Q; 
    //	int val;
    //	InitQueue(&Q); //这里传的是指针 
    //	QueuePop(&Q,&val);
    //	QueuePosh(&Q,23);
    //	
    //	QueuePop(&Q,&val);
    //	QueuePop(&Q,&val);
    //	
    //	QueuePosh(&Q,34);
    //	QueuePosh(&Q,4);
    //	QueuePosh(&Q,56);
    //	QueuePosh(&Q,33);
    //	QueuePop(&Q,&val);
    //	printf("pop%d\n",val);
    //	QueuePop(&Q,&val);
    //	printf("pop%d\n",val);
    //	printf("\n\nhello world;!\n\n"); 
    //	return;
    //}
    #endif

## 下面这个是更新的 Create直接返回指着地址 ##

#ifndef __QUEUECHAINCREAT_
    #define __QUEUECHAINCREAT_
    //声明头文件 
    #include "stdio.h"
    #include "malloc.h"
    #include "stdbool.h"
    #include "stdlib.h"
    /* 声明结构体 */ 
    typedef struct Node{
    	int data;
    	struct Node *next;
    }Node,*PNode;
    
    typedef struct Stack{
    	PNode front, rear; //指向Node的front和rear 
    }Queue,*PQueue;
    
    //队列
    //创建创建队列 Q->front = Q->rear; next = NULL;
    //判断队列为空 Q->front = Q->rear;
    //入队 新建结点,插入到链尾,尾指针指向该结点 Node给rear 
    //出队 判断队空; 直接出队,释放		输出front->next 
    
    
    //这种初始化比较方便,在后面的程序中就可以直接使用Q指针,而不需要在使用&Q来改变Q里面的数据 
    PQueue CreatQueue()
    {
    	PQueue Q = (PQueue)malloc(sizeof(Queue)); //开辟PQueue指针的空间 
    	Q->front = Q->rear = (PNode)malloc(sizeof(Node)); //开辟结点的空间,此时front和rear都指向一个位置 
    	Q->front->next = NULL;
    	return Q;	 
    } 
    
    bool IsEmpty(PQueue Q)
    {
    	if(Q->front == Q->rear)
    	{
    		return true;
    	}
    	return false;
    }
    
    
    void QueuePosh(PQueue Q, int val)
    {
    	PNode N = (PNode)malloc(sizeof(Node)); //create temp node
    	N->data = val;
    	N->next = NULL;
    	Q->rear->next = N;	//rear to next
    	Q->rear = N;	//rear->N
    	return;
    }
    
    void QueuePop(PQueue Q, int *val)
    {
    	if(IsEmpty(Q))
    	{
    		printf("Queue is Empty!\n");return;
    	}
    	
     	PNode N = Q->front->next;
     	*val = N->data;
     	Q->front->next = N->next; 
     	if(Q->rear == N) Q->rear = Q->front; //原队列只有一个结点,删除后为空 
     	free(N);
     	return;		
    }
    
    
    
    //void main()
    //{
    //	PQueue Q = CreatQueue(); 
    //	int val;
    //
    //	QueuePop(Q,&val);
    //	QueuePosh(Q,23);
    //	
    //	QueuePop(Q,&val);
    //	QueuePop(Q,&val);
    //	
    //	QueuePosh(Q,34);
    //	QueuePosh(Q,4);
    //	QueuePosh(Q,56);
    //	QueuePosh(Q,33);
    //	QueuePop(Q,&val);
    //	printf("pop%d\n",val);
    //	QueuePop(Q,&val);
    //	printf("pop%d\n",val);
    //} 
    #endif