在了解队列前,我们还需要了解一下线性表
线性表:是具有相同数据类型的n个数据元素的有限序列,其中n为表长,当n等于0的时候说明这个线性表是一个空表
栈:是只允许在一端进行插入和删除的线性表;
有关栈的博客:数据结构——栈
队列定义:是只允许在一端进行插入,在另一端删除的线性表;
请看下列彩图;
F从队尾插进队列,A从队头从队列中删除
有关队列的重要术语:队头,队尾,空队列
队头:允许删除元素的一端
队尾:允许插入的一端
空队列:队列里面没有元素
队列的特点:先进先出(FIFO)
队列的定义:(一种抽象数据类型(ADT)。队列是一种线性数据结构,它包含一系列按顺序排列的元素,并且具有先进先出(FIFO)的特性。队列可以通过数组、链表或其他数据结构来实现,但它本身是一种抽象概念,不一定要用结构体来实现,但是由于是萌新吧,我觉得我能定义的队列就是由结构体所构成的)
#define maxsize 10 //定义队列中元素的最大个数 typedef int ElemType; typedef struct { ElemType data[maxsize]; //存放队列元素 int front,rear;//队头指针和队尾指针 } SqQueue;
和栈差不多,“还是熟悉的配方”,那我们一起来看看都有那些操作呢?
创,增,删,查,判空/判满
1.InitQueue(*Q):初始化队列,构造一个空队列
void InitQueue(*Q) { Q.front=0;//将队头指针和队尾指针都指向0 Q.rear=0; //队头指针指向的事队头元素;队尾指针指向的事即将插入元素的位置 }
2.判空:判断这个队列是否是空队列
bool QueueEmpty(SqQueue Q) { if(Q.front==Q.rear)//如果队头指针等于队尾指针则说明是空队列 { return true; } else { return false' } }
循环队列:后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
该怎么去实现,就需要(Q.rear+1)%maxsize
那么判满条件是什么呢?是否是Q.rear==Q.front呢?
那么很明显应该不是,否则和判空条件一样了,无法进行区分
真正的判满条件:(Q.rear+1)%maxsize==Q.front
这么做确实可以区分,但是代价就是要浪费一个空间(后续会将不浪费空间的)
3.EnQueue(*Q,x):入队,若队列Q未满,将x加入,使其成为新的队尾
bool EnQueue(SqQueue *Q,ElemType x)//入队操作 { if(Q.rear+1)%maxsize==Q.front)//判满条件 { return false;//满了就直接报错 } Q.data[Q.rear]=x;//如果队列没有满,那么我们将新来的元素x存储在队尾指针指向的位置 Q.rear=(Q.rear+1)%maxsize;//队尾指针自增,指向下一个该插入的位置 return true; }
4.DeQueue(*Q,*x):出队:若队列非空,删除队头元素,并用x返回;
bool DeQueue(SqQueue *Q,ElemType *x) { if(Q.front==Q.rear)//判空条件 { return false;//是空的直接报错 } x=Q.data[Q.front];//将队头元素出队 Q.front=(Q.front+1)%maxsize;//将队头元素向后移一下 return true; }
5.GetHead(Q,*x):读取队头元素,若队列Q非空,则将队头元素赋给x
bool GetHead(SqQueue Q,ElemType *x) { if(Q.front==Q.rear)//判空条件 { return false;//是空的直接报错 } x=Q.data[Q.front];//将队头元素找出来 return true; }
这时候细心的看客可能就会想到,up,up,你不是说有不浪费空间的写法吗?怎么还不说啊,
个位看官莫想太多,书中故事是队列蹉跎,且听我细细道来
一定不能浪费空间的话
我们可以设置一个变量size,用于统计出队和入队的次数,
出队的话size-1,入队的话,size+1;看最后size的值就可以明白是队满还是对空了
请看代码
#define maxsize 10 //定义队列中元素的最大个数 typedef int ElemType; typedef struct { ElemType data[maxsize]; //存放队列元素 int front,rear;//队头指针和队尾指针 int size;//队列当前长度,遇到入队size++,遇到出队size--; } SqQueue; //判断条件 if(size==maxsize)//队满 if(size==0)//队空
或者说是设置一个变量tag,用于统计最近一次操作是入队,还是出队
tag=0,代表出队,tag=1,代表入队
#define maxsize 10 //定义队列中元素的最大个数 typedef int ElemType; typedef struct { ElemType data[maxsize]; //存放队列元素 int front,rear;//队头指针和队尾指针 int tag;//最近一次操作,遇到入队tag=1,遇到出队tag=0; } SqQueue; //判断条件 if(tag=1&&Q.front==Q.rear)//队满 if(tag=0&&Q.front==Q.rear)//队空