数据结构-队列

队列的定义

在很多资料中,队列与往往一同出现,因为它与栈有很多相似的地方。队列是只允许在一端插入另一端删除的线性表,即一种先入先出(FIFO)的结构,队列有顺序对列与循环队列,循环队列主要是为了弥补队列存储空间不足与“假溢出”的问题,所以在实际应用时,往往使用的是循环队列,下面我们从头说下为什么会有循环队列这个东西: 在栈中,我们把数组中的第一个元素作为栈底,因为栈是一种后入先出的顺序,也就是在数组后面push和pop,这不会影响栈内已经存在的元素。但是队列就不行了,队列具有先入先出的性质: 1.如果数组的第一个元素作为队尾,那么每次入队的时间复杂度为O(n); 2.如果数组的第一个元素作为队头,那么每次出队的时间复杂度为O(n); 所以,由于数组与队列的特性,只有一个指针是解决不了了,那就来两个吧。在队列中,front指向队头,rear指向对尾的下一个元素(下一次入队的位置),这样就解决了入队出队都是O(1)的问题:

这个问题解决了,顺序链表的形式也就确定了,那么为什么还会有循环链表?

在这种情况下,rear已经指向数组之外了,但是数组前面明明还有位置,这就是顺序链表的“假溢出”情况,所以为了解决这个问题,会把rear重新指向开头,构成循环队列:

此时,数组的开头既不是队头,也不是对尾,而是front指向的单元。队列为空的条件就是front=rear,但是这样有回产生一个问题,如何判断队列是满的还是空的?

一般解决这个问题可以采用两种办法: 1.设立标志位,flag=0为空队列,flag=1为满队列。 2.故意留出一个位置,比如6个位置的数组,当填满5个时即认为满队列

那么此时满队列的条件就不再是front=rear,而变成了(rear+1)%QueueSize=front,即: (0+1)%6=1 (5+1)%6=0 (1+1)%6=2 以上顺序结构实现的队列,对于链式结构也是同样,在栈中我们将头指针作为栈顶,这样的话只需要一个头指针就可以知道出栈的位置,但是对于链队列,我们却需要三个指针,分别是用于连接链的指针,用于指示队头的指针,用于指示对尾的指针。所在在链队列中就不需要循环队列了。

队列的存储结构

顺序结构:

typedef int QElemType; 
/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[6];
    int front;      /* 头指针 */
    int rear;       /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}SqQueue;

链式结构:

typedef int QElemType; 
typedef struct QNode    /* 结点结构 */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct          /* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

队列的常用操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 
typedef int Status; 
typedef int QElemType; 
Status visit(QElemType c)
{
    printf("%d ",c);
    return OK;
}

循环队列:

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return  OK;
}

/* 将Q清为空队列 */
Status ClearQueue(SqQueue *Q)
{
    Q->front=Q->rear=0;
    return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(SqQueue Q)
{ 
    if(Q.front==Q.rear) /* 队列空的标志 */
        return TRUE;
    else
        return FALSE;
}

/* 返回Q的元素个数,也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
    return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(SqQueue Q,QElemType *e)
{
    if(Q.front==Q.rear) /* 队列空 */
        return ERROR;
    *e=Q.data[Q.front];
    return OK;
}

/* 若队列未满,则插入元素e为Q新的队尾元素 */
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;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(SqQueue Q)
{ 
    int i;
    i=Q.front;
    while((i+Q.front)!=Q.rear)
    {
        visit(Q.data[i]);
        i=(i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

链队列:

/* 构造一个空队列Q */
Status InitQueue(LinkQueue *Q)
{ 
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front)
        exit(OVERFLOW);
    Q->front->next=NULL;
    return OK;
}

/* 销毁队列Q */
Status DestroyQueue(LinkQueue *Q)
{
    while(Q->front)
    {
         Q->rear=Q->front->next;
         free(Q->front);
         Q->front=Q->rear;
    }
    return OK;
}

/* 将Q清为空队列 */
Status ClearQueue(LinkQueue *Q)
{
    QueuePtr p,q;
    Q->rear=Q->front;
    p=Q->front->next;
    Q->front->next=NULL;
    while(p)
    {
         q=p;
         p=p->next;
         free(q);
    }
    return OK;
}

/* 若Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(LinkQueue Q)
{ 
    if(Q.front==Q.rear)
        return TRUE;
    else
        return FALSE;
}

/* 求队列的长度 */
int QueueLength(LinkQueue Q)
{ 
    int i=0;
    QueuePtr p;
    p=Q.front;
    while(Q.rear!=p)
    {
         i++;
         p=p->next;
    }
    return i;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(LinkQueue Q,QElemType *e)
{ 
    QueuePtr p;
    if(Q.front==Q.rear)
        return ERROR;
    p=Q.front->next;
    *e=p->data;
    return OK;
}


/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s) /* 存储分配失败 */
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    Q->rear=s;      /* 把当前的s设置为队尾结点,rear指向s,见图中② */
    return OK;
}

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(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;/* 将原队头结点的后继p->next赋值给头结点后继,见图中② */
    if(Q->rear==p)      /* 若队头就是队尾,则删除后将rear指向头结点,见图中③ */
        Q->rear=Q->front;
    free(p);
    return OK;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(LinkQueue Q)
{
    QueuePtr p;
    p=Q.front->next;
    while(p)
    {
         visit(p->data);
         p=p->next;
    }
    printf("\n");
    return OK;
}

最后,循环队列与链队列肯定是各有利弊的,循环队列终究是顺序结构,所以它一定会有顺序结构的先天缺陷(提前申请空间),所以在空间上可能会有浪费的情况,而链队列则不会这样,但是链队列反复的插入与删除元素就意味着不断的free和malloc,这样就会额外的时间开销(虽然时间复杂度都为O(1)),而且链队列的实现形式更为复杂。 当然这是一篇技术博客,个人的喜欢不应该出现在这里,只能很客观的说:在可以确定队列长度最大值的情况下,建议使用循环队列;在无法估计长度的情况下,使用链队列。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的技术专栏

数据结构图文解析之:队列详解与C++模板实现

974
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

952
来自专栏coolblog.xyz技术专栏

ArrayList 源码详细分析

ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时...

3978
来自专栏后端之路

最熟悉的ArrayList

上来先问几个问题 ArrayList是否存在最大容量? 如果ArrayList存在最大容量 那么达到最大之后会如何处理 ArrayList的性能影响因素 Arr...

1695
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

1906
来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

962
来自专栏racaljk

[数据结构]C语言队列的实现

我个人把链表、队列、栈分为一类,然后图、树分为一类。(串不考虑),分类的理由就是每一类有规律可循,即你能通过修改极少数的代码把链表变成队列、栈。(这里我们不考虑...

812
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

1095
来自专栏曾大稳的博客

线性表(ArrayList 和 LinkedList源码分析)

线性表(linear list) 是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

872
来自专栏有趣的Python

3-玩转数据结构-栈和队列

栈也是一种线性结构;相比数组,栈对应的操作是数组的子集;只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)

2482

扫码关注云+社区