精华内容
下载资源
问答
  • 里面包含了c文件和exe文件,基本操作为:1:初始化链队列2:销毁链队列3:清空链队列4:链队列是否为空5:返回链队列头元素6:元素入队7:元素出队8:当前链队列长度
  • 淮海工学院计算机科学系 实验报告书 课程名 数据结构 题 目 数据结构实验 链队列和循环队列 班 级 学 号 姓 名 评语 成绩 指导教师 批阅时间 年 月 日 数据结构 实验报告 - 1 - 线性数据结构算法实现与应用报告要求 ...
  • 注:分为四个内容:顺序栈、链栈、循环队列、链队列。代码由C++程序设计语言编写,包含栈和队列的基本操作(栈:出、入、取、判空等|队列:出、入、取、打印队列、判空等),并展示了三个具体的使用例子,包括用栈求...
  • 实验六 栈队列的实现 一实验目的 通过实验掌握队列的逻辑结构特点 掌握队列的初始化入队出队和取队首元素等基本操作算法 二实验内容 利用队列模拟银行办理业务时系统叫号客户等待和接受服务的过程
  • C语言中链队列的实现

    2019-01-06 11:01:27
    通过C来实现链队列的代码,包括队列中各个元素的添加和删除函数
  • C语言版实现链队列

    2020-12-25 21:48:53
    本文实例为大家分享了C语言实现链队列的具体代码,供大家参考,具体内容如下 源文件部分: 指针没学好的同学很难看懂^_^,有点乱,希望对大家有点帮助。 #include #include #include #include typedef int ...
  • 链队列(欠判队空操作) 主函数部分纯属测试 部分内容: Status InitQueue (LinkQueue &Q); // 构造一个空队列Q Status EnQueue (LinkQueue &Q,QElemType e) ;// 插入元素e为Q的新的队尾元素 Status DeQueue ...
  • 根据栈和队列的抽象数据类型的定义,按要求实现一个栈或一个队列。 要求: 1、 实现一个共享栈 2、 实现一个链栈 3、 实现一个循环队列 4、 实现一个链队列
  • 链队列和顺序队列.zip

    2019-08-30 19:17:59
    C语言编写的链队列和顺序队列,内含有良好的交互式界面,可以通过指令测试程序,可用于展示给其他人看。代码格式规范,有大量注释。
  • 链队列程序

    2015-04-12 22:14:34
    该程序包括链队列的创建,销毁,清空,添加,删除等。可以根据自己的需要完成相关的功能。
  • 链队列实现

    2018-06-17 10:35:06
    使用纯指针实现的队列数据结构,代码很清晰明了,可以很容易懂
  • 数据结构:链队列

    2014-05-30 10:37:57
    单链队列,详细内容见博文:http://blog.csdn.net/u013071074/article/details/27641665
  • java语言实现链队列

    2021-05-13 09:22:28
    使用java语言实现链队列


    前言:
    队列是一种特殊的线性表,他的特殊性体现在只能在尾部进行插入,头部进行删除,所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的,而线性表又有顺序表和链表两种,所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用单链表来实现的队列–链队列。若是需要查看顺序队列实现请点这里: 顺序队列

    一、实现过程

    1.提供队列的接口:IQueue

    该接口定义了队列中必须实现的方法,因此在队列实现时只需要继承该接口然后正确实现该接口中的方法即可。无论是顺序队列还是链队列。都可以通过实现该接口来实现,下面是该接口中具体定义的方法。

    public interface IQueue {
        void clear();
        boolean isEmpty();
        int length();
        Object peek();//查看队列头元素
        void offer(Object object) throws Exception;//入队
        Object poll();//出队
    }
    

    2.提供节点类:Node

    因为链队列的底层是单链表,因此我们必须要为单链表提供节点类,节点类需要包含两部分:一部分是数据域用以存储数据;一部分是指针域用以存储指向下一节点的指针。同时需要提供相应的构造方法,代码如下:

    public class Node {
        public Object object;
        public Node next;
    
        public Node(){
        }
        public Node(Object object){
            this.object = object;
        }
        public Node(Node next){
            this.next = next;
        }
        public Node(Object object,Node next){
            this.object = object;
            this.next = next;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "object=" + object +
                    ", next=" + next +
                    '}';
        }
    }
    

    3.提供链队列的实现:LinkedQueue

    链队列因为数据流向都是单向的,因此使用单链表就可以实现。又根据队列的“先进先出”规则我们可以知道我们需要同时关注首结点和尾结点,因此需要声明尾结点,这样我们在尾部插入时就会很方便,若是不使用尾结点的话,每次队列的插入操作就需要遍历到链表的尾部进行插入,这样每次插入的时间复杂度都变成了O(n),这是很耗费性能的。因此我们需要提供带有尾结点的单链表,同时提供首结点,用以标注链表的开始,注意这里是首结点不是头结点。首结点与头结点的区别是首结点存储数据,头结点是不存储数据的。提供了首结点和尾结点后我们还需要在构造器中对他们进行初始化。代码如下:

    /**
     * 链式队列就相当于,既含有首结点,也含有尾结点的单链表
     * @author pcc
     * @version 1.0.0
     * @className LinkedQueue
     * @date 2021-04-29 09:55
     */
    public class LinkedQueue implements IQueue{
        Node front;//首结点
        Node rear;//尾结点
    
        public LinkedQueue(){
            front = rear  = new Node();
        }
    
        @Override
        public void clear() {
            front = null;
            rear = null;
    
        }
    }
    

    4.提供清空(clear)、判空(isEmpty)、队列长度(length)等方法

    这些方法的实现就比较简单,就一起简单说下就好。初始状态下front和rear节点相等且他们的数据域都是null,因此清空时我们就将队列还原成这个样子即可;判空也是判断首结点和尾结点是不是在初始装态,是的话自然就是空的了;队列长度的求取有两种方案,一种是维护一个计数器每次出队和入队时进行计算。另外一种就是遍历链表计算结点个数,笔者使用的是遍历链表,代码实现如下:

        @Override
        public void clear() {
            front = rear  = new Node();
    
        }
    
        @Override
        public boolean isEmpty() {
            if(front == rear && front.object == null)
                return true;
            return false;
        }
    
        @Override
        public int length() {
            int length = 0;
            Node temp = front;
            if(front!=rear)
                while(temp!=null){
                    length++;
                    temp = temp.next;
                }
            return length;
        }
    

    5.提供入队方法:offer

    队列的典型特征是“先进先出”,因此我们肯定是在一端进行插入一端进行删除。简单分析下数据的插入场景后可以发现,在第一个数据插入时front和rear应该还是相等的,只有一个元素时首结点也是尾结点;数据量大于1时则首结点和尾结点则不会有直接关系,此时的插入只需要在尾结点后继续拼接即可,代码如下:

        @Override
        public void offer(Object object) throws Exception {
            Node temp = new Node(object,null);
            if(rear.object==null)
                rear = front = temp;
            else{
                rear.next = temp;//尾部插入
                rear = temp;
            }
    
        }
    

    6.提供出队方法:poll

    队列的典型特征是“先进先出”或者叫“后进后出”,插入时选择在尾部插入,那么我们显然就应该在头部进行删除(反过来其实一样:在链表的头部进行插入尾部进行删除)。头部进行删除我们应该考虑两种情况一种是只有一个元素时一种是多个元素时,一个元素时front和rear相等,此时出队后队列就空了。多个元素时只需要将首结点的下一个结点设置为首结点即可。代码实现如下:

        @Override
        public Object poll() {
            if(front!=null){
    
                Node frontTemp = front;
                if(front==rear){//只有一个元素时出队
                    front = rear = new Node();
                }else{//其他场景出队
                    front = front.next;
                }
                return frontTemp.object;
            }
            return null;
        }
    

    7.提供获取队列头部元素的方法:peek

    该方法只是返回队列的头部元素,并不进行出队。该方法的实现就比较简单了,我们只需要确定首结点不是null即可,非null返回首结点的数据域,否则返回null。代码如下:

        @Override
        public Object peek() {
            return front!=null?front.object:null;
        }
    

    8.提供实现的完整代码

    到这里链队列的方法就都实现了,各个方法实现起来其实都不难,难的是什么呢?好像没有难的,知道链队列的思想就可以轻松实现了。下面贴下链栈的完整代码:

    /**
     * 链式队列就相当于,既含有首结点,也含有尾结点的单链表
     * @author pcc
     * @version 1.0.0
     * @className LinkedQueue
     * @date 2021-04-29 09:55
     */
    public class LinkedQueue implements IQueue{
        Node front;//首结点
        Node rear;//尾结点
    
        public LinkedQueue(){
            front = rear  = new Node();
        }
    
        @Override
        public void clear() {
            front = rear  = new Node();
    
        }
    
        @Override
        public boolean isEmpty() {
            if(front == rear && front.object == null)
                return true;
            return false;
        }
    
        @Override
        public int length() {
            int length = 0;
            Node temp = front;
            if(front!=rear)
                while(temp!=null){
                    length++;
                    temp = temp.next;
                }
            return length;
        }
    
        @Override
        public Object peek() {
            return front!=null?front.object:null;
        }
    
        @Override
        public void offer(Object object) throws Exception {
            Node temp = new Node(object,null);
            if(rear.object==null)
                rear = front = temp;
            else{
                rear.next = temp;//尾部插入
                rear = temp;
            }
    
        }
    
        @Override
        public Object poll() {
            if(front!=null){
    
                Node frontTemp = front;
                if(front==rear){//只有一个元素时出队
                    front = rear = new Node();
                }else{//其他场景出队
                    front = front.next;
                }
                return frontTemp.object;
            }
    
    
            return null;
        }
    }
    
    

    二、测试顺序队列的相应方法

    1.测试入队和出队

    链队列的实现已经完成了,下面需要测试下实现的方法是否正确,根据队列的“先进先出”特点,若是入队和出队的顺序保持一致,则说明方法的实现没有问题,测试结果如下,可以发现方法的入队和出队是一致的,也代表队列的入队和出队方法没有问题。
    在这里插入图片描述

    2.测试其他方法

    上面的案例中已经测试了入队、出队、长度、非空等方法了,下面再配合清空方法测试下,如下图:
    在这里插入图片描述
    由上图可以看出:插入5个元素后队列长度是5、此时判空是false、然后清空操作再判空是true、然后获取首元素就是null;可以发现这些方法的操作和输出都没有问题。

    三、总结

    这篇文章总结了链队列的实现,代码是没有难度的,主要是掌握队列的思想。无论是使用单链表还是顺序表来实现队列,都只是队列的内部实现而已,平时的使用更关注的是队列的操作。队列是一种使用很广的数据结构,使用频率也很高,比如jvm中的finalize队列,线程池的等待队列,以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的,这篇文章只是以一个实现者的角度去写的,可能并不是适合很多人,但也希望可以帮到看到这篇文章的你。

    展开全文
  • 数据结构(严蔚敏)实验代码
  • 编写一个程序,实现链队列的各种基本运算,并在基础上完成以下功能: 1) 初始化链队列; 2) 判断链队列是否为空; 3) 依次进队元素a,b,c; 4) 出队一个元素,并输出该元素; 5) 输出链队列的长度; 6) 依次进队元素d,...
  • 链队列

    2019-01-23 15:19:08
    在对链队列做出队操作时,不会改变front指针的值。(B) A.T B.F 笔记: 若链队列是带头结点的,则不会改变; 若链队列是不带头结点的,则定会改变;因为头指针会始终指向队首元素,当然会改变。 ...

    在对链队列做出队操作时,不会改变front指针的值。(B)

    A.T
    B.F

    笔记:

    若链队列是带头结点的,则不会改变;

    若链队列是不带头结点的,则定会改变;因为头指针会始终指向队首元素,当然会改变。

    展开全文
  • 队列之链队列详解(C语言版)

    千次阅读 多人点赞 2021-02-13 22:17:47
    本篇文章详细的介绍了数据结构队列中的链队列,并用C语言对其常用操作进行了实现。


    前言

            大家好,越努力,越幸运。本篇文章小猿将跟您分享数据结构队列中的链队列,希望对您有所帮助。

    在这里插入图片描述

    一、链队列的定义

           首先我们来看看什么是队列?队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。队列的结构图如下所示:
    在这里插入图片描述
           明白了队列之后,链队列就非常简单了,用链表表示的队列就简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能惟一确定。

    二、链队列的结构

    结构图
    在这里插入图片描述
    代码描述

    //数据类型
    #define ElemType int
    
    //队列结点类型
    typedef struct QueueNode
    {
    	ElemType data;          //数据域
    	struct QueueNode *next; //指针域
    }QueueNode;
    
    //链式队列管理结构
    typedef struct LinkQueue
    {
    	QueueNode *front;  //队头指针
    	QueueNode *tail;   //队尾指针
    }LinkQueue;
    

    三、链队列的常用操作

    初始化

    //初始化队列
    void InitQueue(LinkQueue *Q)
    {
    	//申请头结点内存空间
    	QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    	assert(s != NULL);
    	//初始化时,将头指针和尾指针都指向头结点
    	Q->front = Q->tail = s;
    	//将头结点的下一结点赋空
    	Q->tail->next = NULL;
    }
    

    入队

    //入队操作:在队尾执行插入操作
    void EnQueue(LinkQueue *Q, ElemType x)
    {
    	//申请队列结点
    	QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    	assert(s != NULL);
    	//为申请的队列结点赋值
    	s->data = x;
    	s->next = NULL;
    	//将申请的队列结点插入到队尾
    	Q->tail->next = s;
    	//更改队列管理结点中尾指针的指向
    	Q->tail = s;
    }
    

    出队

    //出队操作:删除队头的第一个有效结点
    void DeQueue(LinkQueue *Q)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//将队头的第一个有效结点从队列中断开
    	Q->front->next = p->next;
    	//释放该结点
    	free(p);
    	//如果删除的结点是最后一个有效结点,需要更改尾指针的指向
    	if(p == Q->tail)
    		Q->tail = Q->front;
    }
    

    打印队列数据

    //打印队列内的数据
    void ShowQueue(LinkQueue *Q)
    {
    	//获取队列中第一个有效结点
    	QueueNode *p = Q->front->next;
    	printf("Front:>");
    	//将队列中每个有效结点中的数据打印
    	while(p != NULL)
    	{
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("<:Tail.\n");
    }
    

    获取队头元素

    //获取队头元素
    void GetHead(LinkQueue *Q, ElemType *v)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//返回队头第一个有效结点数据
    	*v = p->data;
    }
    

    求队列长度

    //求队列的长度
    int Length(LinkQueue *Q)
    {
    	int len = 0;//初始长度为0
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//遍历队列,获取一个结点,将队列长度加一
    	while(p != NULL)
    	{
    		len++;
    		p = p->next;
    	}
    	//返回长度值
    	return len;
    }
    

    清空队列

    //清空队列:释放所有的有效结点
    void ClearQueue(LinkQueue *Q)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//遍历队列中的有效结点
    	while(p != NULL)
    	{
    		//移除结点
    		Q->front->next = p->next;
    		//释放结点
    		free(p);
    		//指向下一个结点
    		p = Q->front->next;
    	}
    	Q->tail = Q->front;
    }
    

    销毁队列

    //销毁队列
    void DestroyQueue(LinkQueue *Q)
    {
    	//清空队列
    	ClearQueue(Q);
    	//释放头结点
    	free(Q->front);
    	//将管理结点中的头指针和尾指针都指向空
    	Q->front = Q->tail = NULL;
    }
    

    结语

            对链队列的介绍就到这里啦,希望这篇文章能给予你一些帮助,感谢各位人才的:点赞、收藏和评论,我们下次见。
    在这里插入图片描述

    附录

    以下提供链队列的测试代码

    LinkQueue.h

    #ifndef __LINKQUEUE_H__
    #define __LINKQUEUE_H__
    
    #include<stdio.h>
    #include<malloc.h>
    #include<assert.h>
    
    //数据类型
    #define ElemType int
    
    //队列结点类型
    typedef struct QueueNode
    {
    	ElemType data;          //数据域
    	struct QueueNode *next; //指针域
    }QueueNode;
    
    //链式队列管理结构
    typedef struct LinkQueue
    {
    	QueueNode *front;  //队头指针
    	QueueNode *tail;   //队尾指针
    }LinkQueue;
    
    void InitQueue(LinkQueue *Q);
    void EnQueue(LinkQueue *Q, ElemType x);
    void ShowQueue(LinkQueue *Q);
    void DeQueue(LinkQueue *Q);
    void GetHead(LinkQueue *Q, ElemType *v);
    int Length(LinkQueue *Q);
    void ClearQueue(LinkQueue *Q);
    void DestroyQueue(LinkQueue *Q);
    
    #endif //__LINKQUEUE_H__
    

    LinkQueue.cpp

    #include"LinkQueue.h"
    
    //初始化队列
    void InitQueue(LinkQueue *Q)
    {
    	//申请头结点内存空间
    	QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    	assert(s != NULL);
    	//初始化时,将头指针和尾指针都指向头结点
    	Q->front = Q->tail = s;
    	//将头结点的下一结点赋空
    	Q->tail->next = NULL;
    }
    
    //入队操作:在队尾执行插入操作
    void EnQueue(LinkQueue *Q, ElemType x)
    {
    	//申请队列结点
    	QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    	assert(s != NULL);
    	//为申请的队列结点赋值
    	s->data = x;
    	s->next = NULL;
    	//将申请的队列结点插入到队尾
    	Q->tail->next = s;
    	//更改队列管理结点中尾指针的指向
    	Q->tail = s;
    }
    
    //打印队列内的数据
    void ShowQueue(LinkQueue *Q)
    {
    	//获取队列中第一个有效结点
    	QueueNode *p = Q->front->next;
    	printf("Front:>");
    	//将队列中每个有效结点中的数据打印
    	while(p != NULL)
    	{
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("<:Tail.\n");
    }
    
    //出队操作:删除队头的第一个有效结点
    void DeQueue(LinkQueue *Q)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//将队头的第一个有效结点从队列中断开
    	Q->front->next = p->next;
    	//释放该结点
    	free(p);
    	//如果删除的结点是最后一个有效结点,需要更改尾指针的指向
    	if(p == Q->tail)
    		Q->tail = Q->front;
    }
    //获取队头元素
    void GetHead(LinkQueue *Q, ElemType *v)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//返回队头第一个有效结点数据
    	*v = p->data;
    }
    
    //求队列的长度
    int Length(LinkQueue *Q)
    {
    	int len = 0;//初始长度为0
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//遍历队列,获取一个结点,将队列长度加一
    	while(p != NULL)
    	{
    		len++;
    		p = p->next;
    	}
    	//返回长度值
    	return len;
    }
    
    //清空队列:释放所有的有效结点
    void ClearQueue(LinkQueue *Q)
    {
    	//如果队中无有效结点,无需进行操作
    	if(Q->front == Q->tail)
    		return;
    	//获取队头的第一个有效结点
    	QueueNode *p = Q->front->next;
    	//遍历队列中的有效结点
    	while(p != NULL)
    	{
    		//移除结点
    		Q->front->next = p->next;
    		//释放结点
    		free(p);
    		//指向下一个结点
    		p = Q->front->next;
    	}
    	Q->tail = Q->front;
    }
    
    //销毁队列
    void DestroyQueue(LinkQueue *Q)
    {
    	//清空队列
    	ClearQueue(Q);
    	//释放头结点
    	free(Q->front);
    	//将管理结点中的头指针和尾指针都指向空
    	Q->front = Q->tail = NULL;
    }
    

    Main.cpp

    #include"LinkQueue.h"
    
    void main()
    {
    	LinkQueue Q;
    	InitQueue(&Q);//初始化队列
    	
    	for(int i=1; i<=10; ++i)
    	{
    		EnQueue(&Q,i);//入队操作
    	}
    	ShowQueue(&Q);
    	DeQueue(&Q);
    	DeQueue(&Q);
    	ShowQueue(&Q);
    	printf("Len = %d\n",Length(&Q));
    }
    
    展开全文
  • 队列——链队列和循环队列

    千次阅读 2018-11-03 16:02:15
    链队列 转载:https://www.cnblogs.com/muzijie/p/5655228.html 1 链队列的存储结构  将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。 空队列时,头指针front和尾指针rear都指向头结点。 ...

    链队列

    转载:https://www.cnblogs.com/muzijie/p/5655228.html

    1 链队列的存储结构

      将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。

    空队列时,头指针front和尾指针rear都指向头结点。

     

    链队列的存储结构为:

    typedef int QElemType;
    typedef struct QNode {            //结点结构
        QElemType data;
        struct QNode *next;
    }QNode;
    
    typedef struct QNode * QueuePtr;
    
    typedef struct {                //队列的链表结构
        QueuePtr rear;
        QueuePtr front;
    }LinkQueue;

    2 入队操作

    //插入元素e为Q的新的队尾结点
    Status EnQueue(QueuePtr Q, QElemType e) {
        QueuePtr q = (QueuePtr)malloc(sizeof(QNode));
        if (!q) {                //存储分配失败
            exit(OVERFLOW);
        }
        q->data = e;
        q->next = NULL;
        Q->rear->next = q;
        Q->rear = q;
        return OK;
    }

    3 出队操作

      出队操作,就是头结点的后继结点出队,将头结点的后继改为它后面的结点。

      若链表除头结点外只剩一个元素时,则需将rear指针指向头结点。

    //若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR。
    Status DeQueue(QueuePtr Q, QElemType *e) {
        QueuePtr q;
        if (Q->rear == Q->front) {        //空队列
            return ERROR;
        }
        q = Q->front->next;                //q指向第一个结点
        *e = q->data;
        Q->front->next = q->next;
    
        if (Q->rear == p) {                //若队头就是队尾,删除后,需要将rear指针指向头结点
            Q->rear = Q->front;
        }
        free(q);
        return OK;
    }

    4 循环队列与链队列的比较

      从时间上考虑,循环队列和链队列的基本操作都是O(1),不过循环队列是事先已申请好空间,使用期间不会释放。而对于链队列,每次申请和释放结点也会存在一些时间开销。如果入队和出队频繁,两者还是有细微差异的。
      从空间来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但是是可以接受的。所以从空间上说,链队列更加灵活。
      总的来说,在可以确定链队列最大长度的情况下,建议使用循环队列。如果无法预估队列的长度,则使用链队列。

     

     

    循环队列

    转载:https://www.cnblogs.com/hughdong/archive/2017/05/11/6841970.html

    (作者说的挺有意思的话:You know something and I know nothing.)

            和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队头到队尾的元素外,尚需敷设两个指针front和rear分别指示队列头元素位置和队列尾元素的位置。

    如果使用顺序表作为队列的话,当处于右图状态则不能继续插入新的队尾元素,否则会因为数组越界而导致程序代码被破坏。

     

    由此产生了由链表实现的循环队列,只有队列未满时才可以插入新的队尾元素。

     

    下面内容,转载:https://www.cnblogs.com/chenliyang/p/6554141.html

            1.图中有两个指针(其实就是两个整数型变量,因为在这里有指示作用,所以这里理解为指针)front、rear,一个指示队头,一个指示队尾。

         2.rear和front互相追赶着,这个追赶过程就是队列添加和删除的过程,如果rear追到head说明队列满了,如果front追到rear说明队列。

    说明:令队列空间中的一个单元闲置,使得队列非空时,Q.rear与Q.front之间至少间隔一个空闲单。(思考为什么空一格)

         3.我们把它掰弯,用的是求余,这样两个值就不会跑出最大范围,并且可以实现弯曲的效果,所以说对于循环队列我们必须给定最大值MAXQSIZE。

       这其实是我们臆想的,反正我们要做的就是利用循环来解决空间浪费的问题。  

    循环队列的实现过程(important)

        ☆当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余?

        ☆当删除一个元素时,(front+1)%MAXQSIZE;//理解为什么求余?

        ☆当rear=front的时候,队列可能是满,也可能是空。(这也是为什么空一格的原因)

          因为存在满和空两种情况,我们需要分别判断:

            ☆:当队列添加元素到rear的下一个元素是head的时候,也就是转圈子要碰头了,我们就认为队列满了。(Q.rear+1)%MAXSIZE=Q.front

            ☆:当队列删除元素到head=rear的时候,我们认为队列空了。Q.rear==Q.front,不一定为0

            上面这一段要好好理解,在其他编程的地方,也会用到类似的思想。

            下面的代码思想很重要。

    2.1对节点的定义

    #define MAXQSIZE 100
    typedef int QElemtype;
    typedef int status;
    
    typedef struct{
        QElemtype *base;
        int front;
        int rear;
        }SqQueue;

    2.2初始化队列

    SqQueue* InitQueue()
    {
        SqQueue *q;
        q=new SqQueue;
        q->base=new int[MAXQSIZE];
        q->rear=q->front=0;
        return q;
    }

    2.3添加操作

    status EnQueue(SqQueue *q,QElemtype e)
    {
        //插入到队尾
        if((q->rear+1)%MAXQSIZE==q->front)
            return 0;
        q->base[q->rear]=e;
        q->rear=(q->rear+1)%MAXQSIZE;
        return 1;
    }

    2.4删除操作

    status DeQueue(SqQueue *q)
    {
        if(q->front==q->rear)
            return 0;
        printf("%d",q->base[q->front]);
        q->front =(q->front+1)%MAXQSIZE;
        return 1;
    }

    备注,这插入和删除的操作,类似于标记。(这也很重要)

    2.5获取队列长度

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

     

    补:还有些其他的队列,比如优先队列,双端队列。(用的时候可以查STL)

    队列练习:

    团体队列

    并行程序模拟

     

    展开全文
  • 数据结构-链队列详解(很经典的那种)

    千次阅读 多人点赞 2020-11-16 11:38:07
    链队列的设计与运行 1.链队 这里的链队,也是队列的一种,只不过运用链表的知识对队列进行再设计 还是老话,让我们动手实践~ 2.代码部分 主函数(实现对功能的选择) #include"basic.h" int main() { int ...
  • 队列----链队列

    千次阅读 2019-04-15 09:55:03
    链队列:使用链表实现的队列;具有队头指针和队尾指针,指示队列元素所在的位置。 链队列特性: 只能队尾插入元素、在队头删除元素。 先进先出(First In First Out)的线性表,先进入的元素出队,后进入的元素...
  • 队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端...
  • 链队列的基本操作和实现链队列的基本操作和实现
  • 链队列模板

    2014-09-17 11:15:50
    用C++编写的链队列模板,有必要注释,可以运行。
  • C语言实现链队列

    2020-12-31 13:08:24
    记录一下C语言实现的链队列代码,供大家参考,具体内容如下 #include #include #include typedef int ElemType; //链队列的结点定义 typedef struct node{ ElemTypeval; struct node* next; }QueueNode; //链队列...
  • python实现链队列

    2020-06-10 08:20:51
    python链队列 在写链队列之前,我们需要知道队列元素进出的原则为“先进先出”。 class Node(): #结点类 def __init__(self,elem): self.elem = elem # 数据域,用来存放数据元素 self.next = None # 指针域,...
  • 顺序队列,链队列的基本操作 一、实验目的 1.深入了解队列的定义和特性。 2.掌握队列的数组表示、链表表示以及相应操作的实现,巩固对这两种结构的构造方法的掌握。 3. 会灵活运用队列结构解决某些实际问题。 二、...
  • C语言实现链队列代码

    2020-12-31 12:01:41
    本文实例为大家分享了C语言实现链队列的具体代码,供大家参考,具体内容如下 #include /* 队列的结构体 */ typedef int DataType; #define NODE_LEN sizeof(NODE) /* 队列的节点 */ typedef struct stNode { ...
  • JAVA实现链队列

    2020-03-23 00:04:43
    JAVA实现链队列 队列是一种特殊的线性表,主要的特点在于其添加数据是在队尾进行操作的而删除数据是在队首进行操作的。 定义Node类 class Node{ int data; Node next; public Node(int data){ this.data=data; ...
  • 链队列的各种基本运算

    千次阅读 多人点赞 2017-12-04 17:32:56
    链队列的各种基本运算 码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创 。   欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正错误回答...
  • 链队列的几种基本操作

    千次阅读 多人点赞 2018-11-27 12:25:08
    cout链队列不存在!"; cout请输入你的选择:"; break; } else { ClearQueue(q); cout清空成功!"; cout请输入你的选择:"; break; } case 4: if(q.front == NULL...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 351,032
精华内容 140,412
关键字:

链队列