队列的知识点总结_队列考点

目录

引言：

一、基本概念：

        1.定义：

        2.队列的基本操作:

         3.队列的分类：

                a.链表队列

                 b.循环队列

                c双端队列（知道即可）

 二、重点代码（重点讲解链表队列）：

三、易错及重要的知识点:

结尾：

---

引言：

中午在食堂打饭，真是一个令人头疼的事情，去食堂的路上也总是步伐匆匆，为什么啊，这还用说，迟一点去，你就会知道什么叫做人山人海了，在食堂排队的时候，相比较学生来说，打饭阿姨毕竟是少数，在每个窗口都有人的时候，不免我们就得等待，直到前面的一个学生打完饭离开，后面排队的人才可以继续向前走，直到轮到自己，别提多费劲了，但是秩序和规则却是我们每个人都应该遵守的，也只能抱怨自己来的迟了

一、基本概念：

        1.定义：

             一个“先进先出”的数据结构。队列是一种只允许在一段进行删除操作，在另一端进行插入操作的线性表。

例子补充：用电脑的时候，有时候机器会处于疑似死机的状态， 鼠标点什么似乎都没有用，双击任何快捷方式都不动，就当你失去耐心，打算reset的时候，突然它就像酒醒了一样，把你刚才点击的所有操作全部按照顺序执行了一遍，这其实是因为操作系统中的多个程序隐需要通过一个通道输出，而按照先后次序排队等待造成的 ——《大话数据结构》

        2.队列的基本操作:

        Enqueue（入队）：是在队尾进行插入操作。

        Dequeue（出队）：是在队首进行删除操作。

         3.队列的分类：

                a.链表队列

链式队列是队列的实现方式之一。链式队列内部使用带头结点的单向链表来实现。它的好处的是灵活，队列容量理论上是不受限制的。

我们使用链表的首结点来表示队列的队头，链表的尾结点代表队尾。

当队列为空时，队尾元素指针指向头结点headNode。

                 b.循环队列

        使用顺序结构（数组）来实现队列，将队头存放在数组开头的位置， 但是我们会遇到一个问题：如果执行出队后，array[0]就空出来了，但是又不能被利用，因为队列只能在队尾追加元素，这样就会造成“假满”的情况。

            我们可以将一个固定长度的数组在逻辑上臆造成一个环形。这样，队头元素存放的位置不是固定的，他会随着 出队 动态改变，而队尾元素也会随着入队 动态改变。可以将front和rear变量看做是2个小孩子围着一颗树你追我赶一样，只要他们在追赶过程中没有相遇，队列就不是满的。 这样就会让每个数组空间都能得到利用。

                c双端队列（知道即可）

双端队列是一种两端都可以 删除元素和追加元素的线性结构。双端队列比普通的队列更加灵活。

如果我们在使用时，自己限制自己的操作行为，则可以将双端队列当成其它的数据结构来使用。

如果我们对一个双端队列只调用他的removeFirst() 和 addLast() ，那么就是当做一个队列使用。

如果我们对一个双端队列只调用他的addLast() 和 removeLast() 【或者只调用addFirst和removeFirst()】，那么就是当做一个栈使用。

注：双端队列可以用双向链表实现。

 二、重点代码（重点讲解链表队列）：

注：若对循环队列不懂可以看我之前发的循环队列的插入与删除

#include<stdio.h>
#include<stdlib.h>
 
//链表队列的结构体(其实就是一个链表)
typedef struct Queue 
{
	int data;
	struct Queue* next;	 
}Queue ;
 
Queue * InitQueue()
{
	Queue  *Q=(Queue *)malloc(sizeof(Queue));
	Q->data=0;	//队尾元素为0
	Q->next=NULL;
	return Q;
}
//进队
void enQueue(Queue  *Q,int data)
{
	Queue  *q=Q;	//创建一个结点，并指向Q的头结点
	Queue  *node=(Queue  *)malloc(sizeof(Queue ));	//创建一个新的结点
	node->data=data;
	for(int i=0;i<Q->data;i++)	//遍历队列，到尾结点
	{
		q=q->next;	
	}
	node->next=q->next;    
	q->next=node;
    //上面两步与链表的插入操作原理相同
	Q->data++;
}
//判断是否为空
int isEmpty(Queue  *Q)
{
	if(Q->data==0||Q->next==NULL)	//队列为空
	{
		return 0;
	}
	else 
	{
		return 1;
	}
	
}
//出队
int deQueue(Queue  *Q)
{
	if(isEmpty(Q))
	{
		Queue  *p=Q->next;
		int data=p->data;
		Q->next=p->next;
		free(p);
        //以上步骤与链表的删除操作原理相同
		return data;
	}
	else
	{
		printf("队列为空\n");
		return -1;	
	}
}
//答应队列
void printQueue(Queue  *Q)
{
	Queue  *p=Q->next;
	for(int i=0;p;i++)
	{
		printf("%d->",p->data);
		p=p->next;
	}
	printf("NULL");
}
//主函数
int main()
{
	Queue  *Q=InitQueue();
	enQueue(Q,1);
	enQueue(Q,2);
	enQueue(Q,4);
	enQueue(Q,6);
	printQueue(Q);
	int num=deQueue(Q);
	printf("\n删除元素为：%d\n",num);
	printQueue(Q);
	return 0;
}

注：给读者的一点建议：大家可以学习一下我的代码的格式。因为如果一个代码敲出来不美观，乱七八糟的话，会导致给别人看代码不太方便理解以及自己去Debug的时候，不容易发现自己的bug出现在哪。

三、易错及重要的知识点:

注：由于链表队列比较简单，所以并没有比较重要的知识点，只需读者掌握基本操作即可。所以我主要写一下循环链表的。

  在循环队列中，画图易得知当循环队列为空时，队首指针(front)和队尾指针(rear)是指向同一个结点的。但又仔细的想想的，当循环队列满时，神奇的发现队首和队尾指针也是指向同一个结点的。所以，就引发了我们该如何判断一个循环队列是空还是满呢？

  针对这个问题，我给出三个解决方案：

• A：设置一个标志变量flag，当front = rear的时，且flag = 0的时候为空，若flag = 1 的时候为队列满
• B：设计一个计数器count统计当前队列中的元素数量，count == 0 队列空，count == maxsSize 队列满
• C：保留一个存储空间用于区分是否队列已满，也就是说，当一个还空闲一个单元时候，我们就认为表已经满了

  前两个相信读者的水平是可以自己编码实现的。所以，这里我重点讲解一下C方案：

        根据C方案，我们可以总结出以下的等式：

• 队列为满的条件：(rear+1) % MaxSize == front
• 队列为空的条件：front == rear
• 队列中元素的个数：(rear- front + maxSize) % MaxSize
• 入队：rear = (rear + 1) % maxSize
• 出队：front = (front + 1) % maxSize

结尾：

        如果文章中有什么不足，或者错误的地方，欢迎大家留言分享想法，感谢朋友们的支持！