这一章我们来看队列 队列的概念:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 其实我们来对比栈,栈的特点是只能在一端进行操作的,而队列是一端插入一端删除。
用一句很有歧义却很形象的话来讲两者的区别就是:栈就是插进去抽出来,而队列是插进去吐出来。
我们还是上图来更加直观的看队列
队列分为两种,一种是顺序队列,一种是循环队列。 其实从存储结构上讲,队列也分为两种,一种是顺序队列,一种是链队列。 如果从存储上加以区分的话,在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。
顺序队列的简单实现(我们要采用数组) 初始是这样的,因为还没有存放任何元素
我们来看入队的过程
我们来看出队的过程
其实这里涉及假溢出和真溢出 我们来解释下
假溢出:就是明明存储空间还有,却放不下数据了。
真溢出:很好理解,就是真的插不进去了。因为空间真的不够用了,被塞满了。
我们来看顺序表实现队列的操作 上代码: 我们这样实现就很简单,避免了使用结构体
#include <stdio.h>
int PushQueue(int *a,int rear,int data){
a[rear]=data;
rear++;
return rear;
}
void DeQueue(int *a,int front,int rear){
while (front!=rear) { //当font=rear时,我们表示他为空
printf("出队元素:%d\n",a[front]);
front++;
}
}
int main() {
int a[100];
int front,rear;
//设置队头指针和队尾指针,当队列中没有元素时,队头和队尾指向同一块地址
front=rear=0;
//入队
rear=PushQueue(a, rear, 1);
rear=PushQueue(a, rear, 2);
rear=PushQueue(a, rear, 3);
rear=PushQueue(a, rear, 4);
//出队
DeQueue(a, front, rear);
return 0;
}
这样的顺序表的实现方式存在假溢出的假象。这样太浪费空间了。我我们想了一种办法,就是采用循环的结构,就是把它看做一个头尾相接循环结构。
我们要判断队满和队空,但是我们发现,在队满和队空的情况下,都存在head=tail的情况,或者是font=rear。我们想办法进行区分。
两种办法: 1:少用一个数据元素的空间,当队尾指针所指的空闲单元的后继单元是队头元素所在的单元时,我们就认为队满,不再插入新的元素。我们有这样判断(Q.rear+1)%MAXSIZE==Q.font,如果满足这个条件,队就满了。队空的条件不受影响,就是Q.rear == Q.font. 我们来看循环队列的结构体定义
#define MAXSIZE 1024
typedef int elemtype
typedef struct SequenQueue
{
elemtype data[MAXSIZE];
int font ;
int rear;
} SequenQueue;
我们来看一些操作
1:初始化
SequenceQueue *Init_SequenQueue()
{
SequenQueue * Q; //定义循环队列的指针变量
Q = (SequenQueue *)malloc (sizeof(SquenQueue))
if(Q!=NULL){
Q->font =0;
Q->rear =0;
}
return Q;
}
2:判断队列是否为空
int Sequen_Empty(SequenQueue * Q)
{
if(Q->rear==Q->font){
return 1;
}
else
{
return 0;
}
}
其他的操作都是大同小异的,注意用到空间申请函数了,我们要加上相应的头文件。
能够把复杂的东西做的简单才是最明智的。
我们还是不用结构体。。来看一个完整代码。
下面展示一些 内联代码片
。
#include <stdio.h>
#define max 5//表示顺序表申请的空间大小
int enQueue(int *a,int front,int rear,int data){
//添加判断语句,如果rear超过max,则直接将其从a[0]重新开始存储,如果rear+1和front重合,则表示数组已满
if ((rear+1)%max==front) {
printf("空间已满");
return rear;
}
a[rear%max]=data;
rear++;
return rear;
}
int deQueue(int *a,int front,int rear){
//如果front==rear,表示队列为空
if(front==rear%max) {
printf("队列为空");
return front;
}
printf("%d ",a[front]);
//front不再直接 +1,而是+1后同max进行比较,如果=max,则直接跳转到 a[0]
front=(front+1)%max;
return front;
}
int main() {
int a[max];
int front,rear;
//设置队头指针和队尾指针,当队列中没有元素时,队头和队尾指向同一块地址
front=rear=0;
//入队
rear=enQueue(a,front,rear, 1);
rear=enQueue(a,front,rear, 2);
rear=enQueue(a,front,rear, 3);
rear=enQueue(a,front,rear, 4);
//出队
front=deQueue(a, front, rear);
//再入队
rear=enQueue(a,front,rear, 5);
//再出队
front=deQueue(a, front, rear);
//再入队
rear=enQueue(a,front,rear, 6);
//再出队
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
return 0;
}
如果不是很理解结构体,用这种方式其实也是同样的道理。 我们来看链栈如何实现 链队列的初始状态
初始状态,尾指针和头指针都指向头结点。 我们来看结构;
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
1:初始化:
下面展示一些 内联代码片
。
QNode * initQueue(){
//创建一个头节点
QNode * queue=(QNode*)malloc(sizeof(QNode));
//对头节点进行初始化
queue->next=NULL;
return queue;
2:入队操作:
下面展示一些 内联代码片
。
QNode* enQueue(QNode * rear,int data){
//1、用节点包裹入队元素
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//2、新节点与rear节点建立逻辑关系
rear->next=enElem;
//3、rear指向新节点
rear=enElem;
//返回新的rear,为后续新元素入队做准备
return rear;
}
3:出队操作
我们来看代码:
下面展示一些 内联代码片
。
void DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("队列为空");
return ;
}
// 1、
QNode * p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
这里和链表真的太像了 我们来看完整代码;
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
QNode * initQueue(){
QNode * queue=(QNode*)malloc(sizeof(QNode));
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//使用尾插法向链队列中添加数据元素
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("\n队列为空");
return rear;
}
QNode * p=top->next;
printf("%d ",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
int main() {
QNode * queue,*top,*rear;申明头结点,top指针,和尾指针。
queue=top=rear=initQueue();//创建头结点
//向链队列中添加结点,使用尾插法添加的同时,队尾指针需要指向链表的最后一个元素
rear=enQueue(rear, 1);
rear=enQueue(rear, 2);
rear=enQueue(rear, 3);
rear=enQueue(rear, 4);
//入队完成,所有数据元素开始出队列
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
return 0;
}
oj8k,队列的总结就到这里了。 相关的请遵守csdn协议 -------博主jgdabc