顺序队基本运算算法——C/C++

Myth丶恋晨 2022-01-16 07:51 179阅读 0赞

## 队列 ##

**1、简介**

1.  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
2.  队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first  
    in first out）线性表。

**2、队列示意图**

2.1、队列映射示意图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]  
2.2、队列操作过程示意图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]**3、顺序队列的重要要素**

1.  队空的条件：q->front==q->rear。
2.  队满的条件：q->rear==MaxSize-1(data数组的最大下标)。
3.  元素的进队操作：先将rear加1，然后将元素c放入data的数组的rear位置。
4.  出队操作：先将front加1，然后取出data的数组的front位置元素。

**4、各个函数接口**

//初始化队列 
    void initQueue(SqQueue * &q)
    //销毁队列
    void destroyQueue(SqQueue * &q)
    //判断队列是否为空
    bool emptyQueue(SqQueue * &q)
    //进队列
    bool enQueue(SqQueue * &q,char c)
    //出队列 
    bool deQueue(SqQueue * &q,char ch)

**5、函数实现及解释**  
用到的库基本库<stdio.h>、需要分配地址空间的库<malloc.h>

#include<stdio.h>
    #include<malloc.h>
    
    #define MaxSize 1024				//定义MaxSize为1024
    
    typedef struct Quene{				//定义顺序队 
    	int front;						//队头指针 
    	char data[MaxSize];				//存放队中元素 
    	int rear;						//队尾指针 
    }SqQueue; 							//struct Queue 的别名

5.1、初始化队列

void initQueue(SqQueue * &q){
    	q=(SqQueue *)malloc(sizeof(SqQueue));	//分配一个空间 
    	q->front=q->rear=-1;					//置 -1 
    }

5.2、销毁队列

void destroyQueue(SqQueue * &q){
    	free(q);								//释放内存 
    }

5.3、判断队列是否为空

bool emptyQueue(SqQueue * &q){
    	if(q->front==q->rear){					//首指针和尾指针相等，说明为空 
    		return true;						//返回真 
    	}
    	else{
    		return false;						//返回假 
    	}
    }

5.4、进队列

bool enQueue(SqQueue * &q,char c){
    	if(q->rear==MaxSize-1){					//判断队列是否满了 
    		return false;						//返回假 
    	}
    	q->rear++;								//头指针加 1 
    	q->data[q->rear]=c;						//传值 
    	return true;							//返回真 
    }

5.5、出队列

bool deQueue(SqQueue * &q,char ch){
    	if(q->front==q->rear){					//判断是否空了 
    		return false;						//返回假 
    	}
    	q->front++;								//尾指针加 1 
    	ch=q->data[q->front];					//取值 
    	printf("%c",ch);						//输出值 
    	return true;							//返回真 
    }

**6、结果展示**  
主函数

int main(){
    	SqQueue *Q;
    	initQueue(Q);
    	printf("初始化成功\n");
    	
    	//销毁队列 
    //	destroyQueue(Q);
    	
    	int n=0;
    	char *str=(char *)malloc(sizeof(char) * MaxSize);
    	printf("请输入要加入元素：");
    	scanf("%s",str);
    	while(n<MaxSize){
    		char c=str[n];
    		n++;
    		if(c!='\0'){
    			enQueue(Q,c);
    		}
    		else{
    			break;
    		}
    	}
    	printf("加入成功"); 
    	printf("\n");
    	
    	char ch;
    	printf("队列元素：");
    	while(emptyQueue(Q)==false){
    		deQueue(Q,ch);
    	}
    	
    	return 0;
    }

结果展示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20220114/9bc8ad797a2b43c1a5bd36d0b9a22599.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20220114/de2e64c1ce2b41a8ac4d2bb2cd6ed1aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20220114/39f670bab076431bb0ad30d8d0a5d020.png