数据结构:队列的顺序存储结构(循环队列)

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头。我们在《栈的顺序存储结构》中发现,栈操作的top指针在Push时增大而在Pop时减小,栈空间是可以重复利用的,而队列的front、rear指针都在一直增大,虽然前面的元素已经出队了,但它所占的存储空间却不能重复利用。但大多数程序并不是这样使用队列的,一般情况下出队的元素就不再有保存价值了,这些元素的存储空间应该回收利用,由此想到把队列改造成环形队列(Circular Queue):把queue数组想像成一个圈,front和rear指针仍然是一直增大的,当指到数组末尾时就自动回到数组开头,就像两个人围着操场赛跑,沿着它们跑的方向看,从front到rear之间是队列的有效元素,从rear到front之间是空的存储位置,如果front追上rear就表示队列空了,如果rear追上front就表示队列的存储空间满了。故一般我们将其实现为循环队列,当出队列时就不需要全部进行移动,只需要修改队头指针,也可以解决“假溢出”的问题。

示例程序:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 20

typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int front; /* 头指针 */
    int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    int count; //元素个数
} SqQueue;

bool InitQueue(SqQueue &Sq)
{
    cout << "Init Queue ..." << endl;
    Sq.front = 0;
    Sq.rear = 0;
    Sq.count = 0;
    return true;
}

bool ClearQueue(SqQueue &Sq)
{
    cout << "Clear Queue ..." << endl;
    Sq.front = 0;
    Sq.rear = 0;
    Sq.count = 0;
    return true;
}

bool QueueEmpty(SqQueue &Sq)
{
    return Sq.count == 0; /* 队列空的标志 */
}

bool QueueFull(SqQueue &Sq)
{
    return Sq.count == MAXSIZE;
}

int QueueLength(SqQueue &Sq)
{
    if (QueueFull(Sq))
        return MAXSIZE;

    /* 队列的当前长度 */
    return (Sq.rear - Sq.front + MAXSIZE) % MAXSIZE;
}
/* 返回头元素 */
bool GetHead(SqQueue &Sq, ElemType *pe)
{
    if (QueueEmpty(Sq))
        return false;
    else
    {
        *pe = Sq.data[Sq.front];
        cout << "Get Head Item " << *pe << endl;
        return true;
    }
}

bool EnQueue(SqQueue &Sq, ElemType Elem)
{
    /* 队列满 */
    if (QueueLength(Sq) == MAXSIZE)
        return false;
    cout << "EnQueue Item " << Elem << endl;
    Sq.data[Sq.rear] = Elem;/* 将元素赋值给队尾 */
    Sq.rear = (Sq.rear + 1) % MAXSIZE;/* rear指针向后移一位置, */
    /* 若到最后则转到数组头部 */
    Sq.count++;
    return true;
}

bool DeQueue(SqQueue &Sq, ElemType *pe)
{
    if (QueueEmpty(Sq))
        return false;
    *pe = Sq.data[Sq.front];/* 将队头元素赋值给*pe */
    cout << "DeQueue Item " << *pe << endl;
    Sq.front = (Sq.front + 1) % MAXSIZE;/* front指针向后移一位置, */
    /* 若到最后则转到数组头部 */

    Sq.count--;
    return true;
}

bool QueueTraverse(SqQueue &Sq)
{
    if (QueueEmpty(Sq))
    {
        cout << "Queue is empty" << endl;
        return false;
    }

    cout << "Queue Traverse ..." << endl;
    for (int i = 0;  i < Sq.count; i++)
        cout << Sq.data[i + Sq.front] << ' ';
    cout << endl;
    return true;
}

int main(void)
{
    SqQueue Sq;
    InitQueue(Sq);
    for (int i = 0; i < 20; i++)
        EnQueue(Sq, i);
    QueueTraverse(Sq);
    if (!QueueEmpty(Sq))
        cout << "Queue Length: " << QueueLength(Sq) << endl;
    int result;
    GetHead(Sq, &result);
    DeQueue(Sq, &result);
    DeQueue(Sq, &result);
    if (!QueueEmpty(Sq))
        cout << "Queue Length: " << QueueLength(Sq) << endl;
    QueueTraverse(Sq);

    return 0;
}

输出为:

单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列也面临着数组可能溢出的问题。

注:上述用 Use a fill count to distinguish the two cases. 的方法实现循环队列。常用的还有 Always keep one slot open. 也就是多申请一个不用的元素

位置,那么判断满时  (cb->end + 1) % cb->size == cb->start;  判断空时 cb->end == cb->start;

参考:

《大话数据结构》

《Data Structures》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

微店2016技术岗面试题

第一部分 简答(请选择一个题目解答) 1.请写出C/C++ 语言中的相关问题。 A. 请简述C/C++ 语言中找空间和对空间的主要区别。 B. C++处理异常可...

33612
来自专栏二次元

什么是递归?

一上来你肯定觉得读这句话好绕,好吃力。 其实你用递归来读就很简单了: 递归要有一个终点(小鲤鱼) 当递归尚未达到终点的时候,函数会反复调用自己。 ...

810
来自专栏LinkedBear的个人空间

设计模式笔记(二)——模板方法模式 原

因为学生3没有抄完(而且抄的题目还写错了。。。),以至于之后要背书的时候怎么也背不对了。。。

612
来自专栏林德熙的博客

VisualStduio 打断点调试和不打断点调试有什么区别 随机数

最近小伙伴告诉我,他的代码在打断点的时候,运行到断点,之后就可以运行。如果没有断点,他的代码就无法运行,经过了一段时间的研究才发现,原来打断点和不打断点是有一些...

372
来自专栏吉浦迅科技

DAY37:阅读不同存储器的修饰符

1074
来自专栏数据小魔方

R语言学习笔记——R语言面向对象编程系列2

最近在看任坤大神的新作——《R语言编程指南》,其中对于编程语言中非常流行的面向对象编程范式(OOP)在R语言中的实现进行了非常详尽的讲解,强烈推荐各位有志于进阶...

27612
来自专栏达摩兵的技术空间

文件拓展名、周几的写法优化

本文主要是练习如何获取文件拓展名的练习。之前有分享过一个方案,但是早晨有复习字符串语法中有涉及到一个方法交lastIndexOf(),所以想就这个问题应该有个更...

561
来自专栏数据小魔方

左手用R右手Python系列——面向对象编程基础

面向对象编程是程序设计中一种重要且高效的编程规范,它区别于常见的面向过程编程。在R语言以及Python的程序包开发过程中,大量使用了面向对象的编程范式。 百度...

41712
来自专栏take time, save time

你所能用到的数据结构(六)

八、数据结构不一定很枯燥   正如我现在实习的公司的一个同事说的那样,数据结构是一本催眠的书,我想对于大多数人应该是这样的,当然对我也是,看着一大堆的算法,结...

3165
来自专栏菩提树下的杨过

scala 学习笔记(05) OOP(中)灵活的trait

trait -- 不仅仅只是接口! 接上回继续,scala是一个非常有想法的语言,从接口的设计上就可以发现它的与众不同。scala中与java的接口最接近的概念...

17410

扫码关注云+社区