数据结构-队列

队列的定义

在很多资料中,队列与往往一同出现,因为它与栈有很多相似的地方。队列是只允许在一端插入另一端删除的线性表,即一种先入先出(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 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

1825
来自专栏深度学习与计算机视觉

数据结构-栈

栈的定义 栈是一种特殊的线性表,仅允许在表的一端进行插入和删除运算。这一端被称为栈顶(top),相对地,把另一端称为栈底(bottom)。向一个栈插入新元素又称...

18010
来自专栏决胜机器学习

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十四) ——键树(双链树) (原创内容,转载请注明来源,谢谢) 一、概念 键树又称为数字查找树,该树的度>=2,每个节点不是存储关键字,而是存...

4079
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3387
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

411
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

1949
来自专栏开发与安全

数据结构:队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头节点,而队尾指针指向终...

1879
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2176
来自专栏Bingo的深度学习杂货店

Q66 Plus One

Given a non-negative integer represented as a non-empty array of digits, plus on...

3156
来自专栏猿人谷

顺序循环队列

1 //循环队列的顺序存储表示与实现 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 /**...

1838

扫码关注云+社区