精华内容
下载资源
问答
  • 循环队列的存储结构定义
    千次阅读
    2018-07-01 23:24:31
    五、队列的定义
    定义:队列(queue):队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
    队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入操作的一端称为队尾,允许删除操作的一端称为队头。
    队列与现实生活中的排队机制很像,排在队头的出队,而想入队则只能从队尾开始。
    ===============================================================================
    队列:
    顺序存储结构:(循环队列)

    #define N 10
    typedef int data_t;
    typedef struct
    {
    data_t data[N]; //数据存储
    int length; //不能用,注意想想方式
    }Node;

    ===============================================================================
    六、循环队列
    线性表有顺序存储和链式存储两种结构,队列作为特殊的线性表,自然也有顺序队列和链式队列两种形式。
    但是,队列的顺序存储却有很大的缺陷。如果我们要建立元素个数为n的队列,则需要建立一个数组长度不小于n的数组,数组下标为0的为队头,当最大下标的为队尾。若有元素要入队,则只需将其存储在第n+1个位置即可。
    而若想出队,则删除了下标为0的元素后,所有在其后的元素都需要向前移动一格,即保持下标为0的元素为队头。但这样做显然浪费了大量时间。
    解决该问题的方法就是不再限制下标为0的元素为队头,每次出队后,队头自动变成当前数组下标最小的元素即可。这样就无需所有元素向前移动。
    但是,若如此做,则会造成大量的已出队的元素的存储空间浪费。而且,若此时入队元素已经大于n,则我们需要更大的存储空间才行,但队头位置有大量空间未利用,空间浪费严重。
    解决以上问题的方法就是如果后面满了,则我们就从头开始,也就是将队列做成头尾相接的循环。我们把这种头尾相接的顺序存储结构的队列称为循环队列。
    这样,我们就需要两个指示其队头(front)和队尾(rear)的下标变量。
    typedef int data_t;
    typedef struct
    {
    data_t data[MAXSIZE];
    int front; 头位置下标
    int rear; 尾位置下标
    }SqQueue;

    循环队列的操作:
    1、创建空的循环队列(CreateSqQueue)
    2、判断是否为空队列(SqQueueEmpty)
    3、判断是否为满队列(SqQueueFull)
    4、新数据元素入队(EnQueue)
    5、数据元素出去(OutQueue)
    6、求队长(SqQueueLenght)
    7、遍历循环队列(VisitSqQueue)

    当front==rear时,此时队头和队尾重合,则该队列为空队列;当(rear+1)%QueueSize==front时,此时队尾的下个位置就是队头,则该队列为满队列。注意rear的位置不是队尾元素的位置,而是队尾元素的下一个位置,即当队列满时,队列中还有一个空闲存储空间,但我们规定该状态下就是满队列。
    那么,定义好队列的的队头和队尾位置,我们来考虑怎样计算队列长度。
    当rear>front时,表示队尾在队头右边,此时队列长度为rear-front;当rear<front时,表示队尾在队友左边,此时计算队列长度应分成两部分,即rear一部分,QueueSize-front一部分,总体长度为rear-front+QueueSize。
    通用计算队列长度的公式是
    length=(rear-front+QueueSize)%QueueSize
    1、判断队是否为空EmptyQueue
    //代码见附录
    2、判断队是否为满FullQueue
    //代码见附录
    3、入队操作EnQueue
    //代码见附录
    4、出队操作DeQueue
    //代码见附录
    从循环队列的特性我们可以看出,循环队列虽然操作较为简单,但是由于队列定长,因此会出现数据溢出问题。这时我们需要考虑使用队列的链式存储结构。
    ===============================================================================
    七、队列的链式存储结构及实现
    队列的链式存储结构本质上是从单链表演化而来的。将单链表改造成链式队列,如果将头结点做为队头,最后一个节点做为队尾,则该队列的出队操作方便,而入队操作较慢;反之,如果将头结点做为队尾,最后一个节点做为队头,则该队列的入队操作方便,而出队操作较慢。
    那么,能否将单链表稍加改进,使得该链式队列的入队操作和出队操作一样方便呢?
    答案是可以的,只需要改进头结点。将“头结点存储一个next指针”改为“头结点存储两个指针front和rear”,front指针指向队头,rear指针指向队尾。这样我们进行出队/入队操作时,只需要访问这两个指针就能快速地找到队头/队尾。
    1、队列的链式存储结构定义
    将单链表的头结点稍加改造
    typedef int data_t;
    typedef struct node_t//定义单链表
    {
    data_t data;
    struct node_t *next;
    } linknode_t, *linklist_t;
    typedef struct//定义链式队列
    {
    linklist_t front, rear;
    } linkqueue_t;

    链式队列的操作:
    申请的头指针为lq,lq->front == lq->rear
    1、创建空链式队列(CreateLinkQueue)
    2、判断是否为空(LinkQueueEmpty) rear == front != NULL
    3、清空链式队列(ClearLinkQueue)
    4、求链式队列的长度(LinkQueueLength)
    5、新数据元素入队(EnLinkQueue) rear指向最后元素
    6、数据元素出队(DeLinkQueue)
    7、遍历整个链式队列数据元素(PrintLinkQueue)

    2、判定链式队列是否为空
    由于单链表的属性,链式队列几乎不会出现“队列已满”的情况,因此不考虑判定链式队列是否已满的操作。
    判定链式队列是否为空,只需要判定队列的front指针是否为空即可。
    //代码见附录
    3、队列的链式存储结构——入队操作
    入队操作其实就是在链表尾部插入节点。新来的数据节点附在当前rear节点之后,并将rear节点指向该节点即可。
    //代码见附录
    4、队列的链式存储结构——出队操作
    出队操作就是将链表的头结点的后继节点出队,并将其之后的节点设置为头结点的后继节点。若链表除头结点外仅剩一个元素,则需将rear指向头结点。
    //代码见附录

    对于循环队列和链式队列的比较,二者从时间复杂度上来说都是O(1),不过链式队列需要花费额外的申请节点的时间,而且链式队列删除节点也需要一些时间。从空间上来说,循环队列有固定长度,就意味着循环队列有其存储上限,因此也就存在元素溢出以及空间浪费等问题,而链式队列则不存在这些问题。
    总体来说,若可以大致确定元素个数的情况下,推荐使用循环队列;若无法事先预知元素个数,则应使用链式队列。
    ===============================================================================
    ======================================================================
    更多相关内容
  • 循环队列定义及主要操作3.主函数(测试函数)三.运行结果 一、队列 为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列...


    一、队列

    为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。

    循环队列和普通队列有所不同,需要注意的是队空队满
    为了区分队空还是队满的情况,有多种处理方式(这里选的是第一种):

    方式1: 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,即约定以"队头指针在队尾指针的下一位置作为队满的标志"
    方式2: 增设表示队列元素个数的数据成员size,此时,队空和队满时都有front==rear。
    方式3: 增设tag数据成员以区分队满还是队空

    二、代码

    1.头文件与宏定义

    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 50
    #define QueueElemType char
    
    

    2.循环队列的定义及主要操作

    typedef struct {
    	QueueElemType elem[MAXSIZE];
    	int front;  //头
    	int rear;	//尾
    }SeqQueue;
    
    // 初始化
    void InitQueue(SeqQueue* Q) {
    	Q->front = Q->rear = 0;
    }
    
    // 判断队列是否为空
    int IsEmpty(SeqQueue Q) {
    	if (Q.front == Q.rear) {
    		return TRUE;
    	}
    	else {
    		return FALSE;
    	}
    }
    
    // 入队
    int EnterQueue(SeqQueue* Q, QueueElemType x) {
    	if ((Q->rear + 1) % MAXSIZE == Q->front) {
    		//队列已满
    		return FALSE;
    	}
    	else {
    		Q->elem[Q->rear] = x;
    		Q->rear = (Q->rear + 1) % MAXSIZE;	//重新设置队尾
    		return TRUE;
    	}
    }
    
    // 出队
    int DeleteQueue(SeqQueue* Q, QueueElemType* x) {
    	if (Q->front == Q->rear) {
    		//队列为空
    		return FALSE;
    	}
    	else {
    		*x = Q->elem[Q->front];
    		Q->front = (Q->front + 1) % MAXSIZE;
    		return TRUE;
    	}
    }
    
    // 求队的长度
    int LenQueue(SeqQueue Q) {
    	return ((Q.rear + MAXSIZE - Q.front) % MAXSIZE);
    }
    
    // 输出队中元素
    int PrintQueue(SeqQueue Q) {
    	if (Q.front == Q.rear) {
    		//队列为空
    		return FALSE;
    	}
    	while(TRUE) {
    		if (Q.rear == Q.front) {
    			return TRUE;
    		}
    		else {
    			printf("%c ", Q.elem[Q.front++]);
    		}
    	}
    }
    

    3.主函数(测试函数)

    int main() {
    	SeqQueue Q;
    	int i, n, flag, len;
    	QueueElemType x;
    	//初始化循环队列
    	InitQueue(&Q);
    
    	//判断队列是否为空
    	printf("当前队列是否为空: ");
    	flag = IsEmpty(Q);
    	if (flag) {
    		printf(" 当前队列为空。\n");
    	}
    	else {
    		printf(" 当前队列不为空。\n");
    	}
    
    	//入队
    	printf("请输入入队数量:\n");
    	scanf("%d", &n);
    	getchar();
    	printf("请输入元素:\n");
    	for (i = 0; i < n; i++) {
    		x = getchar();
    		getchar();	
    		flag = EnterQueue(&Q, x);
    		if (!flag) {
    			printf("当前队列已满!!\n");
    			break;
    		}
    	}
    
    	//出队
    	printf("出对一个元素并输出\n");
    	flag = DeleteQueue(&Q, &x);
    	if (flag) {
    		printf("%c \n", x);
    	}
    	else {
    		printf("队列为空!!!\n");
    	}
    
    	//当前队列元素的个数
    	len = LenQueue(Q);
    	printf("当前队列元素的个数:%d\n", len);
    
    	//入队
    	printf("请输入入队数量:\n");
    	scanf("%d", &n);
    	getchar();
    	printf("请输入元素:\n");
    	for (i = 0; i < n; i++) {
    		x = getchar();
    		getchar();
    		flag = EnterQueue(&Q, x);
    		if (!flag) {
    			printf("当前队列已满!!\n");
    			break;
    		}
    	}
    
    	//当前队列元素的个数
    	len = LenQueue(Q);
    	printf("当前队列元素的个数:%d\n", len);
    
    	//所有元素出队
    	printf("所有元素出队:\n");
    	while (TRUE){
    		flag = DeleteQueue(&Q, &x);
    		if (!flag) {
    			break;
    		}
    		else {
    			printf("%c ", x);
    		}
    	}
    	printf("\n");
    
    	//判断队列是否为空
    	printf("当前队列是否为空: ");
    	flag = IsEmpty(Q);
    	if (flag) {
    		printf(" 当前队列为空。\n");
    	}
    	else {
    		printf(" 当前队列不为空。\n");
    	}
    
    	return 0;
    }
    

    三.运行结果

    在这里插入图片描述

    展开全文
  • 队列的顺序存储结构循环队列

    千次阅读 2020-04-24 15:46:24
    一、队列的定义 队列( queue )是只允许在一端进行插入...二、循环队列的引出 为了避免当队中只剩一个元素的时候,队头队尾重合使处理变得麻烦。所以我们引入两个指针,front指针指向队头元素,rear指针指向队尾元素...

    一、队列的定义
    队列( queue )是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
    队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。如图所示:
    在这里插入图片描述
    二、循环队列的引出
    为了避免当队中只剩一个元素的时候,队头队尾重合使处理变得麻烦。所以我们引入两个指针,front指针指向队头元素,rear指针指向队尾元素。这样当front=rear时,队列中不是只剩一个元素,而是它是一个空队列。而且这样也大大方便了我们删除队头元素。这样就当我们删除队头元素时就只需要移动front指针,这样可以大大降低算法的时间复杂度。
    但是当删除元素的时候,front不断后移,前面的位置不断空出来。插入元素时rear指针 b不断后移。对于一个有限的队列来说,在不断得插入元素时rear最终会指向一个无效位置。具体情况如下图所示:
    删除元素时:
    在这里插入图片描述
    插入元素时:
    在这里插入图片描述
    用循环队列可以巧妙得解决这个问题。
    三、循环队列
    1、循环队列的定义
    **我们把队列的这种头尾相接的顺序存储结构称为循环队列。**如下图所示:
    循环队列满时:
    在这里插入图片描述
    循环队列空时:
    在这里插入图片描述
    判断循环队列空的条件是:

    front == rear;

    判断循环队列满的条件是:

    (rear+1)%6==front

    为了区别判空和判满的状态,我们总在插入元素时牺牲一个空间来区别这两种状态,这也是为啥判满的时候是(rear+1)%6==front
    2、循环队列的简单实现
    (1)循环队列的整体结构的设计

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

    2、初始化(init)
    初始化的时候我们只需要将我们的头指针和尾指针置成0即可。

    void init(pQueue pqu)
    {
    	if(pqu != NULL)
    	{
    	pqu->front = pqu->rear = 0;
    	}
    } 
    

    3、入队操作(enqueue)
    在进行入队操作之前我们首先应该对队列进行判满的操作。如果队列是满的,我们就插入不了元素。如果队列不满我们就可以进行我们的入队操作。
    判满

    int full(pQueue pqu)
    {
    	return (pqu->rear + 1)%MAX_SIZE == front ? 1 : 0;
    }
    

    插入元素
    插入元素时,我们只需要将这个队列中的rear指针的下标置成我们要插入的元素即可。

    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;
    }
    

    4、出队操作(dequeue)
    在进行出队操作时,我们首先要判断的是队列是否为空。若队列中的元素为空,则就无法进行出队的操作。
    判空

    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;
    }
    

    5、获取队头元素(front)

    int front(pQueue pqu)
    {
    	if(empty(pqu))
    	{
    	return -1;//牺牲一个数值位
    	}
    	return pqu->arr[pqu->front];
    }
    

    6、获取队尾元素(back)

    int back(pQueue pqu)
    {
    	if(empty(pqu))
    	{
    	return -1;//队列为NULL
    	}
    	return pqu->arr[(pqu->rear + MAX_SIZE - 1)%MAX_SIZE];
    }
    
    展开全文
  • 1.1 队列定义   队列(Queue) 简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队。删除元素称为出队或离队。这和我们日常生活中的排队是...

    一、队列的基本概念

    1.1 队列的定义

      队列(Queue) 简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队进队。删除元素称为出队离队。这和我们日常生活中的排队是一致的,最早排队的也是最早离队的,其操
    作的特性是先进先出(First In First Out, FIFO),如:
    在这里插入图片描述
    队头(Front): 允许删除的一-端,又称队首。
    队尾(Rear)。: 允许插入的一-端。
    空队列: 不含任何元素的空表。

    1.2 队列常见的基本操作

    InitQueue(&Q): 初始化队列,构造-一个空队列 Q.
    QueueEmpty(Q): 判队列空,若队列Q为空返回true,否则返回false.
    EnQueue(&Q,x): 入队,若队列Q未满,将x加入,使之成为新的队尾。
    DeQueue (&Q, &x): 出队,若队列e非空,删除队头元素,并用x返回。
    GetHead(Q,&x): 读队头元素,若队列Q非空,则将队头元素赋值给x。

    注意: 栈和队列是操作受限的线性表,因此不是任何对线性表的操作都可以作为栈 和队列的操作。比如,不可以随便读取栈或队列中间的某个数据。

    二、队列的顺序存储结构

      队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针:队头指针front 指向队头元素,队尾指针rear 指向队尾元素的下一个位置 (也可以让rear指向队尾元素、front 指向队头元素) 。
      顺序结构可描述为:

    typedef struct SqQueue
    {
    	ElemType data[MaxSize];	//存放队列元素
    	int front;	//队头指针
    	int rear;	//队尾指针
    }SqQueue;
    

      初始状态(队空条件):Q.front==Q.rear==0
      进队操作:队不满时,先送值到队尾元素,再将队尾指针加1。
      出队操作:队不空时,先取队头元素值,再将队头指针加1。

    队列的操作:
    在这里插入图片描述

    顺序存储结构存在的问题:

    在这里插入图片描述
      出队a1、a2,则front指针指向下标为2的位置,rear 不变,如左图所示,再入队a5,此时front 指针不变,rear 指针移动到数组之外。嗯?数组之外,那么就会产生数组越界的错误,可实际上,我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做 “假溢出”。如右图所示。

    三、循环队列

      为了解决假溢出的问题,引入了循环队列,使其头尾相连。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

    3.1 实现思路

      当队首指针Q. front=MaxSize-1后,.再前进一个位置就自动到0,这可以利用 除法取余运算(%) 来实现。.
      初始时: Q.front=Q.rear=0
      队首指针进 1: Q.front= (Q.front+1) % MaxSize
      队尾指针进 1: Q.rear= (Q.rear+1) % MaxSize
      队列长度: (Q. rear +MaxSize-Q. front) % MaxSize
      出队入队时:指针都按顺时针方向进1 (如图所示)

    3.2 循环队列队空和队满的判断条件

      循环队列队空和队满的判断条件是什么呢?显然,队空的条件是Q.front==Q.rear
    若入队元素的速度快于出队元素的速度,则队尾指针很快就会赶上队首指针,如图(d1)所示,此时可以看出队满时也有Q.front==Q.rear
      为了区分队空还是队满的情况,有三种处理方式:

    1. 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的做法,
      约定以 “队头指针在队尾指针的下一位置作为队满的标志”,如图(d2)所示。
      队满条件: (Q.rear+1) % MaxSize==Q.front
      队空条件仍为: Q.front==Q.rear。
      队列中元素的个数: (Q. rear-Q. front+MaxSize)各MaxSize.
    2. 类型中增设表示元素个数的数据成员。这样,队空的条件为Q.size==0;队满的条件为
      Q.size==MaxSize。这两种情况都有Q. front==Q. rear.
    3. 类型中设置一个标志变量 flag,以区分是队满还是队空。flag 等于 0 时,若因删除导致
      Q.frontQ.rear ,则为队空; flag 等于 1 时,若因插入导致Q. frontQ. rear,则为队满。(常用
      在这里插入图片描述

    3.3 循环队列的操作

    #include<stdio.h>
    #include<malloc.h>
    
    
    #define MaxSize 20
    typedef int ElemType;
    
    typedef struct SqQueue
    {
    	ElemType *data;	//存放队列元素
    	int front;	//队头指针
    	int rear;	//队尾指针
    }SqQueue;
    
    void InitQueue(SqQueue *Q);	//初始化队列
    bool isEmpty(SqQueue Q);	//判断队列是否为空
    bool isFull(SqQueue Q);	//判断队列是否已满
    bool EnQueue(SqQueue *Q,ElemType e);	//入队
    bool DeQueue(SqQueue *Q,ElemType *e);	//出队
    void PrintQueue(SqQueue pQ);
    
    int main()
    {
    	SqQueue Q;
    	ElemType e;
    	InitQueue(&Q);
    
    	EnQueue(&Q,1);
    	EnQueue(&Q,2);
    	EnQueue(&Q,3);
    	EnQueue(&Q,4);
    	EnQueue(&Q,5);
    	EnQueue(&Q,6);
    	EnQueue(&Q,7);
    	
    	PrintQueue(Q);
    
    	if(DeQueue(&Q,&e))
    		printf("出队成功,出队元素为:%d\n",e);
    	else
    		printf("出队失败\n");
    
    	PrintQueue(Q);
    
    	return 0;
    }
    
    
    void InitQueue(SqQueue *Q)
    {
    	Q->data = (ElemType *)malloc(sizeof(ElemType)* MaxSize);
    	Q->front = Q->rear = 0;
    }
    
    
    bool isEmpty(SqQueue Q)
    {
    	if(Q.rear == Q.front)
    		return true;
    	else
    		return false;
    }
    
    bool isFull(SqQueue Q)
    {
    	if((Q.rear + 1) % MaxSize == Q.front)
    		return true;
    	else
    		return false;
    }
    
    bool EnQueue(SqQueue *Q,ElemType e)
    {
    	if((Q->rear + 1) % MaxSize == Q->front)
    		return false;	//队满报错
    	Q->data[Q->rear] = e;
    	Q->rear = (Q->rear +1) % MaxSize;	//队尾指针加1取模
    	return true;
    }
    
    bool DeQueue(SqQueue *Q,ElemType *e)
    {
    	if(Q->rear == Q->front)
    		return false;	//队空报错
    	*e = Q->data[Q->front];
    	Q->front = (Q->front +1) % MaxSize;	//队头指针加1取模
    	return true;
    }
    
    void PrintQueue(SqQueue pQ)
    {
    	int i = pQ.front;
    
    	while(i != pQ.rear)
    	{
    		printf("%d ",pQ.data[i]);
    		i = (i+1) % MaxSize;
    	}
    	printf("\n");
    }
    

    四、队列的链式存储结构

    4.1 队列链式存储

      队列的链式表示称为链队列,它实际上是一个同时带有队头指针和队尾指针的单链表。头指
    针指向队头结点,尾指针指向队尾结点,即单链表的最后一个结点
      队列的链式存储如图:
    在这里插入图片描述
    可描述为:

    typedef struct QNode	/* 结点结构 */
    {
       ElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    {
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;
    

      当Q. front==NULLQ.rear==NULL时,链式队列为空。
      出队时,首先判断队是否为空,若不空,则取出队头元素,将其从链表中摘除,并让Q. front
    指向下一个结点(若该结点为最后一个结点,则置Q. front和Q. rear都为NULL)。入队时,
    建立一个新结点,将新结点插入到链表的尾部,并改让Q. rear指向这个新插入的结点(若原队列为空队,则令Q. front也指向该结点)。
      不带头结点的链式队列在操作上往往比较麻烦,因此通常将链式队列设计成一个带头结点的单链表,这样插入和删除操作就统一了。
    在这里插入图片描述

    使用场景: 用单链表表示的链式队列特别适合于数据元素变动比较大的情形,而且不存在队列满且产生溢出的问题。另外,假如程序中要使用多个队列,与多个栈的情形一样,最好使用链式
    队列,这样就不会出现存储分配不合理和“溢出”的问题。

    4.2 链式队列的基本操作

    4.2.1 初始化

    void InitQueue(LinkQueue *Q)
    { 
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    	Q->front->next=NULL;
    }
    

    4.2.2 判队空

    bool IsEmpty(LinkQueue Q)
    { 
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }
    

    4.2.3 入队

      入队操作时,其实就是在链表尾部插入结点,如图所示:
    在这里插入图片描述
    其代码如下:

    bool EnQueue(LinkQueue *Q,ElemType e)
    { 
    	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    	s->data=e;
    	s->next=NULL;
    	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    	Q->rear=s;		/* 把当前的s设置为队尾结点,rear指向s,见图中② */
    	return true;
    }
    

    4.2.4 出队

      出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear 指向头结点,如图所示:
    在这里插入图片描述

    其代码如下:

    bool DeQueue(LinkQueue *Q,ElemType *e)
    {
    	QueuePtr p;
    	if(Q->front==Q->rear)
    		return false;
    	p=Q->front->next;		/* 将欲删除的队头结点暂存给p,见图中① */
    	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继,见图中② */
    	if(Q->rear==p)		/* 若队头就是队尾,则删除后将rear指向头结点,见图中③ */
    		Q->rear=Q->front;
    	free(p);
    	return true;
    }
    

    4.3 队列链式结构完整代码

    #include<stdio.h>
    #include<malloc.h>
    
    #define MaxSize 10;
    typedef int ElemType;
    
    typedef struct QNode	/* 结点结构 */
    {
       ElemType data;
       struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct			/* 队列的链表结构 */
    {
       QueuePtr front,rear; /* 队头、队尾指针 */
    }LinkQueue;
    
    
    /* 构造一个空队列Q */
    void InitQueue(LinkQueue *Q)
    { 
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    	Q->front->next=NULL;
    }
    
    bool IsEmpty(LinkQueue Q)
    { 
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }
    
    /* 插入元素e为Q的新的队尾元素 */
    bool EnQueue(LinkQueue *Q,ElemType e)
    { 
    	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    	s->data=e;
    	s->next=NULL;
    	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    	Q->rear=s;		/* 把当前的s设置为队尾结点,rear指向s,见图中② */
    	return true;
    }
    
    
    
    /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
    bool DeQueue(LinkQueue *Q,ElemType *e)
    {
    	QueuePtr p;
    	if(Q->front==Q->rear)
    		return false;
    	p=Q->front->next;		/* 将欲删除的队头结点暂存给p,见图中① */
    	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
    	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继,见图中② */
    	if(Q->rear==p)		/* 若队头就是队尾,则删除后将rear指向头结点,见图中③ */
    		Q->rear=Q->front;
    	free(p);
    	return true;
    }
    
    
    void PrintQueue(LinkQueue Q)
    {
    	QueuePtr p;
    	p=Q.front->next;
    	while(p)
    	{
    		 printf("%d ",p->data);
    		 p=p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	LinkQueue Q;
    	ElemType e;
    
    	InitQueue(&Q);
    
    	EnQueue(&Q,1);
    	EnQueue(&Q,2);
    	EnQueue(&Q,3);
    	EnQueue(&Q,4);
    	EnQueue(&Q,5);
    	EnQueue(&Q,6);
    	EnQueue(&Q,7);
    	
    	PrintQueue(Q);
    
    	if(DeQueue(&Q,&e))
    		printf("出队成功,出队元素为:%d\n",e);
    	else
    		printf("出队失败\n");
    
    	PrintQueue(Q);
    
    
    	return 0;
    }
    
    展开全文
  • 循环队列的顺序存储结构Java

    千次阅读 2019-12-19 16:33:54
    循环队列的顺序存储结构 在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面...
  • 循环队列 (顺序存储)

    千次阅读 2021-10-21 12:23:13
    队列是一种操作受限的线性表。队列只能在表的一端进行插入操作,在另一端进行删除操作。其中,允许插入的一端叫...循环队列是对队列的一种改进,主要是为了解决队尾溢出而实际上数组仍有空余空间这种“假溢出” 问题
  • 数据结构栈和队列

    2018-01-02 21:43:05
    2、理解队列的逻辑结构定义及特点、掌握循环队列存储结构及其描述方法、掌握循环队列的基本运算。 二、实验内容: 1、建立顺序栈,并实现顺序栈的基本操作; 2、建立链栈,并实现链栈的基本操作; 3、建立循环队列...
  • 顺序存储结构定义: typedef struct{ QElemType *base; int Front,Rear; }CQueue;   循环队列的基本操作: 1、初始化一个队列 2、清空一个队列 3、判断一个队列是否为空 4、求队列的长度 5、入队列操作 ...
  • 数据结构循环队列

    千次阅读 2022-04-12 18:48:24
    循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。 环形队列可以使用数组实现,也可以使用循环链表实现。 重点:循环队列,无论使用数组实现还是链表实现,都要多开一个空间,也...
  • 一、队列的存储结构 1、队列的物理存储可以用顺序存储结构,也可用链式存储结构。相应队列的存储方式也分为两种,即顺序队列和链式队列。...二、循环队列的基本操作语句 1、队列的初始:front=rear=0; 2、
  • 【数据结构】第三章(2)队列、队列的存储结构——顺序队列、循环队列(顺序循环队列、链循环队列
  • 什么是队列 队列是一种操作受限的线性表,队列只...其中,循环队列必须损失一个存储空间(如上图中下标为0的空间),如果控件0也存入元素,则队满和队空的条件都是q.front==q.rear,此时便无法区分队空和队满了。 ...
  • 数据结构循环队列C语言实现(详细)

    万次阅读 多人点赞 2020-05-25 23:59:25
    队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。 这一篇讲的是循环队列,链式队列在另外一篇文章中 循环数组 循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢? ...
  • 文章目录循环队列的顺序储存结构队列的基本定义队列的基本操作初始化队列求队列长度入队列操作出队列函数打印该队列项目整体源代码: 队列的基本定义 队列是只允许在一端进行插入操作,而在另一端进行删除操作的...
  • 引言:这篇文章的末尾有完整的实现代码,前面还是先进行分步实现,即我们探讨一下为什么要这样做,以及我们应该怎么样一步一步的实现循环队列。 目录 一、队列的概念 二、队的基本操作 三、对于队的操作,了解...
  • 队列(Queue)是另一种限定性的线性表,它只允许再表的一端插入元素,而再另一端删除元素,多以队列具有先进先出(First In First Out,FIFO)的特性。这与我们日常生活中的排队是一样的,最早进入队列的人最早离开,新...
  • 文章目录顺序存储队列的缺点循环队列定义 顺序存储队列的缺点 我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即时对头,所谓的...
  • 顺序存储的队列,元素循环存储循环队列定义循环队列判空、判满循环队列长度代码实现测试结果 循环队列定义 在逻辑上把顺序存储的队列想象成一个环,就是循环队列循环队列仍是顺序存储,只是元素可以循环存储在...
  • 【数据结构】队列的顺序存储实现-循环队列 //循环队列的实现 //队列向前删除,向后新增元素,实现先进先出,如排队 #include&lt;iostream&gt; using namespace std; ​ typedef int ElementType; #define ...
  • 数据结构 顺序队列 循环队列 链对列
  • 实验要求 编写一个程序,以菜单形式实现循环队列的各种基本运算,并在此基础上设计一个主程序,完成如下功能: (1)初始化空队列 (2)建立循环队列 ...#define maxsize 10 //宏定义循环队列最大存储空间
  • 队列之循环队列详解(C语言版)

    千次阅读 2021-02-15 20:41:59
    本篇文章详细的介绍了数据结构队列中的循环队列,并用C语言对其常用操作进行了实现。
  • 队列(queue)是只允许在一段进行插入操作,而在另一端进行删除操作的线性表。具有先进先出的特点,允许插入的一段称为队尾,允许删除的一端称为队头。
  • 循环队列的顺序存储结构的实现(七)

    千次阅读 多人点赞 2018-11-24 10:55:44
    顺序存储的队列写起来跟顺序实现的栈很像,也是采用数组存储数据,但是在不断入队列和出队列过程中,数据会不断后移,所以会造成大量的空间浪费,所以这里我们采用循环队列的形式 循环队列长度 我们需要知道,循环...
  • 1.顺序队列的常用基本操作及条件判断 队空: Q.front=Q.rear 队满: Q.rear=Maxlen 求队长: Q.rear-Q.front 入队: 1)新元素按 rear 指示位置加入 ...2.顺序队列的类型定义 #define ...
  • 数据结构之数组存储循环队列(C++实现) 本实验程序用于验证循环队列的基本操作算法,包括:入队、出队、取队头元素、取队尾元素、判队空或满、显示队列元素等。为了用户了解循环队列的循环特性,在基本操作中,...
  • 循环队列

    2021-07-15 02:42:30
    为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的...中文名循环队列外文名Circular Queue领域实现方式有关术语特点大小固定循环队列简介编辑语音循环队列就是将队列存储空间的最后...
  • 1、定义循环队列结构 2、返回循环队列的长度 3、访问循环队列元素 4、取循环队列的队头元素 5、在循环队列的队尾插入元素 6、删除循环队列的队头元素 7、清空循环队列 8、销毁一个循环队列 9、主函数
  • 队列定义 队列(queue )简称队,它同堆栈一样,也是一种运算受限的线性表, 其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。 在队列中把插入数据元素的一端称为 队尾(rear) ),删除数据元素的一端...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 156,175
精华内容 62,470
关键字:

循环队列的存储结构定义