C语言实现队列的定义及其基本操作

r囧r小猫 2023-07-19 16:27 15阅读 0赞

## 队列的基本操作 ##

1.  **队列的定义**
2.  **队列的特点**
3.  **队列的存储结构**
4.  **顺序队列的定义及其基本操作**
5.  **链队的定义及其基本操作**
    
    **1、队列的定义**  
    队列，简称队，它是一种操作受限的线性表，其限制在表的一端进行插入，另一端进行删除。可进行插入的一端称为**队尾（rear）**,可进行删除的一端称为**队头（front）**。向队中插入元素叫入队，新元素进入之后就称为新的队尾元素。从队中删除元素叫出队，元素出队后，其后继结点元素就称为新的队头元素。  
    **2、队列的特点**  
    队的特点就是**先进先出**（栈为先进后出）。打个比方，队列就是在食堂吃饭的时候排队，先到的人先拿到饭，后到的人后拿到。  
    **3、队列的存储结构**  
    队列按存储结构可分为链队和顺序队两种。  
    **4、顺序队列**  
    主要来说循环队列

定义：

typedef struct{
        
       QelemType  *base;
       int front;
       int rear;
       }squene;

**约定**：空队列 Q.front=Q.rear  
队满 Q.front=(Q.rear+1)%MAXSIZE  
入队 Q.rear++  
出队 Q.front++  
非空队列：front始终指向队头元素，rear始终指向队尾元素的下一位置  
每插入一个元素，rear=（rear+1）%（MAXSIZE）  
每删除一个元素，front=（front+1）%（MAXSIZE）  
循环队列示意图在这里插入图片描述

**初始化**

void Initquene(squene &s){
        
    	s.base=(QelemType *)malloc(sizeof(QelemType));
    	if(!s.base)
    		exit(-1);
    	s.front=0;
    	s,rear=0;
    }

**入队操作**

void enquene(squene &s,QelemType e){
        
    	if(((s.base+1)%MAXSIZE)==s.front){
        
    	printf("队满");
    	exit(-1);
    	}
    	s.base[s.rear]=e;
    	s.rear=(s.rear+1)%MAXSIZE;
    }

**出队操作**

void dequene(squene &s,QelemType e){
        
    	if(s.rear==s.front){
        
    	printf("栈空");
    	exit(-1);
    	}
    	e=s.base[s.front];
    	s.front=(s.front+1)%MAXSIZE;
    }

**求队的长度**

int length(squene s){
        
    	return (s.rear-s.front+1) % MAXSIZE;
    }

**全部代码为：**

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    typedef int QelemType;
    typedef struct{
        
    	QelemType *base;
    	int front;
    	int rear;
    }squene;
    void Initquene(squene &s){
        
    	s.base=(QelemType *)malloc(MAXSIZE * sizeof(QelemType));
    	if(!s.base)
    	exit(-1);
    	s.front=0;
    	s.rear=0;
    }
    void enquene(squene &s,QelemType e){
        
    	if((s.rear+1)%MAXSIZE==s.front){
        
    		printf("duimanb");
    		exit(0);
    	}
    	s.base[s.rear]=e;
    	s.rear=(s.rear+1)%MAXSIZE;
    }
    void dequene(squene &s,QelemType e){
        
    	if(s.rear==s.front){
        
    	printf("栈空");
    	exit(-1);
    	}
    	e=s.base[s.front];
    	s.front=(s.front+1)  % MAXSIZE;
    }
    int length(squene s){
        
    	return (s.rear-s.front+MAXSIZE) % MAXSIZE;
    }
    int main(){
        
    	squene s;
    	Initquene(s);
    	int m,n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
        
    		scanf("%d",&m);
    		enquene(s,m);
    	}
    	printf("%d",length(s));
    	return 0;
    }

## 5、链队 ##

**链队的定义**

typedef struct QNode{
        
    	QElemType data;
    	struct QNode *next;
    }Qnode,*Queneptr;	
    typedef struct{
        
    	Queneptr front;//队头指针
    	Queneptr rear;//队尾指针
    }LinkQuene;

**约定:**  
队空：s.front=s.rear（有头结点）  
s.front=NULL（无头结点）  
链队无队满的情况（假定内存足够大）  
进队操作

s->rear->next=p;
    s->rear=p;

**出队操作**

p=s->front;
    s->front=p->next;(或者s->front=s->front->next;)
    x=p->data;
    free ( p );

## 算法实现 ##

**1、初始化**

Initquene(LinkQuene &s){
        
    	s.front=(Queneptr *)malloc(sizeof(Qnode));
    	if(!s.front)
    		exit(-1);
    	s.rear=s.front;
    	s.front->next=NULL;
    }

**2、判断队空**

int isqueneempty(LinkQuene &s){
        
    	if(s.rear==NULL||s.front==NULL)
    		return 1;
    	return 0;
    }

**3、入队**

void enquene(LinkQuene &s,QElemType e){
        
    	Queneptr p=(Queneptr *)malloc(sizeof(Qnode));
    	if(!p)
    		exit(-1);
    	p->data=e;
    	p->next=NULL;
    	s.rear->next=p;
    	s.rear=p;
    }

**4、出队**

void dequene(LinkQuene &s,QElemType &e){
        
    	if(s.rear==NULL||s.front==NULL){
        
    		printf("对空");
    		exit(-1);
    	}
    	Queneptr p=s.front->next;
    	e=p->data;
    	s.front->next=p->next;
    	if(s.rear==p)
    		s.rear=s.front;
    	free(p);
    }

**5、销毁队列**

int destory(LinkQuene &s){
        
    	while(s.front){
        
    		s.rear=s,front->next;
    		free(s.front);
    		s.front=s.rear;
    	}
    	if(s.rear==s.front)
    		return 1;
    	return 0;
    }

6、全部代码

#include<stdio.h>
    #include<stdlib.h>
    typedef int QElemType;
    typedef struct QNode{
        
    	QElemType data;
    	struct QNode *next;
    }Qnode,*QuenePtr;
    typedef struct{
        
    	QuenePtr front;
    	QuenePtr rear;
    }LinkQuene;
    void Initquene(LinkQuene &s){
        
    	s.front=(QuenePtr)malloc(sizeof(Qnode));
    	if(!s.front)
    		exit(-1);
    	s.rear=s.front;
    	s.front->next=NULL;
    }
    void enquene(LinkQuene &s,QElemType e){
        
    	QuenePtr p=(QuenePtr)malloc(sizeof(Qnode));
    	if(!p)
    		exit(-1);
    	p->data=e;
    	p->next=NULL;
    	s.rear->next=p;
    	s.rear=p;
    }
    void dequene(LinkQuene &s,QElemType &e){
        
    	if(s.front==s.rear){
        
    		printf("出错");
    		exit(0);
    	}
    	QuenePtr p=s.front->next;
    	e=p->data;
    	s.front->next=p->next;
    	if(s.rear==p){
        
    		s.rear=s.front;
    	}
    	free(p);
    }
    int Destory(LinkQuene &s){
        
    	while(s.front){
        
    		s.rear=s.front->next;
    		free(s.front);
    		s.front=s.rear;
    	}
    	if(s.front==s.rear){
        
    		return 1;
    	}
    	return 0;
    }
    void print(LinkQuene s,int n){
        
    	QuenePtr p=s.front->next;
    	while(p!=s.rear){
        
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("%d",p->data);
    	printf("\n");
    }
    int main(){
        
    	LinkQuene s;
    	Initquene(s);
    	int n,m,x;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
        
    		scanf("%d",&m);
    		enquene(s,m);
    	}
    	print(s,n);
    //	printf("\n");
    	dequene(s,x);
    	printf("%d",x);
    	printf("\n");
    	print(s,n-1);
    	int a=Destory(s);
    	if(a==1)
    	printf("已销毁");
    	else
    	printf("还没销毁呢***");
    	return 0;
    }

————————————————  
版权声明：本文为CSDN博主「qq\_42338808」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/qq\_42338808/article/details/83247086