精华内容
下载资源
问答
  • 循环队列和链队列

    2020-05-22 21:04:51
    //容易 #include<cstdio> #include<cstdlib> # define OK 1 #define ERROR 0 #define MAXSIZE 100 ...//循环队列的顺序存储结构 typedef struct { Qelemtype data[MAXSIZE]; int front; i
    //容易
    #include<cstdio>
    #include<cstdlib>
    # define OK 1
    #define ERROR 0
    #define MAXSIZE 100
    typedef int Qelemtype;
    typedef int status;
    //可根据需要随时改动Qelemtype和status的类型
    //循环队列的顺序存储结构
    typedef struct
    {
        Qelemtype data[MAXSIZE];
        int front;
        int rear;
    }SqQueue;
    //循环队列的初始化
    status InitSqQueue(SqQueue &Q)
    {
        Q.front=0;
        Q.rear=0;
        return OK;
    }
    //循环队列求队列长度
    //返回Q的元素e个数,也就是当前d循环队列长度
    status QueueLength(SqQueue &Q)
    {
        return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
    }
    //循环队列的入队列操作
    //若队列未满,则插入元素e为新的队尾元素
    status EnQueue(SqQueue &Q,Qelemtype e)
    {
        if((Q.rear+1)%MAXSIZE==Q.front)//队列满的判断
            return ERROR;
        Q.data[Q.rear]=e;             //将元素e赋值给队尾元素
        Q.rear=(Q.rear+1)%MAXSIZE;    //rear指针向后移一位置
                                      //若到最后则转到数组头部
        return OK;
    }
    //循环队列的出队列操作
    //若队列不为空,则删除Q中队头元素,用e返回其值
    status DeQueue(SqQueue &Q,Qelemtype *e)
    {
        if(Q.front==Q.rear)            //队列空的判断
            return ERROR;
        *e=Q.data[Q.front];           //将队头元素赋值给e
        Q.front=(Q.front+1)%MAXSIZE;  //front指针向后移一位置
                                      //若到最后则转到数组头部
        return OK;
    }
    //取队头元素
    bool GetHead(SqQueue Q,Qelemtype &e)
    {
        if(Q.front !=Q.rear)          //队列非空
    {
        e=Q.data[Q.front];
        return true;
    }
    else    return false;             //队列为空返回false
    }
    //循环队列的遍历
    void QueueTraverse(SqQueue Q)
    {
        for (int k=0;k<(Q.rear-Q.front+MAXSIZE )%MAXSIZE;k++)
        {
        printf("%d",Q.data[(Q.front+k)%MAXSIZE]);
        printf("\n");
        }
    }
    
    //链队列的存储结构
    typedef struct QNode
    {
        Qelemtype data;
        struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct
    {
        QueuePtr front,rear;  //队头队尾指针
    }LinkQueue;
    //队列的链式存储结构——入队操作
    //插入元素e为Q的新的队尾元素
    status En_LinkQueue(LinkQueue &Q,Qelemtype e)
    {
        QueuePtr s=(QueuePtr)malloc(sizeof(QNode));//分配一个结点的空间给结构体指针变量s
        if(!s)                                     //若存储分配失败
            exit(ERROR);
        s->data=e;
        s->next=NULL;
        Q.rear->next=s;              //将新结点s赋值给原队尾结点的后继
        Q.rear=s;               //将当前sz设置为队尾结点,rear指向s
        return OK;
    }
    //队列的链式存储结构——出队操作
    //若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
    status De_LinkQueue(LinkQueue &Q,Qelemtype *e)
    {
        QueuePtr p;
        if(Q.front==Q.rear)//若队列为空
            return ERROR;
        p=Q.front->next;  //将欲删除的队头结点暂存给p
        *e=p->data;    //将欲删除的队头结点的值赋值给e
        Q.front->next=p->next; //将原队头结点的后继赋值给头结点后继
        if(Q.rear==p)//若队头是队尾,则删除后将rear指向头结点
            Q.rear=Q.front;
        free(p);
        return OK;
    }
    
    展开全文
  • 循环队列和链队列的比较

    前言

    本文原本是一篇随感+笔记,被翻出来后就整理发了博客。
    不曾想能上搜索头条,既如此,决定更新一下,加上必要的阐释,避免影响有需求的读者。
    (我这么理解大家,如果有需要的话,是不是可以考虑点个赞或者点个关注再走呢?)

    编程实现

    说实话,这个编程实现的话,emmmm……我其实不喜欢用Python那种太强的语言,本想用C/C++,奈何网上或者教材多用C/C++,不需要我单独写,另外是我个人用Java比较熟练一些,就用Java实现的这两种数据结构:

    勉强可以一看啦,因为其实这只是编程实现,所以不涉及分析。
    分析的话以后再说吧Orz……有问题可以问我,嗯……

    总结

    作为队列本身来说,在队首出队和队尾入队的效率都很高——O(1),因此二者可以直接比较的只有空间性能。
    初始化时循环队列必须确定一个固定的长度,所以有储存元素个数的限制和浪费空间的问题;
    链队列没有溢出的问题,只有当内存没有可用空间时才会出现溢出,但是每个元素都需要一个引用域,从而产生了结构性开销。

    展开全文
  • 队列可以分为顺序队列,循环队列以及链队列 顺序队列: (1)如果队首元素删除之后,所有元素不移动,那么入队出队操作的时间复杂度是O(1) (2)如果队首元素删除之后,所有元素都要往前移动一位,那么入队的时间...

    队列可以分为顺序队列,循环队列以及链队列
    顺序队列:
    (1)如果队首元素删除之后,所有元素不移动,那么入队和出队操作的时间复杂度是O(1)
    (2)如果队首元素删除之后,所有元素都要往前移动一位,那么入队的时间复杂度是O(1),出队的复杂度是O(n)
    第一种做法在时间复杂度上比第二种做法要优越,但是可能会发生"假溢出",也就是数组的低端还有空闲位置,但是数组的高端却被插满了

    循环队列:
    循环队列则可以很好地解决"假溢出"这个问题,当数组高端满了之后,可以将队尾指针指向数组低端位置,这样就可以解决"假溢出"问题
    其中,判断队满的条件是(rear+1)%queueSize==front,这样做虽然浪费了一个数组元素空间,但是减少了时间代价。判断队空的条件是rear=front
    可以想出,判断队满的条件也可以是rear=front,但是如此做的话,会让判断队空和判断队满的条件重复,因此需要牺牲一个数组元素空间来判断队满

    链队列:
    链队列为了操作的方便,会设置一个头结点,然后用队头指针指向链队列的头结点,队尾指针指向终端结点
    循环队列代码如下:

    #include<iostream>
    #include<string>
    using namespace std;
    const int queueSize = 10;
    template<typename T>
    class CirQueue
    {
    private:
    	int front, rear;
    	T data[queueSize];
    public:
    	CirQueue();
    	void insertQueue(T x);//入队
    	T exitQueue();//出队
    	T getQueueHead();//得到队首元素
    	bool empty();//判断是否为空
    	void printQueue();//打印出队列里面的元素
    };
    
    template<typename T>
    CirQueue<T>::CirQueue()
    {
    	front = rear = queueSize - 1;
    }
    
    template<typename T>
    void CirQueue<T>::insertQueue(T x)
    {
    	if ((rear + 1) % queueSize == front)//插入元素前需要判断队列是否已经满了
    	{
    		throw exception("插入元素时发生了上溢");
    	}
    	rear = (rear + 1) % queueSize;
    	data[rear] = x;
    }
    
    template<typename T>
    T CirQueue<T>::exitQueue()
    {
    	if (front == rear)
    	{
    		throw exception("删除队首元素时发生了下溢");
    	}
    	front = (front + 1) % queueSize;
    	return data[front];
    }
    
    template<typename T>
    T CirQueue<T>::getQueueHead()
    {
    	if (front == rear)
    	{
    		throw exception("获取队首元素时发生了下溢");
    	}
    	int x = (front + 1) % queueSize;
    	return data[x];
    }
    
    template<typename T>
    bool CirQueue<T>::empty()
    {
    	if (front == rear)
    	{
    		return true;
    	}
    	return false;
    }
    
    template<typename T>
    void CirQueue<T>::printQueue()
    {
    	if (front == rear)
    	{
    		throw exception("队列已空,无法打印元素");
    	}
    	front = (front + 1) % queueSize;
    	while (front != rear)
    	{
    		cout << data[front] << endl;
    		front++;
    	}
    	cout << data[front];
    }
    int main()
    {
    	CirQueue<int> cirQueue;
    	try
    	{
    		cirQueue.insertQueue(1);
    		cirQueue.insertQueue(10);
    		cirQueue.insertQueue(100);
    		cirQueue.insertQueue(1000);
    		cout << "删除队首元素:" << cirQueue.exitQueue() << endl;
    		cout << "得到队首元素:" << cirQueue.getQueueHead() << endl;
    		cout << cirQueue.empty();
    		cirQueue.printQueue();
    	}
    	catch (exception e)
    	{
    		cout << e.what() << endl;
    	}
    	return 0;
    }
    

    链队列的代码如下:

    #include<iostream>
    using namespace std;
    template<typename T>
    class Node
    {
    public:
    	T data;
    	Node<T>*next;
    	Node() :next(nullptr) {};
    };
    
    template<typename T>
    class LinkQueue
    {
    private:
    	Node<T>*front, *rear;
    public:
    	LinkQueue();
    	~LinkQueue();
    	void insertQueue(T x);
    	T deQueue();
    	T getHead();
    	void printQueue();
    	bool empty();
    };
    
    template<typename T>
    LinkQueue<T>::LinkQueue()//初始化链队列,将front指针和rear指针都指向头结点
    {
    	Node<T> *s = new Node<T>();
    	front = rear = s;
    }
    
    template<typename T>
    LinkQueue<T>::~LinkQueue()
    {
    	while (front != rear)
    	{
    		Node<T>*p = new Node<T>();
    		p = front;
    		front = front->next;
    		delete p;
    	}
    	delete front;
    }
    
    template<typename T>
    void LinkQueue<T>::insertQueue(T x)//链队列的插入
    {
    	Node<T>*s = new Node<T>();
    	s->data = x;
    	rear->next = s;
    	rear = s;
    }
    
    template<typename T>
    T LinkQueue<T>::deQueue()//链队列的删除
    {
    	if (rear == front)
    	{
    		throw exception("删除队首结点时发生了下溢");
    	}
    	Node<T>*p = new Node<T>();
    	p = front->next;
    	T x = p->data;
    	front->next = p->next;
    	if (front->next == nullptr)
    	{
    		rear = front;
    	}
    	delete p;
    	return x;
    }
    
    template<typename T>
    T LinkQueue<T>::getHead()
    {
    	if (front == rear)
    	{
    		throw exception("得到队首元素时发生了下溢");
    	}
    	return front->next->data;
    }
    
    template<typename T>
    bool LinkQueue<T>::empty()//判断链队列是否为空
    {
    	if (front == rear)
    	{
    		return true;
    	}
    	return false;
    }
    
    template<typename T>
    void LinkQueue<T>::printQueue()
    {
    	if (front == rear)
    	{
    		throw exception("队列为空,无法打印队列");
    	}
    	front = front->next;
    	while (front != nullptr)
    	{
    		cout << front->data << endl;
    		front = front->next;
    	}
    }
    
    int main()
    {
    	LinkQueue<int> linkQueue;
    	linkQueue.insertQueue(10);
    	linkQueue.insertQueue(100);
    	linkQueue.insertQueue(200);
    	linkQueue.insertQueue(300);
    	try
    	{
    		cout << "删除队首元素:" << linkQueue.deQueue() << endl;
    		cout << "删除队首元素:" << linkQueue.deQueue() << endl;
    		cout << "得到队首元素:" << linkQueue.getHead() << endl;
    		cout << "删除队首元素:" << linkQueue.deQueue() << endl;
    		cout << "删除队首元素:" << linkQueue.deQueue() << endl;
    		cout << linkQueue.empty() << endl;
    	}
    	catch (exception e)
    	{
    		cout << e.what() << endl;
    	}
    	return 0;
    }
    
    展开全文
  • 循环队列和链队列(queue)

    千次阅读 2018-11-06 22:32:59
    循环队列和链队列(queue) 队列的定义:队列是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,...

    循环队列和链队列(queue)

     

    队列的定义:队列是一种特殊的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

     

    我们今天来看一看循环队列和链队列

     

    我们先来看一看循环队列的定义:

     

    再看一下链队列的定义:

     

     

     

    -------------------------------------------------------------------------------------------------------------

    循环队列功能的实现:

    ①:初始化

     

    ②:判满

     

    ③:入队

     

    ④:判空

     

    ⑤:出队并将其数值带出

     

     

    ⑥:打印队列

     

    ⑦:清空队列

     

    ⑧:毁灭队列

     

    -------------------------------------------------------------------------------------------------------------

     

     

     

     

     

     

    -------------------------------------------------------------------------------------------------------------

    链队列功能的实现:

     

    ①:初始化

     

    ②:动态开辟新结点

     

    ③:入队

     

    ④:判空

     

    ⑤:出队并将其数值带出

     

    ⑥:打印链队列

     

    ⑦:清空链队列

     

    ⑧:毁灭链队列

     

    -------------------------------------------------------------------------------------------------------------

     

     

    展开全文
  • 循环队列和链队列的实现 指针学的好水啊。。为了加深了对指针的运用 循环队列用了指针 链队列用了引用,还有就是在一个地方卡了好久好久,20多个报错无法编译通过要不要这么狠哇。。。最后发现是case内定义了新的...
  • 今天学了队列,就自己写了一下代码,队列有顺序队列和循环队列以及链队列,由于顺序队列存在“假上溢”现象,所以基本上不用,那么主要研究循环队列和链队列循环队列是采用数组实现的,其中分别由front rear指示...
  • 队列——链队列和循环队列

    千次阅读 2018-11-03 16:02:15
    链队列 转载:https://www.cnblogs.com/muzijie/p/5655228.html 1 链队列的存储结构  将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。 空队列时,头指针front尾指针rear都指向头结点。 ...
  • 循环队列和链队列1. 循环队列1.1 定义1.2 初始化1.3 入队(重点)1.4 出队(重点)1.5 打印队列2. 链队列2.1 定义2.2 初始化2.3 入队(重点)2.4 出队(重点)2.5 打印队列记忆小结 出入队算法为重点 1. ...
  • 循环队列和链队列(Java)

    万次阅读 2020-01-04 13:59:02
    1.循环队列  队列的顺序储存结构:用数组存储队列,引入front指针指向队头元素,rear指针指向队尾元素的下一个位置,当front=rear时,为空队列,结构如下图所示。   当执行入队操作时,若数组尾部已满,而...
  • 队列:顺序队列 循环队列 链队列 用C语言分别实现顺序队列、循环队列链队列,并完成入队、出队、获取对头元素等…… queue.h 在这里插入代码片
  • 1.循环队列:实际上为顺序表,把它认为是循环结构。如下图所示,初始时,first与rear两个指针指向同一块空间,当入队时,从first指向的位置插入值,然后rear指针后移,设M表示队列的长度,则rear=(rear+1)%M,判断...
  • 队列:只允许在一端进行插入操作,在另一端进行产出操作的线性表。 队列是一种先进先出的线性表(简称FIFO)。其中允许插入操作的一端称为队尾,允许删除操作的一端称为队头。例如队列a=(a1,a2,a3,...,an),其中a1是...
  • 通过该实验,使学生理解链队列的构造特点并灵活应用,掌握链队基本操作的编程实现,认识栈是在一端进行插入,在另一端进行删除集中操作的线性结构,掌握队列的“先入先出”操作特点,知道判断队列空满的条件,...
  • C语言数据结构中队列的复习
  • 顺序队列,循环队列链队列
  • 文章目录循环队列存储结构初始化求队列长度入队出队取队头元素队存储结构初始化入队出队取队头元素 循环队列 在顺序分配的队列中,会出现假溢出的情况。 当我们将顺序队列变为一个环状的空间,我们就不会出现假...
  • // 循环队列#include #include "SeqQue.h"// 循环队列的基本运算/*const int maxsize = 20;typedef struct cycque{int data[maxsize];int front, rear;}CycQue;*/// 1. 初始化void InitQueue(CycQue CQ){CQ.front = ...
  • 首先,对于顺序队列,用的比较多的是循环顺序队列,简称循环队列。关于循环队列,阔以参考下面这篇博客的内容,讲解的非常清晰:https://www.cnblogs.com/curo0119/p/8608606.html。在此我不再过多赘述,只贴出自己...
  • 顺序队列一般实现为循环队列,因为普通的队列可能产生“假溢出”。 1 struct SqQueue{ 2 int data[maxSize]; 3 int front;...2.队满 (注意,循环队列必须损失一个存储空间,用来区分队空堆满...
  • 1.循环队列
  • // 循环队列#include <stdio.h> #include "SeqQue.h" // 循环队列的基本运算 /* const int maxsize = 20; typedef struct cycque { int data[maxsize]; int front, rear; }CycQue; */ // 1....
  • 队列---循环队列链队列比较

    千次阅读 2015-10-21 23:11:45
    对于循环队列链队列的比较,可以从两方面来考虑:1、从时间上,其实它们的基本操作都是常数时间,即都为0(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请释放结点也会存在一些...
  • 本文根据《大话数据结构》一书,实现了Java版的循环队列链队列。 队列:只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 1.循环队列  队列的顺序储存结构:用数组存储队列,引入front指针...
  • 普通队列,循环队列以及链队列的相关操作
  • 目录队列结构的定义属性队列结构的抽象数据类型顺序队列循环队列链队列 队列结构的定义属性 定义:队列是一种与线性表相似的线性结构。但仅允许在表的一端进行插入,而在表的另一端进行删除。 队列结构的几个...
  • 链队列:为操作方便,给链队列添加一个头结点 队列的链式存储结构: typedef struct Qnode{ int data; struct Qnode *next; }Qnode, *queueptr; typedef struct { queueptr front; 队头指针 queueptr ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 128,283
精华内容 51,313
关键字:

循环队列和链队列的区别