精华内容
下载资源
问答
  • 循环队列判断队满和队空的条件

    千次阅读 2019-10-15 15:34:21
    循环队列判断队满和队空的条件 队满:front=(rear+1)%size ; 队空:front = rear&&

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

    队满:front=(rear+1)%size ;
    队空:front = rear&&
    在这里插入图片描述
    图片上的信息来自王红梅教授版数据结构第二版

    展开全文
  • 循环队列队列有着先入先出的特性。但是对于队列如果删除头...对照着图很容易理解:对于原来队列里的操作自然有不同的地方:判断满循环队列不再是rear=front 而是改成(rear-front+maxn)%maxn。入队操作: dat...

    循环队列

    队列有着先入先出的特性。但是对于队列如果删除队头以后剩下的空间将不会被释放,又由于队列只能由队尾插入这就导致被删除部分的空间被浪费。解决这个问题就是循环队列。循环队列顾名思义就是将队列串起来形成一个类似与环的结构。对照着图很容易理解:

    对于原来队列里的操作自然有不同的地方:

    1. 判断满:循环队列的满不再是rear=front 而是改成(rear-front+maxn)%maxn。
    2. 入队操作: data[rear] = x; rear = (rear+1)%maxn;

    总体思想就是不让rear和front的值超过maxn的大小。于是就在rear和front自增时候模maxn,其实就是Ring Buffer。

    795f62539f3d186e5148f75a729e7456.png

    循环队列示意图

    设计思想

    空队时指针(下标)front和rear在一起都指向队前方,当有元素进队,则rear后移;有元素出队,则front后移,最后,开始时分配给队的前端不再被利用。

    为了充分利用队列,顺序队列总是做成一个逻辑上的循环队列。

    b055067a7d83bbd722791c43d03cea9c.png

    循环队列设计思想

    注意:空队时rear等于front,满队时必须空一个位置。

    代码实现

    #include using namespace std;template class cycleQueue{ private:  unsigned int m_size; int m_front; int m_rear; T* m_data; public: cycleQueue(unsigned size) :m_size(size), m_front(0), m_rear(0) {  m_data = new T[size]; }  ~cycleQueue() {  delete [] m_data; }  bool isEmpty() {  return m_front == m_rear; }  bool isFull()  {  return m_front == (m_rear + 1)%m_size; }  void push(T ele)throw(bad_exception) { if(isFull()) { throw bad_exception(); } m_data[m_rear] = ele; m_rear = (m_rear + 1)%m_size; } T pop() throw(bad_exception) { if(isEmpty()) { throw bad_exception(); } T tmp = m_data[m_front]; m_front = (m_front + 1)%m_size; return tmp; }};int main(){ cycleQueue q(5); q.push(1); q.push(2); q.push(3); q.push(4); for (int i = 0; i < 4 ; i++) cout << q.pop() << endl; q.push(5); q.push(5); q.push(5); cout << q.pop() << endl; cout << q.pop() << endl; cout << q.pop() << endl; cout << q.pop() << endl; return 0;}
    展开全文
  • 队列的性质队列满足的基本性质为先进先出,后进后出。eg:生活中类似于排队打饭一样,先排队的先打饭。...图解:如上图可以得出:判断队列满的方法就是队尾加1除以队长跟头位置是否相等。即(S->rear+1)%Siz...

    队列的性质

    队列满足的基本性质为先进先出,后进后出。

    eg:生活中类似于排队打饭一样,先排队的先打饭。

    一,关于顺序栈的结构体表示

    结构体定义

    struct Node{ int data[MaxSize]; //存放队列的数组 int front; //队尾 int rear; //队头};

    图解:

    a7940519a518e91d8167b71e05c06b6d.png
    873ce7409b17b8cd5383c7913046671d.gif

    如上图可以得出:

    • 判断队列满的方法就是队尾加1除以队长跟队头位置是否相等。即(S->rear+1)%Size==S->front
    • 判断队列为空的方法就是队头跟队尾位置是否相等。即S->front==S->rear
    • 这里可以当作,队列满是看队头是否能追上队尾
    • 队列空,是看队尾是否能追上队头
    • 此处将n-1就定义为满队列的原因是,若全部都存入数据,则S->front与S->rear相等,与空栈情况一样。

    循环队列的定义

    Node *Init(){Node *S = new Node;S->front = S->rear = 0;return S;}
    873ce7409b17b8cd5383c7913046671d.gif

    即简单初始化队头队尾,都指向队列底就行,也就是赋值为0.


    入队

    void Enter(Node &S){if ((S.rear + 1) % MaxSize != S.front)    //判断是否为满队列{cout << "输入要进入队列的值:";cin >> *(S.data + S.rear);S.rear = (S.rear + 1) % MaxSize;}else{cout << "队列已满" << endl;}}
    873ce7409b17b8cd5383c7913046671d.gif

    先判断是否为满队列,若队列已满,则不能继续存数据


    出队列

    void Delete(Node &S){if (S.front != S.rear)                  //队列不为空{S.front = (S.front + 1) % MaxSize;}else{cout << "队列为空" << endl;}}
    873ce7409b17b8cd5383c7913046671d.gif

    队列的性质是先进先出,所以先判断队列是否为空,若不为空,则先出先进的,即存放在队尾的数据


    显示先入队列的数据

    void Show(Node *S){cout << "队头元素为:";cout << *(S->data + S->front) << endl;}
    873ce7409b17b8cd5383c7913046671d.gif

    代码:

    #includeusing namespace std;#define MaxSize 20struct Node{int data[MaxSize];int front;int rear;};Node *Init(){Node *S = new Node;S->front = S->rear = 0;return S;}void Enter(Node &S){if ((S.rear + 1) % MaxSize != S.front){cout << "输入要进入队列的值:";cin >> *(S.data + S.rear);S.rear = (S.rear + 1) % MaxSize;}else{cout << "队列已满" << endl;}}void Delete(Node &S){if (S.front != S.rear)                  //队列不为空{S.front = (S.front + 1) % MaxSize;}else{cout << "队列为空" << endl;}}void Show(Node *S){cout << "队头元素为:";cout << *(S->data + S->front) << endl;}int main(){Node *S = Init();Enter(*S);Enter(*S);Enter(*S);Show(S);Delete(*S);Show(S);system("pause");}
    873ce7409b17b8cd5383c7913046671d.gif
    展开全文
  • ---- 网易云热评一、队列1、queue.c内容#include "02queue.h"//队列的初始化函数void queue_init(queue *p_queue/*指向调用函数提供的代表队列的结构体存储区*/) { //初始化要保证队列里没有数字,也就是...

    孤独是什么,洗了个头,吹了个好看的发型,换了双干净的鞋子,穿了件帅气的衣服,去超市买了一包烟和一瓶水然后就回家了。。。

    ----  网易云热评

    一、队列

    1、queue.c内容

    #include "02queue.h"//队列的初始化函数void queue_init(queue *p_queue/*指向调用函数提供的代表队列的结构体存储区*/) {    //初始化要保证队列里没有数字,也就是    //head和tail成员变量必须相等    p_queue->head = 0;    p_queue->tail = 0;}//队列的清理函数void queue_deinit(queue *p_queue) {    //清理函数需要把队列里的数字都删除    p_queue->head = 0;    p_queue->tail = 0;}//获得队列里数字个数的函数int /*表示得到的数字个数*/queue_size(const queue *p_queue) {    return p_queue->tail - p_queue->head;}//判断队列是否空的函数int /*返回值为真表示队列空,否则不空*/queue_empty(const queue *p_queue) {    return p_queue->head == p_queue->tail;}//判断队列是否满的函数int /*返回值为真表示队列满,否则不满*/queue_full(const queue *p_queue) {    //只要最后一个存储区被使用过    //就表示队列满了    return p_queue->tail >= SIZE;}//向队列里加入数字的函数int /*返回值为真表示成功加入,否则加入不成功*/queue_push(queue *p_queue, int val/*要加入的数字*/) {    if (p_queue->tail >= SIZE) {        //如果队列已经满了就不能在加入数字了        return 0;    }    p_queue->buf[p_queue->tail] = val;   //把新数字放在数组里以tail做下标的存储区里    p_queue->tail++;    //tail向后移动一步    return 1;}//从队列里获得数字的函数(同时删除数字)int /*返回值为真表示获得数字成功,否则失败*/queue_pop(queue *p_queue, int *p_val/*用来向调用函数传递数字*/) {    if (p_queue->head == p_queue->tail) {        //队列是空的        return 0;    }    *p_val = p_queue->buf[p_queue->head];   //以head做下标的存储区里面就是最前面的数字,把它赋值给整数指针形式参数指向的存储区    p_queue->head++;   //把head向后移动一步,这样下次获得的就是后面的数字(相当于把当前数字删除了)    return 1;}//从队列里获得数字的函数(不会删除数字)int queue_front(const queue *p_queue, int *p_val) {    if (p_queue->head == p_queue->tail) {        //队列空的情况        return 0;    }    *p_val = p_queue->buf[p_queue->head];    return 1;}

    2、queue.h内容

    #ifndef           __QUEUE_H__#define           __QUEUE_H__typedef struct {    int buf[SIZE];    //用来存放队列里的数字.前面的数字记录到小下标的存储区里,后面的数字记录到大下标的存储区里.只要最后一个存储区被使用过就认为队列已经被充满了,即使前面有空着的存储区也不可以使用    int head;         //代表最前面的数字所在的下标.如果队列里没有数字则head应该等于tail    int tail;         //代表下一个数字应该放置的位置下标} queue;   //代表队列的结构体类型//队列的初始化函数void queue_init(queue */*指向调用函数提供的代表队列的结构体存储区*/);//队列的清理函数void queue_deinit(queue *);//获得队列里数字个数的函数int /*表示得到的数字个数*/queue_size(const queue *);//判断队列是否空的函数int /*返回值为真表示队列空,否则不空*/queue_empty(const queue *);//判断队列是否满的函数int /*返回值为真表示队列满,否则不满*/queue_full(const queue *);//向队列里加入数字的函数int /*返回值为真表示成功加入,否则加入不成功*/queue_push(queue *, int /*要加入的数字*/);//从队列里获得数字的函数(同时删除数字)int /*返回值为真表示获得数字成功,否则失败*/queue_pop(queue *, int * /*用来向调用函数传递数字*/);//从队列里获得数字的函数(不会删除数字)int queue_front(const queue *, int *);#endif      //__QUEUE_H__

    3、主函数

    #include #include "queue.h"int main() {    int val = 0;    queue que = {0};    queue_init(&que);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_push(&que, 10);    queue_push(&que, 20);    queue_push(&que, 30);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_front(&que, &val);    printf("最前面的数字是%d\n", val);    queue_pop(&que, &val);    printf("%d ", val);    queue_pop(&que, &val);    printf("%d\n", val);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_push(&que, 40);    queue_push(&que, 50);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    while (1) {        if (!queue_pop(&que, &val)) {            //不能从队列里获得数字了            break;        }        printf("%d ", val);    }    printf("\n");    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_deinit(&que);    return 0;}运行结果:数字个数是0判断空的结果是1判断满的结果是0数字个数是3判断空的结果是0判断满的结果是0最前面的数字是1010 20数字个数是1判断空的结果是0判断满的结果是0数字个数是3判断空的结果是0判断满的结果是030 40 50数字个数是0判断空的结果是1判断满的结果是0

    二、循环队列

    1、loop_queue.c文件内容

    #include "loop_queue.h"//队列的初始化函数void queue_init(queue *p_queue) {    p_queue->tail = 0;    //下一个数字应该放在下标为0的存储区里    p_queue->qty = 0;     //队列里还没有数字}//队列的清理函数void queue_deinit(queue *p_queue) {    p_queue->tail = 0;    p_queue->qty = 0;}//计算第一个数字所在下标的函数int /*得到的下标*/get_head(const queue *p_queue) {    //如果tail是6,qty是3    //使用tail - qty可以得到第一个数字    //的下标    //如果tail是3,qty是6    //使用tail - qty + SIZE可以得到第一个    //数字的下标    int ret = p_queue->tail - p_queue->qty;    if (ret < 0) {        //最前面的数字在最后面数字的后面        ret += SIZE;    }    return ret;}//获得队列里数字个数的函数int queue_size(const queue *p_queue) {    return p_queue->qty;}//判断队列空的函数int queue_empty(const queue *p_queue) {    return !p_queue->qty;}//判断队列满的函数int queue_full(const queue *p_queue) {    return p_queue->qty >= SIZE;}//向队列里加入数字的函数int queue_push(queue *p_queue, int val) {    if (p_queue->qty >= SIZE) {        //队列已经满了        return 0;    }    p_queue->buf[p_queue->tail] = val;    p_queue->tail++;    if (p_queue->tail >= SIZE) {        //当最后一个存储区里已经放好数字后        //应该把tail设置成0,表示后面的        //数字应该从下标为0的存储区        //开始继续存放        p_queue->tail = 0;    }    p_queue->qty++;    //数字个数加一    return 1;}//从队列里获得数字的函数(同时删除数字)int queue_pop(queue *p_queue, int *p_val) {    if (!p_queue->qty) {        //队列是空的        return 0;    }    *p_val = p_queue->buf[get_head(p_queue)];   //首先计算第一个数字所在存储区的下标,然后把这个存储区里的数字传递给调用函数    p_queue->qty--;     //把数字个数减一,这导致最前面数字所在的下标向后移动一步(相当于删除最前面的数字)    return 1;}//从队列里获得数字的函数(不会删除数字)int queue_front(const queue *p_queue, int *p_val) {    if (!p_queue->qty) {        //队列是空的        return 0;    }    *p_val = p_queue->buf[get_head(p_queue)];    return 1;}

    2、loop_queue.h文件内容

    #ifndef          __LOOP_QUEUE_H__#define          __LOOP_QUEUE_H__typedef struct {    int buf[SIZE];    //用来存放队列里的数字.前面的数字存放在小下标的存储区里,后面的数字存放在大下标的存储区里.当最后一个存储区被使用过以后可以把后面的数字存放在下标为0的存储区里(前提条件是下标为0的存储区里没有有效数字)    int qty;          //记录队列里的数字个数    int tail;         //记录下一个数字应该放置的存储区下标} queue;    //代表循环队列的结构体//队列的初始化函数void queue_init(queue *);//队列的清理函数void queue_deinit(queue *);//获得队列里数字个数的函数int queue_size(const queue *);//判断队列空的函数int queue_empty(const queue *);//判断队列满的函数int queue_full(const queue *);//向队列里加入数字的函数int queue_push(queue *, int );//从队列里获得数字的函数(同时删除数字)int queue_pop(queue *, int *);//从队列里获得数字的函数(不会删除数字)int queue_front(const queue *, int *);#endif         //__03LOOP_QUEUE_H__

    3、主函数内容

    #include #include "loop_queue.h"int main() {    int val = 0;    queue que = {0};    queue_init(&que);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_push(&que, 10);    queue_push(&que, 20);    queue_push(&que, 30);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_front(&que, &val);    printf("最前面的数字是%d\n", val);    queue_pop(&que, &val);    printf("%d ", val);    queue_pop(&que, &val);    printf("%d\n", val);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_push(&que, 40);    queue_push(&que, 50);    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    while (1) {        if (!queue_pop(&que, &val)) {            //不能从队列里获得数字了            break;        }        printf("%d ", val);    }    printf("\n");    printf("数字个数是%d\n", queue_size(&que)/*获得队列里的数字个数*/);    printf("判断空的结果是%d\n", queue_empty(&que)/*判断队列是否空*/);    printf("判断满的结果是%d\n", queue_full(&que));/*判断队列是否满*/    queue_deinit(&que);    return 0;}运行结果:数字个数是0判断空的结果是1判断满的结果是0数字个数是3判断空的结果是0判断满的结果是0最前面的数字是1010 20数字个数是1判断空的结果是0判断满的结果是0数字个数是3判断空的结果是0判断满的结果是030 40 50数字个数是0判断空的结果是1判断满的结果是0

    欢迎关注公众号:顺便编点程

    cb6ab5871fc58a5fedb442df31bdc639.png

    f561900bc41c5a4602f78071896a2bdf.png

    展开全文
  • ☝☝☝软件工程考研独家平台撰稿| 康康哥编辑| 丽丽姐本文由懂计算机、软件工程的博士师哥原创双日练:NO.20200922循环队列放在一维数组A[0…M-1]中,end1指向头元素,end2指向队尾元素的后一个位置。假设队列两端...
  • 循环队列判断队满与队空

    万次阅读 多人点赞 2016-04-02 11:16:38
    在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了
  • 生活中随处可见队列,例如食堂打饭,超市买单的时候,我们都会自然而然地排队。那么,在计算机中如何表示这一现象呢?1.什么是队列队列,是一种我们再熟悉不过的模型了,现实中到处可见它的场景,比如,饭堂打饭需要...
  • 在引用循环队列前,我们需要了解队列是如何线性实现的。    (纠错:上图中出队列应该是:x=sq[front++])简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾指针+1,删除元素是头指针-1。但是,我们会...
  • (二) 队列定义和栈相似,队列也是一种特殊的线性表...队列的基本操作和栈相似,对于队列,插入数据只能在队尾进行,删除数据只能在头进行,在队列中插入数据我们叫入队enqueue,删除队列中的数据我们叫出deque...
  • 在引用循环队列前,我们需要了解队列是如何线性实现的。 简单地讲,便是当队列为空时,front = rear = 0,每当插入元素尾指针+1,...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满
  • 环形队列判断队满

    2020-12-28 17:47:49
    在引用循环队列前,我们需要了解队列是如何...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的,可以通过牺牲一个存储空间来实现。 如上图d2所示, 队头
  • 循环队列队满判断

    万次阅读 2018-03-23 21:06:28
    第一种方法是设置一个标志量flag,当front==rear且flag=0时为空,当front==rear且flag=1时列为;第二种方法是我们修改条件,保留一个元素空间,也就是说,数组中还有一个空闲单元时,我们就认为这个队列已经了...
  • front表示队头指针(指向队列内首元素) rear表示队尾指针(指向队列内尾元素的下一个位置) m表示队列的容量 队空:front=rear ...队满:front=(rear+1)%m 队列内元素个数:(rear - front + m) % m ...
  • 循环队列判断满与空

    千次阅读 2013-09-22 00:08:32
    由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”。 注:先进入的为‘头’,后进入的为‘尾’。 解决此...
  • 循环队列设置tag标志域判断队满队空 算法思想: tag等于0的情况下,若因删除导致Q.Rear==Q.Front则为队空 tag等于1的情况下,若因插入导致Q.Rear==Q.Front则为队满 核心代码: //tag等于0的情况下,若因删除...
  • 循环队列判断满空的两种方法(C#)

    千次阅读 2019-10-20 20:06:46
    如果进队元素的速度快于出队元素的速度,队尾指针很快就赶上了队首指针,此时可以看出循环队列队满条件也为 rearfront。怎样区分这两者之间的差别呢? 解决方案: 方法一:把数组的前端和后端连接起来,形成一个...
  • 循环队列判断

    2020-12-21 08:19:33
    在引用循环队列前,我们需要了解...我们可以发现,当循环队列属于上图的d1情况时,是无法判断当前状态是队空还是队满。为了达到判断队列状态的目的,可以通过牺牲一个存储空间来实现。 1.队头指针在队尾指针的下一位置
  • C语言之循环队列判断满与空

    千次阅读 2017-03-23 08:23:54
    由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”。 注:先进入的为‘头’,后进入的为‘尾’。 解决此问题的...
  • 循环队列实现(通过设置标志位tag位判断队满队)
  • 循环队列的队空与队满的条件

    千次阅读 2014-07-19 00:29:15
     因此只凭等式front=rear无法判断队空还是队满。 有两种方法处理上述问题:  (1)另设一个标志位以区别队列是空还是满。  (2)少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 381
精华内容 152
关键字:

循环队列判断队满