数据结构~10.顺序队和链队

布满荆棘的人生 2023-03-03 04:54 6阅读 0赞

# 数据结构~10.顺序队和链队 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

## 顺序队 ##

### 循环队列 ###

在顺序队中,通常让队尾指针rear指向刚进队的元素位置,让队首指针front指向刚出队的元素位置。因此,元素进队的时候,rear要向后移动:元素出队的时候,front也要向后移动。这样经过一系列的出队和进队操作以后,两个指针最终会达到数组末端MAXSIZE - 1 处。虽然队中已经没有元素,但仍然无法让元素进队,这就是所谓的 "假溢出"。要解决这个问题,我们可以把数组弄成一个环，让rear和front绕着一个环走,这样就永远不会出现两者来到数组尽头无法继续往下走的情况。

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    //顺序队的定义
    typedef struct { 
    	int data[MAXSIZE];
    	int front;				//队首指针
    	int rear;				//队尾指针
    }SqQueue;					//顺序队结点类型定义
    
    //初始化操作
    void initQueue(SqQueue &list) { 
    	//队首和队尾指针重合并且指向0
    	list.front = list.rear = 0;
    }
    
    //判断队空算法
    int isEmpty(SqQueue list) { 
    	//不论队首和队尾在哪个位置,重合即是空
    	return list.front == list.rear ? 1 : 0;
    }
    
    //进队算法
    int push(SqQueue &list,int x) { 
    	//假如队满,则不能进队
    	if ((list.rear + 1) % MAXSIZE == list.front) { 
    		return 0;
    	}
    	//如果没满就先移动指针
    	list.rear = (list.rear + 1) % MAXSIZE;
    	//存入元素
    	list.data[list.rear] = x;
    	return 1;
    }
    
    //出队算法
    int pop(SqQueue &list) { 
    	//如果队列空,则不能出队
    	if (isEmpty(list) == 1) { 
    		return 0;
    	}
    	//如果队列不空,就先移动指针
    	list.front = (list.front + 1) % MAXSIZE;
    	//取出元素
    	return list.data[list.front];
    }
    
    //遍历
    void Print(SqQueue list) { 
    	int i;
    	for (i = list.front + 1; i <= list.rear; i++) { 
    		//判断是否到了最后
    		if (i != list.rear) { 
    			printf("%d -> ",list.data[i]);
    		}
    		else { 
    			printf("%d\n",list.data[i]);
    		}
    	}
    }
    
    int main(int argc,char *argv[]) { 
    	SqQueue list;
    	initQueue(list);
    	int i;
    	for (i = 1; i < 10; i++) { 
    		push(list,i);
    	}
    	Print(list);
    	//出队
    	int n = pop(list);
    	printf("出队的元素: %d\n",n);
    	Print(list);
    	getchar();
    }

## 链队 ##

链队就是采用链式存储结构存储队列,这里的话呢,就采用单链表来实现吧!链队的特点主要就是基本上不存在满的情况。

##### 链队的状态 #####

队空状态

list->rear == NULL 或者 list->front == NULL

### 链队代码实现 ###

#include<stdio.h>
    #include<stdlib.h>
    //链队定义
    //队结点类型
    typedef struct QNode { 
    	int data;				//数据域
    	struct QNode* next;		//指针域
    }QNode;						//队结点类型定义
    //链队类型定义
    typedef struct { 
    	QNode* front;			//队头指针
    	QNode* rear;			//队尾指针
    }LiQueue;					//链队类型定义
    
    //初始化链队
    void initQueue(LiQueue *&list) { 
    	list = (LiQueue*)malloc(sizeof(LiQueue));
    	list->front = list->rear = NULL;
    }
    
    //判断队空
    int isEmpty(LiQueue *list) { 
    	return (list->front == NULL || list->rear == NULL) ? 1 : 0;
    }
    
    //入队
    void push(LiQueue *list,int x) { 
    	QNode* p = (QNode*)malloc(sizeof(QNode));
    	p->data = x;
    	p->next = NULL;
    	if (list->rear == NULL) { 
    		//如果队列为空,那么新结点即是队尾也是队首
    		list->front = list->rear = p;
    	}
    	else { 
    		//将新结点连接到队尾,rear指向它
    		list->rear->next = p;
    		list->rear = p;
    	}
    }
    //出队操作
    int pop(LiQueue *list) { 
    	QNode* p;
    	int x;
    	//队空不能出队
    	if (list->rear == NULL) { 
    		return 0;
    	}
    	else { 
    		p = list->front;
    	}
    	//队列中只有一个结点时出队操作需特殊处理
    	if (list->front == list->rear) { 
    		list->front = list->rear = NULL;
    	}
    	else { 
    		list->front = list->front->next;
    	}
    	x = p->data;
    	free(p);
    	return x;
    }
    
    //遍历操作
    void Print(LiQueue *list) { 
    	// 遍历
    	QNode* temp = list->front;
    	while (temp != NULL) { 
    		printf("%d ",temp->data);
    		temp = temp->next;
    	}
    	printf("\n");
    }
    
    int main(int argc,char*argv[]) { 
    	LiQueue* list;
    	int n;
    	//初始化
    	initQueue(list);
    	int i;
    	//进队
    	for (i = 1; i < 10; i++) { 
    		push(list,i);
    	}
    	//遍历
    	Print(list);
    	//出队
    	n = pop(list);
    	printf("出队的值是: %d\n",n);
    	Print(list);
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107643349