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

    千次阅读 2014-06-05 16:31:35
    1. 一循环队列,队头指针front,队尾指针rear,循环队列长度N,其队内有效长度_______ 2.
    1.   一循环队列,队头指针为front,队尾指针为rear,循环队列长度为N,其队内有效长度为_______

    2.   在一个容量为25的循环队列中,若头指针front=16,尾指针rear=9,则该循环队列中共有元素是_18__
            
    循环队列头指针为front,队列尾指针为rear,队列容量为M,则元素个数为(rear-front+M)%M

    循环队列满时,数组中还有一个空的单元。如图4-12-8所示,我们认为,队列已经满了,也就是说,我们不允许出现4-12-7的右图情况出现。

     

    队列满的条件是:

    (rear+1)%QueueSize == front

    通用的计算队列长度的公式为:

    (rear - front+ QueueSize)%QueueSize



    为了解决顺序队列中的"假溢出"问题,需要把数组想象为一个首尾相接的环,称这种数组为"循环数组",存储在其中的队列成为"循环队列"。

    解决队满、队空的判断问题有3种方法:


    ①设置一个布尔变量以区别队满还是队空。


    ②浪费一个元素的空间,用于区别队满还是队空。


    ③是用一个计数器记录队列中的元素个数(即队列长度)。


    在使用中,大都采用第②种方法,即队头、队尾指针中有一个指向元素,而另一个指向空闲元素。

    通常约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示在一维数组中的当前位置的前一个位置。这种顺序队说明如下:

    ①队头指针的引用为q->front,队尾指针的引用为q->rear。(q 为队列名)

    ②初始时,设置q->front=q->rear=0。

    ③入队操作:在队列未满时,队尾指针先加1(要取模),再送值到队尾指针指向的空闲元素。

    ④出队操作:在队列非空时,队头指针先加1(要取模),再从队头指针指向的队头元素处取值。

    ⑤队空的条件:q->front=q->rear;队满的条件:q->front=(q->rear+1)% QueueSize。

    ⑥队列长度为(q->rear+QueueSiz-q->front)% QueueSize。

    在循环队列的操作时应注意,队头指针、队尾指针加1时,都要取模,以保持其值不出界。

     

    在循环队列上实现的基本运算:

    ①初始化InitQueue(q)。

           void InitQueue(qnode*&q)  

    {q=(qnode*)malloc(sizeof(snode));  ∥指针初始化

      q->rear=q->front=0;

     } 

    ②判定队列是否为空Emptyq(q)。

           int Emptyq(snode*q) 

     {if(q->rear=q->front)  

    return 1;  

    else return 0; 


    ③入队列EnQueue(q,x)。

      int EnQueue(qnode*q,ElemType x)

     {if((q->rear+1)%QueueSize==q->front)    ∥队满 

     return 0; 

     q->rear=(q->rear+1)%QueueSize;        ∥队尾指针进1

      q->data[q->rear]=x;  

    return 1;  

    } } 

    ④出队列OutQueue(qnode*q,ElemType x)。

    int OutQueue(qnode*q,ElemType x)  

    {if(q->rear=q->front) 

     return 0; 

     q->front=(q->front+1)%QueueSize;      ∥队头指针进1

      x=q->data[q->front];

      return 1;  }  } 


    ⑤取队头元素GetHead(q,x)。

    int GetHead(qnode*q,ElemType &x) 

     {if(q->rear=q->front)

      return 0;

      x=q->data[(q->front+1)%QueueSize]; 

     return 1;  }  } 

    双端队列

    双端队列(DeQue)是限定插入删除操作在表的两端进行的线性表。这两端分别叫做端点1和端点2。在实际使用中,可以有输出受限的双端队列,即一个端点允许插入和删除,另一个端点只允许插入的双端队列和输入受限的双端队列,即一个端点允许插入和删除,另一个端点只允许删除的双端队列。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻接的栈了。




    展开全文
  • 数据结构之循环队列

    2018-05-29 22:56:06
    循环队列的基本操作实现1.循环队列的特点:

    懒癌患者敲打敲打

    循环队列的基本操作实现

    1.构造循环队列原因:队列初始化时,令front=rear=0,每当插入一个元素时,“尾指针加1”;

    删除一个元素时,“头指针加1”(注意指针都是加一)。

    因此,在非空队列中,头指针始终指向队列的头元素,二尾指针始终指向队列的尾元素。

    当删除一定量的元素后,队首则放空,而队尾若到达了边界值,则无法继续入队,这种情况下,造成了空间的浪费。

    所以一个巧妙的方法就是,构造一个循环队列,充分利用空间。

    2.循环队列判空、满的解决:

    由于队列的判空或满的情况冲突,因此采用以下两种方法来解决这种问题:

    (1)另外设置一个标志位以区别队列是“空”还是“满”;

    (2)少用一个元素空间,约定“当队列头指针在队列尾指针的下一位(指环状的下一个位置)”上作为队列满“满”的标志。 

    即当队列是空的时候 满足条件Q.front==Q.rear;当队列满的时候满足条件(Q.rear+1)%MAXSIZE == Q.front。MAXSIZE指

    代队列的最大长度。

    3.队列当前长度的获取:(Q.rear-Q.front+MAXSIZE)%MAXSIZE

    4.循环基本操作队列实现(C语言)

    #include<iostream>
    #include<cstdlib>
    using namespace std;
    #define MaxLength 100
    typedef int Elemtype;
    typedef struct {
        Elemtype *base;//初始化的动态分配存储空间
        int front;//头指针,若队列不空,则指向队列的头元素
        int rear;//尾指针,若队列不空,指向队尾元素的下一个位置
    }SqQueue;

    /*循环队列基本操作的实现*/

    //1.初始化,构造一个空队列
    int init(SqQueue &Q){
        Q.base = (Elemtype *)malloc(MaxLength*sizeof(Elemtype));//申请内存空间,其类型为Elemtype
        if(!Q.base) exit(0);
        Q.front = Q.rear = 0; //初始化
        return 1;
    }

    //2.求循环队列的长度
    int length(SqQueue &Q){
        return (Q.rear-Q.front + MaxLength)%MaxLength;
    }

    //3.插入一个元素
    int insertRear(SqQueue &Q,Elemtype e){
        if((Q.rear+1)%MaxLength == MaxLength){
            cout<<"队列已满";
            return 0;
        }
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear+1)%MaxLength;//队尾指针进1
        return 1;
    }

    //4、删除一个元素
    int deleteFront(SqQueue &Q,Elemtype &e){
        if(Q.front == Q.rear){
            cout<<"队列为空"<<endl;
            return 0;
        }
        e = Q.base[Q.front]; //选取队首元素,用e返回其地址
        cout<<e<<" ";
        Q.front=(Q.front+1)%MaxLength;
        return 1;
    }

    int main(){
        SqQueue Q;
        init(Q);
        int i,n;
        Elemtype e;
        
        cout<<"请输入队列的元素(小于0则结束):"<<endl;
        while(1){
            cin>>e;
            if(e<0)break;
            cout<<"输入下一个元素:"<<endl;
            insertRear(Q,e);
        }
        
        int len = length(Q);
        cout<<"删除所有元素(列出队列的所有元素)"<<endl;
        for(int i=0;i<len;i++){
            deleteFront(Q,e);
        }
        
        //在执行一次删除,出现异常
        deleteFront(Q,e);
        return 0;
    }

    展开全文
  • C++ 顺序队列与循环队列

    千次阅读 2016-04-03 23:24:16
    很好理解,队列就是把数据排成队,先到的排在前面,后到的排在后面,走的时候,在前面的先出去。(不许插队!) 先是顺序队列,也就是基本的排成一队。 实现如下:#include #include using namespace std; class...

    很好理解,队列就是把数据排成队,先到的排在前面,后到的排在后面,走的时候,在前面的先出去。(不许插队!)
    先是顺序队列,也就是基本的排成一队。
    实现如下:

    #include <iostream>
    #include <cassert>
    using namespace std;
    class Queue {
    private:                   //记录了队列的数据,数据的队首(标记),队尾(标记),队列的长度
        int *data;
        int head, tail, length;
    public:
        Queue(int length_input) {                                     
            data = new int[length_input];
            length = length_input;
            head = 0;
            tail = -1;
        }
        ~Queue() {
            delete[] data;
        }
        void push(int element) {                       //后来的数据会排在队列的末尾
            if (tail + 1 < length) {
                tail++;
                data[tail] = element;
            }
        }
        void output() {                                 //遍历队列
            for (int i = head; i <= tail; i++) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
        int front(){                                          //返回队首的数据
            assert(head <= tail);                 //包含在头文件里<cassert> 作用是:判断条件是否满足,true就继续执行,false就会中断(就是简化下 )
            return data[head];
        } 
        void pop(){                                  //出队,排在前面的先出队
            assert(head <= tail);
            head++;
        }
    };
    int main() {
        Queue queue(100);
        for (int i = 1; i <= 10; i++) {
            queue.push(i);
        }
        queue.output();
        cout<<queue.front()<<endl;
        queue.pop();
        queue.output();
        return 0;
    }

    ———————————————————–华丽的分割线————————————————————————–

    这种队列有个隐含的BUG,如果我不停的入队出队,就会造成满队列(假溢出)
    详细解释下,每当我将一个新元素入队列, 就会把这个数据排到队尾,tail会加1,每次出队,队首的元素会出去,head就会+1(移到下个位置),不停的出入,tail会增长到length,head队首标志也会增长到length,然而实际上队列里并没有数据
    所以,有循环队列来解决这种情况。
    原理:引入计数器count,每次增加一个元素对count+1,出队对count-1,tail增长到大于length时便对length取模操作,这样再次回到队列首,head也如此,这样就可以反复入队出队,直到count达到length上限

    实现如下:

    #include <iostream>
    #include <cassert>
    using namespace std;
    class Queue {
    private:
        int *data;
        int head, tail, length, count;
    public:
        Queue(int length_input) {
            data = new int[length_input];
            length = length_input;
            head = 0;
            tail = -1;
            count = 0;
        }
        ~Queue() {
            delete[] data;
        }
        bool push(int element) {
            if (count < length) {
                tail = (tail + 1) % length;
                data[tail] = element;
                count++;
                return true;
            } else {
                return false;
            }
        }
        void output() {
            for (int i = head; i != tail + 1; i = (i + 1) % length) {
                cout << data[i] << " ";
            }
            cout << endl;
        }
        int front() {
            assert(count > 0);
            return data[head];
        }
        void pop() {
            assert(count >0);
            head = (head + 1) % length;
            count--;
        }
    };
    int main() {
        Queue queue(100); 
        for (int i = 1; i <= 10; i++) {
            queue.push(i);
        }
        queue.output();
        cout << queue.front() << endl;
        queue.pop();    
        queue.output();
        return 0;
    } 
    展开全文
  • 本篇章主要介绍队列及循环队列,并用Python实现循环队列的基本操作。

    前言

      本篇章主要介绍队列及循环队列,并用Python实现循环队列的基本操作。

    1. 队列

      队列 ( Q u e u e ) (Queue) (Queue),简称队,也是一种操作受限的线性表,只允许在表的一端(队首)进行插入,另一端(队尾)进行删除,与栈正相反,队列是先进先出 ( F i r s t (First (First I n In In F i r s t First First O u t , F I F O ) Out,FIFO) Out,FIFO)

    在这里插入图片描述
      队列有两个指针,队首指针front指向队首元素,队尾指针fear指向队尾元素。

      入队操作:先将值送到队尾元素,然后队尾指针加1。

      出队操作:先取队首元素,然后队首指针加1。

      队空条件 f r o n t = = r e a r = = 0 front==rear==0 front==rear==0

      队满条件:╰( ´・ω・)つ──☆✿✿✿ f r o n t = = r e a r front==rear front==rear

      队列长度 r e a r − f r o n t rear-front rearfront

      很明显,上面的队满条件不合适,比如下面这种情况, a 1 , a 2 , a 3 a_1,a_2,a_3 a1,a2,a3已经出队,这时 f r o n t = r e a r front=rear front=rear满足队满条件,但是队列并没有满,出现了“假溢出”的情况,所以我们引入了循环队列来解决这一问题。

    在这里插入图片描述

    2. 循环队列

      循环队列在逻辑上可以将其视为一个环,当队首指针 f r o n t = M a x S i z e − 1 front=MaxSize-1 front=MaxSize1后,再前进一个位置就自动到0,即取余运算。

      队空条件 f r o n t = = r e a r = = 0 front==rear==0 front==rear==0

      队满条件 ( r e a r + 1 ) % M a x S i z e = = f r o n t (rear+1)\%MaxSize==front (rear+1)%MaxSize==front

      队列长度 ( r e a r − f r o n t + M a x S i z e ) % M a x S i z e (rear-front+MaxSize)\%MaxSize (rearfront+MaxSize)%MaxSize

      队首指针进1 f r o n t = ( f r o n t + 1 ) % M a x S i z e front=(front+1)\%MaxSize front=(front+1)%MaxSize

      队尾指针进1 r e a r = ( r e a r + 1 ) % M a x S i z e rear=(rear+1)\%MaxSize rear=(rear+1)%MaxSize

      出队入队时,指针都按顺时针加1。

    在这里插入图片描述

    3. 基本操作

    操作名称操作说明
    CreateCircularSequenceQueue(val_list)创建循环队列
    IsEmpty()判断循环队列是否为空
    LengthQueue()返回循环队列的长度
    Traverse()打印出循环队列里的数据元素
    EnQueue(data)入队
    DeQueue()出队
    GetHead()取队首元素

    4. 代码实现

    class CircularSequenceQueue(object):
        def __init__(self):
            self.MaxQuenceSize = 10
            self.Q = [None for i in range(self.MaxQuenceSize)]
            self.front = 0
            self.rear = 0
    
        def CreateCircularSequenceQueue(self, val_list):
            for val in val_list:
                self.EnQueue(val)
    
        def IsEmpty(self):
            if self.front == self.rear:
                return True
            else:
                return False
    
        def LengthQueue(self):
            return (self.rear - self.front + self.MaxQuenceSize) % self.MaxQuenceSize
    
        def EnQueue(self, e):
            if (self.rear + 1) % self.MaxQuenceSize == self.front:
                print('队已满!')
                exit()
            else:
                self.Q[self.rear] = e
                self.rear = (self.rear + 1) % self.MaxQuenceSize
    
        def DeQueue(self):
            if self.IsEmpty():
                print('队为空!')
                exit()
            else:
                e = self.Q[self.front]
                self.front = (self.front + 1) % self.MaxQuenceSize
                return e
    
        def Traverse(self):
            for index in range(self.LengthQueue()):
                print(self.Q[index], end=' ')
            print('')
    
        def GetHead(self):
            return self.Q[self.front]
    

      测试代码如下:

    if __name__ == '__main__':
        q1 = CircularSequenceQueue()
        q1.CreateCircularSequenceQueue([1, 3, 5, 7, 9])
        print('队列里的元素为: ', end='')
        q1.Traverse()
        print('队列的长度为: %d' % q1.LengthQueue())
        print('队首元素为: %d' % q1.GetHead())
        print('出队: ', end='')
        for i in range(q1.LengthQueue()):
            print(q1.DeQueue(), end=' ')
    

      运行结果如下:

    在这里插入图片描述

    展开全文
  • 09.循环队列与链队列

    千次阅读 2015-01-09 22:14:15
    一、队列与循环队列 1.队列 (1)队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。队列是一种先进先出(Fiirst In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端...
  • 数据结构 第7讲 循环队列

    千次阅读 多人点赞 2018-04-09 11:02:31
    数据结构 第7讲 循环队列过了一段时间,小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题,小张跑了无数次居委会,终于将挡在胡同口的建筑清除,这样住在胡同尽头的小张,就可以早早回家停...
  • 【数据结构】 深度剖析循环队列

    千次阅读 2020-03-04 21:12:11
    写在前面 ...文章目录一、问题引入二、问题初步分析三、循环队列实现【第一版】四、第一版本分析优化五、循环队列实现【第二版】六、总结 一、问题引入 某厂笔试题目:请基于学习过的队列知识,...
  • 利用循环队列打印杨辉三角形
  • 循环队列的一些问题总结,入队、出队操作

    千次阅读 多人点赞 2019-02-02 12:48:39
    1.在队列的顺序存储方式里,为了避免存储空间的“假溢出”,充分利用存储空间,我们用了一种实现方式,即循环队列。 (1).图中有两个指针(只是两个整型变量,因为在这里有指示作用,所以理解指针) front、rear,...
  • 条件队列

    千次阅读 2016-04-20 00:02:40
    这一个月,从C#转到java了,去年9...条件队列装入的数据项是等待先验条件成立而被挂起的线程。 我们想在得到的消息到来时,这个消息能立即得到处理,在大多数时候,我们的处理方式是在条件满足时,让这个线程做自旋
  • 顺序队列的基本算法及循环队列

    千次阅读 2011-12-26 01:02:01
    队头指针front指出实际队头元素所在位置的前一个位置,而队尾指针rear指出实际队尾元素所在的位置,初始时,队列为空有front = rear = -1, 测试一个队列是否空的条件是front = rear. 顺序队列的基本算法如下: /...
  • #include using namespace std; class SeqQueue{ private: int* elements; //存放队列元素的数组 int rear,front; //队尾指针和对头指针 int maxSize; //队列可容纳的最大元素个数 public: SeqQueue(int s
  • 数据结构-数组循环队列 ​ 作者:哇塞大嘴好帥 ​ 作者:哇塞大嘴好帥(哇塞大嘴好帅) ​ 思路分析: ​ foot永远指向序列尾 ​ head永远指向队列头部的后一位 ​ 当队列满的时候,条件是: (head + 1) % 数组容量...
  • 队列是另一种经典数据结构,也是有两种,一是静态队列,即数组实现的循环队列,二是用链表实现的动态队列,今天我写的是循环队列,下面我就详细分析一下循环队列我认为不太好理解的几个点 第零,循环队列的构成,用...
  • 操作系统课上一个作业, 要求是用消息队列来实现某些功能 已知消息队列的特性 : 可以多个进程接受相同消息, 可知队列中的消息是不会消失的 目前所想的是用3个进程, 每个进程都有2个线程 ...而不是持续循环读取
  • 顺序栈&链栈&循环队列&链队基本操作的实现

    千次阅读 多人点赞 2020-02-24 18:07:43
    队列的建立、取队中元素、入队、出队、循环队列中入队、出队操作 四、主要仪器设备及耗材 硬件:计算机一台 软件:VC++ 6.0,MSDN2003或者以上版本 五、实验步骤 分析问题 写出算法 编制程序 上机调试 分析结果 ...
  • 关于循环队列的体会

    千次阅读 2014-10-11 00:05:32
    第二种写法可以只设一个尾指针,而这种写法又可以分为 两种,一种是写成带头结点的循环链表来表示队列(作业第六题),第二种是写成只有尾指针,但满足循环队列结构体的形式,即存在记录队列长度的结构体成员(作业...
  • c++ 数据结构 双端(循环队列

    千次阅读 2016-12-11 20:28:44
    双端队列:相比循环队列来说,既可以取队头元素,又可以取队尾元素;可以从队头出队,也可以从队头进队;可以从队尾进队,也可以从队尾出队。 所以本文用继承循环队列的方式来实现双端队列: 1.循环队列(SeqQueue.h...
  • 上文说过普通队列的出队操作的时间复杂度O(n)(因为要整体移动元素),而循环队列就可以完美解决这个问题,使得出队与入队操作均O(1)的时间复杂度,怎么样,很厉害吧~让我们一起来探究一下循环队列究竟何物...
  • Go语言 大话数据结构——循环队列

    千次阅读 2018-08-20 08:39:44
    队列也是一种线性表,只不过它是操作受限的线性表,只能在两端操作,先进先出(First In First Out,FIFO)。 进的一端称为队尾(rear),出的一端称为队头(front)。队列可以用顺序存储,也可以用链式存储。 1...
  • C#实现循环顺序队列队列

    千次阅读 2010-03-08 15:04:00
    队列同栈相对,前者先进先出(First In First In)。 顺序队里中,使用数组存储数据,基本原理同顺序线性表和顺序栈。由于使用数组,所以必须事先定义数组的最大容量MaxSize,使用front表示队头位置(最先入元素...
  • 队列

    千次阅读 2019-09-12 20:03:36
    队列 定义:队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 队列(Queue)是一种先进先出(First In First Out)的线性表,简称FIFO。 允许插入的一端叫做队尾,删除的一端叫做队头。 同样是...
  • 深入分析Node.js事件循环与消息队列

    千次阅读 多人点赞 2018-08-03 00:05:44
    Nodejs 将消息循环又细分 6 个阶段(官方叫做 Phase), 每个阶段都会有一个类似于队列的结构, 存储着该阶段需要处理的回调函数. 我们来看一下这 6 个 Phase 的作用,这六个阶段的核心代码如下: int uv_run(uv_...
  • 状态依赖性的管理2.1 什么是状态依赖性2.1.1 定义2.1.2 单线程和多线程的状态依赖性2.2 内置条件队列2.3 前提条件失败传递给调用者2.4 使用轮询与休眠解决状态依赖性问题2.5 使用内置条件队列解决状态依赖性问题2.6...
  • 如果我们使用数组来实现队列,当队列尾部没有空闲空间时,即便整个队列有空闲空间,新数据也将无法入队。除非采用“数据搬移”的方法,将队尾的数据全部搬移到队列头部,这样队列尾巴才有空间可以进行入队操作。 ...
  • [java并发]深入浅出条件队列-wait、notify、notifyall

    千次阅读 多人点赞 2020-12-30 16:04:01
    java的内置的条件队列存在一些缺陷,每个内置锁(基于synchronize块)都只能有一个关联的条件队列,因此可能存在多个线程因不同的条件谓词不满足而在同一个条件队列上。这个特性很可能就会导致"通知丢失"(不使用notify...
  • 本文分析一下JDK是如何实现Condition条件队列的,对你今后的使用或许有帮助。如果你觉得分析源码太累,看不懂,可以通过阅读本文以大致了解java显式锁的实现,保证你面试够用了。 约定: 本文AQS均指java.util....
  • 等待队列

    千次阅读 2014-10-11 12:18:32
     在Linux内核中等待队列有很多...因此,等待队列表示一组睡眠的进程,当某一条件为真时,由内核唤醒它们。 等待队列循环链表实现,其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头(wait que
  • Condition条件队列是为了实现线程之间相互等待的问题。注意Condition对象只能在独占锁中才能使用。 举个例子:有两个线程,生产者线程,消费者线程。 当消费者线程消费产品时,发现没有产品,这时它就要等待,让生产...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,963
精华内容 32,385
关键字:

循环队列满足的条件为