首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构-队列

数据结构-队列

作者头像
chaibubble
发布2018-01-02 11:36:58
5160
发布2018-01-02 11:36:58
举报

队列的定义

在很多资料中,队列与往往一同出现,因为它与栈有很多相似的地方。队列是只允许在一端插入另一端删除的线性表,即一种先入先出(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)),而且链队列的实现形式更为复杂。 当然这是一篇技术博客,个人的喜欢不应该出现在这里,只能很客观的说:在可以确定队列长度最大值的情况下,建议使用循环队列;在无法估计长度的情况下,使用链队列。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-08-13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 队列的定义
  • 队列的存储结构
  • 队列的常用操作
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档