精华内容
下载资源
问答
  • 队列是一种只允许在一端进行插入操作,而一端进行删除操作的线性表,简称:FIFO 符合生活习惯:排第一个的优先出列,最后来的排队伍后面     2.循环队列------队列的顺序存储结构 所谓的入队操作,...

    1.定义

    队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表,简称:FIFO

    符合生活习惯:排在第一个的优先出列,最后来的排在队伍后面

     

     

    2.循环队列------队列的顺序存储结构

    所谓的入队操作,就是在队尾追加一个元素,而不需要移动任何元素,因此时间复杂度为O(1)。

    定义:把队列这种头尾相接的顺序存储结构称之为循环队列。

    front指针指向队头元素,rear指针指向队尾元素的下一个位置

    如何判断队列满了

    而作为对比,下面4-12-7不作为队列满的的判决办法了,

    而rear与front之间的关系存在于以下两种,所以得到通用的计算队列公式为:

     

    /*循环队列的顺序存储结构*/
    #define MAXMIZE 100
    typedef struct
    {
        int data[MAXMIZE];
        int front;//头指针
        int rear;//尾指针,若队列不空,则指向队尾元素的下一个位置
    }queue;
    
    //初始化队列
    int init(queue *q)
    {
        q->front=0;
        q->rear=0;
    }
    
    / *返回 Q 的个数,也就是队列的当前长度* /
    int quelength(queue q)
    {
        return (q.rear-q.front+MAXMIZE)%MAXMIZE;
    }
    
    //插入新元素
    /*若队列未满,则插入元素 e 为 Q 新的队尾元素*/
    int insect(queue *q,int e)
    {
        q->data[q->rear]=e;
        q->rear=(q->rear+1)%MAXSIZE//将rear指针向后移一个位置,若到最后则转到数组头部
    
        //判断队列为满的判断
        if((q->rear+1)%MAXMIZE==q->front)
            return 0;
        return 1;
    }
    
    //删除元素
    
    /*若队列不空,则删除q中队头元素。用 e返回其值*/
    int delete(queue *q, int e)
    {
        e=q->data[q->front];
        q->front=(q->front+1)%MAXMIZE;
    
        //队列为空的判断
        if(q->front==q->rear)
            return 0;
        return 1;
    }
    
    

    3.循环队列---队列的链式存储结构

    定义:称之为链队列,队列的链式存储结构,就是线性表的单链表,只不过它只能尾进头出

    队头指针指向链队列的头节点队尾指针指向终端节点

    空队列的时候,front和rear都指向头节点

    //链队列的结构
    
    //节点
    typedef struct node
    {
        int data;
        struct node *next;
    }node,*qnode;
    
    
    //链表结构
    typedef struct
    {
        qnodefront,rear;//队头,队尾指针
    }linkqueue;
    
    

    1)入队操作

    入队操作,就是在链表尾部插入节点

    /*插入元素e为Q的新的队尾元素 */
    
    //节点结构
    typedef struct node
    {
        int data;
        struct node *next;
    }node,*qnode;
    
    //队列的链表结构
    typedef struct 
    {
        qnode front ,rear;
    }linkqueue;
    
    
    int enterqueue(linkqueue *q,int e)
    {
        //开辟一个新节点
        qnode s=(qnode)malloc(sizeof(node))
        s->data=e;
        s->next=NULL;
        q->rear->next=s;//操作(1),将新节点s作为q队尾指针的后继
        s->rear=s;//操作(2),把s设置为队尾节点
        
        if(!s)
            exit(OVERFLOW);
    }

    2)出队操作

    /*若队列不空,删除Q的队头元素,用e返回其值, 并返回1,否则返回0 */
    
    typedef struct node
    {
        int data;
        struct node *next;
    }node,*pnode;
    
    
    typedef struct
    {
        pnode front,rear;
    }queue;
    
    int dequeue(queue *q,int *e)
    {
        pnode s;
        s=q->front->next;//操作(1),将预删除的队头节点暂存给s
        *e=q->data;
        q->front->next=s->next;//操作(2),将原头节点后继s->next赋值给头节点后继
        
        //操作(3),若队头是队尾,则删除后,将rear指向头节点
        if(q->rear==p)
            q->rear=q->front;
    
        //错误的情况
        if(q-front==q->rear)
            return 0;
        return 1;
    }

     

     

    总结:

    在确定队列长度最大值的情况下,建议使用循环队列,否则,若无法预估队列的长度时,则用链队列

     

    展开全文
  • 队列

    2015-03-30 01:15:50
    队列允许插入操作的一端称为队尾,允许进行删除操作的一端称为对头。队列的插入操作通常称为入队列,队列的删除操作通常称为出队列。 因为队列只允许一端插入,另一端删除,所以只有最早进入队列的元素才能最先...

    队列(简称为队)也是一种特殊的线性表,队列的数据元素以及数据元素之间的操作与线性表完全相同,差别是线性表允许在任意位置插入和删除,而队列只允许在一端进行插入操作而在另一端进行删除操作。队列允许插入操作的一端称为队尾,允许进行删除操作的一端称为对头。队列的插入操作通常称为入队列,队列的删除操作通常称为出队列。

    因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,因此队列也被称为先进先出表。比方说,大家在食堂排队买饭时,只有最早来排队的,即最先入队列的,才能最先买到饭,即最先出队列。

    展开全文
  • 允许插入的一端叫做队尾,允许删除一端叫做队头。总是删除队头元素,插入总是插入到队尾。这无疑是一种非常符合人类生活习惯的数据结构,所以很好学。 虽然符合人类生活习惯,但是程序设计也一样用的极其频繁...


    队列是一种FIFO(first in first out)线性表,它和栈一样,本质是线性表,但是不同的是他只允许在一端插入,另一端输出。

    允许插入的一端叫做队尾,允许删除的一端叫做队头。总是删除队头元素,插入总是插入到队尾。这无疑是一种非常符合人类生活习惯的数据结构,所以很好学。
    在这里插入图片描述
    虽然符合人类生活习惯,但是在程序设计中也一样用的极其频繁,下面是一些例子

    queue的应用举例(用了先进先出的排队思想的都算)

    • 电脑的鼠标操作
      在这里插入图片描述
      我有!原来如此!
    • 客服电话排队
      在这里插入图片描述
    • 键盘输入
      各种被敲击到的键会进入到一个队列
    • 记事本软件等的输出
      把字符流按照队列顺序显示在记事本中,比如你敲击的是god,显示的就也是god,而不是dog,哈哈哈,先进先出

    队列的抽象数据类型

    ADT Queue 
    Data//元素具有相同数据类型,相邻元素具有前驱后继关系。
    Operation
    	InitQueue(*Q);//建立一个空队列
    	DestroyQueue(*Q);//若Q存在,则销毁
    	ClearQueue(*Q);
    	QueueEmpty(*Q);
    	GetHead(*Q, *e);//把队头元素存入e
    	EnQueue(*Q, e);//把新元素插入到Q中
    	DeQueue(*Q, *e);//删除Q的队头元素,用e返回其值
    	QueueLength(*Q);
    endADT
    

    头尾相接的顺序存储结构:循环队列

    队列也是线性表,所以和栈一样,也有顺序存储结构和链式存储结构两种。

    顺序存储结构还是要用数组实现,但是并不是像栈那样简单地使用,而是要做成一个循环的队列。因为栈只在一端插入或删除,所以直接用数组,把数组为0那端作为栈底就妥了。

    但是如果简单地用数组直接实现队列,则数组索引较大的一端是队尾,这样便于插入新元素时直接插在数组下一个空位,则数组索引为0那边是队头,继续思考你就会发现问题了。队尾增加元素确实还比较方便的,时间复杂度是O(1)。但是队头元素的删除呢?如果我们假设只能把数据存在数组的前n个位置,则每次删除队头元素,就需要把所有后续元素往前移动一个位置,时间复杂度是O(n),如下图。
    在这里插入图片描述

    为了不移动后续所有元素,我们取消元素必须一直存在前N个位置的假设,而是用一个头指针front指向队头元素,和一个尾指针rear指向队尾元素的下一个内存位置。这样的话,删除队头元素只需要改变front指针,时间复杂度也变成O(1)了。插入到队尾只需要改一下rear指针,当然时间复杂度还是O(1)。

    如果rear指向队尾元素,则队列长度为1时,front和rear指向同一个位置,重合了,这样不便于处理,我们不希望front和rear指向同一个位置
    在这里插入图片描述

    你以为这样子的队列就丝滑完美了吗?不,还有问题。你想,不断删除队头结点会使得front指针不断后移,而rear指针不变。这时候用来实现队列的数组的前端有很多空位。如果这时候再往队列中不断添加新元素,知道队尾达到了数组的长度,这时候rear指针不断增大,直到指向数组后面那个内存位置,如上图右边,就不能再增加新元素了(这叫做假溢出),否则就会内存越界,可是明明数组的前端还有很多空位可用啊。

    为了解决假溢出,我们不要让rear指针指向数组后方内存,本身这样做也是很危险的,一般只有迫不得已才这样做,而让rear指针指向数组的头部,索引为0处,这样形成一个环,头尾相接,则可以利用数组前端空位。也永远不会出现指针指向不明的问题。

    所以,经过上面一番问题的出现和解决,我们设计出了顺序存储结构的队列:循环队列。我们也理解了为什么队列用顺序结构存储时必须是循环的,而栈不是。

    空队列和满队列中,front和rear重合

    让rear指针指向队尾元素的下一个位置,还是会有两种情况下,front会和rear相等:

    • 空队列:front == rear == someValue(我之前以为是NULL,后来发现并不是!因为使用数组实现,所以这里的front和rear指针实际是数组下标,是整数,所以不会是NULL)
    • 满队列: front == rear == someValue
      在这里插入图片描述
      由于空队列时俩指针也不是NULL,而是某个整数(数组下标),那怎么解决这个问题呢?有两个办法,都是用多用点空间的办法来换取两指针重合的情况判断。

    办法一:加一个标志变量flag

    设置一个标志变量flag,当标志为0且俩指针重合,则是空队列。这用了额外的一个字节,因为我们一般不会只分配一个比特,虽然表示这个标志位只需要一个比特。

    • 空队列:front == rear && flag == 0
    • 满队列:front == rear && flag == 1

    办法二:改变满队列的定义(用更多)

    满队列会遇到front和rear重合是因为我们把数组的空间全用完了。如果我们省出一个位置不用,即还剩一个位置为空时我们就认为队列已经满了,不能再插入新元素了,那么两个指针在满队列下也不会重合了。

    这样一来,就只有空队列会让两个指针重合了

    无需利用外部变量,直接利用队列本身就可以实现,所以这种办法用的更多。后面我们也只实现这种办法。

    如下图,左右都是新方案的满队列。用一个数组位置来换取指针重合的唯一性。

    在这里插入图片描述

    队列是否满的判断条件

    从上图可以看到,rear可能比front大,也可能比front小。满队列时,二者的差值可能是1,也可能是N-1(N是数组长度)。

    可以确定的是,如果rear比front大且队列为满,则一定是上图左边这种满队列情况,一大就大一整圈。front一定指向第一个位置(front = 0),而rear一定指向最后一个位置(rear = N - 1)
    r e a r = f r o n t + N − 1 = N − 1 rear = front+N - 1 = N - 1 rear=front+N1=N1

    如果rear比front小且队列为满,则一定是上图右边这样,rear比front小1
    r e a r = f r o n t − 1 rear = front - 1 rear=front1

    综合这两种情况可以发现,队列满一定有
    ( r e a r + 1 ) % N = f r o n t (rear + 1) \% N = front (rear+1)%N=front

    队列长度

    另外,不考虑队列是否为满,如果 r e a r > f r o n t rear>front rear>front,则队列长度为 r e a r − f r o n t rear - front rearfront,如上图左子图。
    如果 r e a r < f r o n t rear<front rear<front,则队列长度f分为两段,一段为 N − f r o n t N - front Nfront,另一端为 r e a r rear rear,如上图右子图。所以队列长度是
    N − f r o n t + r e a r N - front + rear Nfront+rear

    综合这两种情况,队列长度的通用公式则为:
    ( r e a r − f r o n t + N ) % N (rear - front + N) \% N (rearfront+N)%N

    总结来说,如果队列中数据元素的类型占用空间比较大,比如是某个类的对象,这个类有很多私有数据成员,则适合用第一种办法,如果队列中存储的数据的类型是int等类型,占用内存和1字节差不多的,对内存又不是特别严苛,就可以使用第二种办法。

    循环队列顺序存储结构相关代码

    队列结点的结构体

    Typedef struct
    {
    	ElemType data[SIZE];
    	int front;//无论数据类型是什么,指针类型都是整型
    	int rear;
    }SqQueue;
    

    初始化

    Status InitQueue(SqQueue * Q)
    {
    	Q->front = Q->rear = 0;
    	return OK;//使用数组,没有要求自己分配数组的内存,所以不需要malloc
    }
    

    求队列长度

    int QueueLength(SqQueue * Q)
    {
    	return (Q->rear - Q->front + SIZE) % SIZE;
    }
    

    入队列操作

    Status EnQueue(SqQueue * Q, ElemType e)
    {
    	if ((Q->rear + 1) % SIZE == Q->front)
    		return ERROR;//已满
    	Q->data[Q->rear] = e;
    	if (Q->rear == SIZE - 1)
    		Q->rear = 0;
    	else
    		++(Q->rear);
    	return OK;	
    }
    

    改变尾指针的那段代码可以简化为如下:

    Status EnQueue(SqQueue * Q, ElemType e)
    {
    	if ((Q->rear + 1) % SIZE == Q->front)
    		return ERROR;//已满
    	Q->data[Q->rear] = e;
    	Q->rear = (Q->rear + 1) % SIZE;
    	return OK;	
    }
    

    出队列操作

    Status DeQueue(SqQueue * Q, ElemType * e)
    {
    	if (Q->rear == Q->front)
    		return ERROR;//空
    	*e = Q->data[Q->front];
    	Q->front = (Q->front + 1) % SIZE;
    	return OK;
    }
    

    到此为止,我们学会了队列的顺序存储结构,用数组实现的循环队列,可以通过上面几个基本函数看到循环队列的时间复杂度还是很不错,入队,出队,返回队长度,初始化的时间复杂度全都是O(1)。

    但是他再好,也是顺序结构,即要底层要用数组实现,那么只要用数组就一定会有数组的缺点:需要提前设置数组长度,长度固定后不能改。这使得循环队列的灵活性差了一些,存的项最多就N-1个(有一个空着,为了使得满队列时两指针不重合,只有空队列才重合)。

    要让长度灵活,当然还是要选择链表,动态实时地分配,随用随分配内存,十分方便。

    队列的链式存储结构:链队列

    本质上就是线性表的单链表,只是他只能尾进头出罢了。

    front指针指向头结点(链表喜欢设置一个头结点以使得空队列和普通队列处理统一),rear指针指向最后一个结点(和循环队列不同)。
    在这里插入图片描述
    在这里插入图片描述

    队列的结点

    typedef struct QNode
    {
    	ElemType data;
    	struct QNode * next;
    }QNode, *QueuePtr;//这里写两个则struct不能是匿名的,且第一个和结构名一样.QueuePtr即QNode *
    

    队列的链表结构

    typedef struct
    {
    	QueuePtr front, rear;//只有队头队尾指针
    }LinkQueue;
    

    入队操作

    Status EnQueue(LinkQueue * Q, ElemType e)
    {
    	//不用判断是否已满,因为是链表
    	(QueuePtr) q = (QueuePtr)malloc(sizeof(ONode));\
    	if (!q)
    		return ERROR;//分配失败,或者写exit(OVERFLOW);
    	q->data = e;
    	q->next = NULL;
    	Q->rear->next = q;
    	Q->rear = q;
    	return OK;
    }
    

    出队操作

    Status DeQueue(LinkQueue * Q, ElemType * e)
    {
    	QNode * q;
    	if (Q->front == Q->rear)
    		return ERROR;//空
    	*e = Q->front->next->data;
    	q = Q->front->next;
    	Q->front = Q->front->next;
    	free(q);
    	return OK;
    }
    
    展开全文
  • 允许插入的一端称为队头,允许删除一端称为队尾.队头和队尾各用一个”指针”指示,称为队头指针和队尾指针.不含任何结点的队列称为”空队列”.队列的特点是结点在队列中的排队次序和出队次序按进队时间先后确定,即...
  • 队列——顺序队列

    2020-03-25 10:18:44
    队列 队列是一种特殊的线性表,特殊之处在于它只...在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列允许在一端插入,一端删除,所以只有最早进入队列的元素才能最先从队列...

    队列

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

    顺序队列

    建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置。

    • 队列的数组实现
      在这里插入图片描述
      每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。
      显然,这样的方式比较浪费内存空间,空间利用率并不高,而且还会出现溢出现象。所以我们采用循环队列:

      循环队列:以数组的形式模拟出环状的结构。 在这里插入图片描述
      在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。

    队列结构

    typedef struct Queue
    {
    	ElemType arr[MAX_SIZE];//int arr[10];
    	int front;//队头指针
    	int rear;//队尾指针
    }Queue,*pQueue;

    整体函数结构设计

    Queue.h整体结构

    typedef int ElemType;
    #define MAX_SIZE 9
    
    typedef struct Queue
    {
    	ElemType arr[MAX_SIZE];
    	int front;
    	int rear;
    }Queue,*pQueue;
    
    void init(pQueue pqu);
    
    int full(pQueue pqu);//1 full  |  0  not full
    int enqueue(pQueue pqu,ElemType val);//1  success  |   0   fail
    
    int empty(pQueue pqu);//1  empty  |  0  not empty
    int dequeue(pQueue pqu);//1  success  |  0  fail
    
    int front(pQueue pqu);//获取队头元素
    int back(pQueue pqu);//获取队尾元素
    

    函数的实现

    Queue.cpp代码实现

    #include<stdio.h>
    #include<iostrem>
    #include"Queue.h"
    
    void init(pQueue pqu)//初始化队列
    {
    	if(pqu != NULL)
    	{
    		pqu->fromt = pqu->rear = 0;
    	}
    }
    
    int full(pQueue pqu)//判满
    {
    	return ((pqu->rear+1)%MAX_SIZE == pqu->front) ? 1 : 0;	
    }
    int enqueue(pQueue pqu,ElemType val);//插入元素  入队
    {
    	if(full(pqu))
    	{
    		return 0;
    	}
    	pqu->arr[pqu->rear] = val;
    	pqu->rear = (pqu->rear+1)%MAX_SIZE;
    	return 1;
    }
    
    int empty(pQueue pqu)//判空
    {
    	return (pqu->rear == pqu->front) ? 1 : 0;
    }
    int dequeue(pQueue pqu)//出队  只删除元素,不移动数据
    {
    	if(empty(pqu))
    	{
    		return 0;
    	}
    	pqu->front = (pqu->front+1)%MAX_SIZE;
    	return 1;
    }
    
    int front(pQueue pqu)//获取队头元素
    {
    	if(empty(pqu))
    	{
    		throw std::exception("queue is empty!");//return -1;//牺牲一个数值位 -1
    	}
    	return pqu->arr[pqu->front];
    }
    
    int back(pQueue pqu)//获取队尾元素
    {
    	if(empty(pqu))
    	{
    		throw std::exception("queue is empty!")//return -1;//-1  队列为NULL  |  数据为 -1
    	}
    	return pqu->arr[(pqu->rear+MAX_SIZE-1)%MAX_SIZE];
    }
    

    程序测试

    main.cpp代码测试

    #include<stdio.h>
    #include"Queue.h"
    
    int main()
    {
     Queue que;
     init(&que);
     for (int i = 0; i < 8; i++)
     {
      enqueue(&que, i + 1);
     }
     int rtfront = front(&que);
     int rtback = back(&que);
     printf("front: %d\n", rtfront);
     printf("back: %d\n", rtback);
     dequeue(&que);
     enqueue(&que, -1);
     rtfront = front(&que);
     rtback = back(&que);
     printf("front: %d\n", rtfront);
     printf("back: %d\n", rtback);
     return 0;
    }
    
    展开全文
  • 队列与优先队列

    2020-03-21 20:08:10
    队列 是一种特殊的线性表,特殊之处在于它只允许在...在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列允许在一端插入,一端删除,所以只有最早进入队列的元素才能最先从队列...
  • 队列是一种先进先出的线性表,允许插入的一端称为队尾(rear),允许删除一端称为队头(front)。向队列中插入元素称为入队,从队列中删除元素称为出队。当队列中没有元素时称为空队列队列的操作...
  • 栈和队列在java的实现

    千次阅读 2013-10-29 08:26:27
    栈和队列在java的实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,797
精华内容 5,918
关键字:

在队列中允许删除的一端称为