【数据结构】队列(顺序队列、循环队列、链队列）

文章目录

前言

队列也是一种线性表，其特殊性在于队列的基本操作是线性表的子集。队列按“先进先出”的规则进行操作，故称其为操作受限的线性表。

---

一、队列的定义

队列（queue）是只允许在一端进行插入操作，在另一端进行删除操作的线性表，简称“队”。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。

允许插入的一端称为队尾（rear），允许删除的一端称为队头(front)。

向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

从队列中删除队头元素称为出队，其后继元素成为新的队头元素。

---

二、队列的顺序存储结构

队列作为一种特殊的线性表，也同样存在两种存储结构：顺序存储结构和链式存储结构，可以分别用数组和链表来实现队列。

1.顺序队列的定义

用一组地址连续的存储单元，依次存放从队头到队尾的数据元素，称为顺序队列。

需要附设两个指针：队头指针（front）和队尾指针（rear），分别指向队头元素和队尾元素。

头尾指针和顺序队列中数据元素之间的关系示意图：

“假溢出”：如果在插入E的基础上再插入元素F，将会插入失败。因为rear==MAXSIZE，尾指针已经达到队列的最大长度。但实际上队列存储空间并未全部被占满，这种现象叫做“假溢出”。

假溢出的原因是顺序队列进行队头出队、队尾入队，造成数组前面会出现空闲单元未被充分利用。

2.循环队列定义

为了解决“假溢出”现象，使得队列的存储空间得到充分利用，一个巧妙的方法就是将顺序队列的数组看成一个头尾相接的循环结构。

队列的头尾相接的顺序存储结构称为循环队列。

问题：当循环对列为空或满时，都是队尾指针等于队头指针，即rear==front 。当rear==front时，该是判满还是判空呢？

解决方案：

方案一：设置一个计数器，开始时计数器设为0，新元素入队时，计数器加1，元素出队，计数器减1。当计数器==MAXSIZE时，队满；计数器==0时，队空。

方案二：保留一个元素空间，当队尾指针指的空闲单元的后继单元是队头元素所在单元时，队满。

队满的条件为（Q.rear+1）%MAXSIZE==Q.front；

队空的条件为Q.rear==Q.front

3.循环队列的基本操作

typedef int ElemType
#define MAXSIZE 1024
 
/*循环队列的顺序存储结构*/
typedef struct
{
    ElemType data[MAXSIZE];
    int front;    //头指针
    int rear;    //尾指针
}SqQueue;
 
/*初始化一个空队列*/
int Init_SeQueue(SeQueue *Q)
{
    Q=(SeQueue *)malloc(sizeof(SeQueue));
    if(Q!=NULL)
    {
        Q->front=0;
        Q->rear=0;
    }
    return 1;
}
 
/*求队列长度*/
int QueueLength(SeQueue *Q)
{
    return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
}
 
/*判空*/
int SeQueue_Empty(SeQueue *Q)
{
    return Q->rear==Q->front;
}
 
/*判满*/
int SeQueue_Full(SeQueue *Q)
{
    return (Q->rear+1)%MAXSIZE==Q->front;
}
 
/*入队操作*/
int Enter_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Full(Q))
    {
        return 0;
    }
 
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return 1;
}
 
/*出队操作*/
int Delete_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Empty(Q))
    {
        return 0;
    }
 
    e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return 1;
}

---

三、队列的链式存储结构

1.链队列的定义

采用链式存储结构实现的队列称为链队列。

为了使操作更加方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点。 

空队列时，front和rear都指向头结点，即front==rear

链队列结构:

typedef int ElemType
 
/*结点结构*/
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
 
/*链队列结构*/
typedef struct 
{
    QueuePtr front,rear;//队头、队尾指针
}LinkQueue;

2.链队列的基本操作

typedef int ElemType
 
/*结点结构*/
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode,*QNodePtr;
 
/*链队列结构*/
typedef struct 
{
    QNodePtr front,rear;//队头、队尾指针
}LinkQueue,*LinkQueuePtr;
 
/*初始化一个空队列*/
int Init_LinkQueue(LinkQueuePtr Q)
{
    Q=(LinkQueuePtr)malloc(sizeof(LinkQueue));
    QNodePtr head=(QueuePtr)malloc(sizeof(QNode));
    
    if(head!=NULL && Q!=NULL)
    {
        head->next=NULL;
        Q->front=head;
        Q->rear=head;
    }
    return 1;
}
 
/*判空*/
int LinkQueue_Empty(LinkQueuePtr Q)
{
    return Q->front==Q->rear;
}
 
/*入队操作*/
int Enter_LinkQueue(LinkQueuePtr Q,ElemType e)
{
    QNodePtr s=(QNodePtr)malloc(sizeof(QNode));
    if(s==NULL){
        return 0
    }    
    //初始化新结点
    s->data=e;
    s->next=NULL;
    //建立新联系
    Q->rear->next=s;
    Q->rear=s;
 
    return 1;
}
 
/*出队操作*/
int Delte_LinkQueue(LinkQueuePtr Q,ElemType *e)
{
    QNodePtr p;
    if(LinkQueue_Empty(Q)){
        return 0
    } 
       
    //保留删除结点的信息
    p=Q->front->next;
    *e=p->data;
 
    //建立新联系
    Q->front->next=p->next;
   
    if(Q->rear==p)
    {
        Q->rear=Q->front)
    }
    
    free(p);
 
    return 1;
}