数据结构之队列C语言实现

太过爱你忘了你带给我的痛 2022-05-27 00:45 202阅读 0赞

C语言实现循环队列：

实现队列需要理解先进先出的思想，可以先看一下数据机构的书籍，不做过多累述

定义为顺序表形式。

typedef struct{
    	Elemtype data[MaxSize];
    	int front,rear;
    }Queue;

MaxSize表示队列最大值，其中front表示队首元素的位置，rear表示队尾元素+1的位置

初始化：

//初始化队列 
    bool InitQueue(Queue &Q){
    	Q.front = Q.rear = 0;
    }

队首指针值与队尾指针值相等时队列为空，我们这里初始化为空

判空：

//判空 
    bool IsEmpty(Queue &Q){
    	if(Q.front == Q.rear){
    		return true;
    	}
    	return false;
    }

元素入队：

//入队
    bool PushQueue(Queue &Q,int val){
    	if((Q.rear+1)%MaxSize == Q.front){
    		return false;
    	}
    	Q.data[Q.rear] = val;
    	Q.rear = (Q.rear+1)%MaxSize;
    	//printf("入队成功%d\n",Q.data[Q.rear-1]); 
    	return true;
    }

首先判断是否队列已满，然后赋值val于队尾Q.rear的位置。

(Q.rear+1)%MaxSize == Q.front：拿出一个位置不存元素，从而区别当rear与front相等时队列可能为满也可能为空的情况

Q.rear = (Q.rear+1)%MaxSize：队尾指针加一，通过取模实现循环

出队：

//出队 
    int PopQueue(Queue &Q){
    	int val;
    	if(Q.front == Q.rear){
    		return -1;
    	}
    	val = Q.data[Q.front];
    	Q.front = (Q.front+1)%MaxSize;
    	return val; 
    }

判空，取值，队尾指针加一

队列长度：

//队列长度
    int QueueLength(Queue &Q){
    	return (Q.rear-Q.front+MaxSize)%MaxSize;
    }

完整代码：

#include<cstdio>
    #include<cstdlib>
    #include<iostream>
    #define MaxSize 6 
    #define Elemtype int
    using namespace std;
    typedef struct{
    	Elemtype data[MaxSize];
    	int front,rear;
    }Queue;
    //创建队列 
    Queue createQueue(){
    	Queue *que = (Queue *)malloc(sizeof(Queue));
    	return *que; 
    }
    //初始化队列 
    bool InitQueue(Queue &Q){
    	Q.front = Q.rear = 0;
    }
    //判空 
    bool IsEmpty(Queue &Q){
    	if(Q.front == Q.rear){
    		return true;
    	}
    	return false;
    } 
    
    //入队
    bool PushQueue(Queue &Q,int val){
    	if((Q.rear+1)%MaxSize == Q.front){
    		return false;
    	}
    	Q.data[Q.rear] = val;
    	Q.rear = (Q.rear+1)%MaxSize;
    	//printf("入队成功%d\n",Q.data[Q.rear-1]); 
    	return true;
    }
    //出队 
    int PopQueue(Queue &Q){
    	int val;
    	if(Q.front == Q.rear){
    		return -1;
    	}
    	val = Q.data[Q.front];
    	Q.front = (Q.front+1)%MaxSize;
    	return val; 
    }
    //队列长度
    int QueueLength(Queue &Q){
    	return (Q.rear-Q.front+MaxSize)%MaxSize;
    } 
    int main(){
    	int x,val;
    	bool flag;
    	Queue que = createQueue();
    	InitQueue(que);
    	while(scanf("%d",&x),x){//x等于0退出 
    		switch(x){
    			case 1:
    				printf("输入一个数入队：\n");
    				scanf("%d",&val);
    				flag = PushQueue(que,val);
    				if(flag == true){
    					printf("%d成功入队\n",val);
    				}
    				else{
    					printf("队列已满\n");
    				}
    				break;
    			case 2:
    				val = PopQueue(que);
    				if(val!=-1){
    					printf("%d成功出队\n",val);
    				}
    				else {
    					printf("队列为空\n"); 
    				}
    				break;
    			case 3:
    				val = QueueLength(que);
    				printf("队列长度为%d\n",val);
    				break;
    		}
    	} 
    	return 0;
    }

运行截图：

![20180408205620887][]

![20180408205638806][]

[20180408205620887]: /images/20220527/4202e95447f349f99eb607176587fb22.png
[20180408205638806]: /images/20220527/b96cac8c633f4f0b87d9d85c8495a4d7.png