数据结构之栈和队列（二）

淡淡的烟草味﹌ 2022-02-25 05:05 385阅读 0赞

在上篇博文中，我们了解了栈的节本原理和操作。本文主要介绍另外一种操作受限的线性表，**队列（Queue）**。

**队列（Queue）也是一种操作受限的线性表，它只允许在表的一端进行插入，而在另外一端进行删除，满足先进先出（FIFO）**。

### 队列的基本操作 ###

1.  `InitQueue(&Q)`：初始化
2.  `QueueEmpty(Q)`：判断队列是否为空
3.  `EnQueue(&Q,x)`：入队，若Q未满，将x加入，使之成为新的队尾
4.  `DeQueue(&Q,&x)`：出队，若Q非空，删除队头元素，并用x返回
5.  `GetHead(Q,&x)`：读队头元素，若Q非空，将队头元素赋值给x

### 队列的顺序存储结构 ###

分配一块**连续的存储单元**存放队列中的元素，并附设**两个指针front和rear**分别指向队头元素和队尾元素的位置。设队头指针指向队头元素，**队尾指针指向队尾的下一个位置**。

**队列的顺序存储类型可描述如下：**

#define MaxSize 50
    typedef struct{
        
        ElemType data[MaxSize];    //存放队列元素
        int front,rear;           //队头指针和队尾指针
    }SqQueue;

**初始状态**（队空条件） Q . f r o n t = = Q . r e a r = = 0 Q.front==Q.rear==0 Q.front==Q.rear==0  
**进队操作**：队不满时，先送值到队尾元素，再将队尾指针**加1**  
**出队操作**：队不空时，先取队头元素，再将队头指针**加1**

![1.png][]

如上图所示，我们可以用 Q . f r o n t = = Q . r e a r = = 0 Q.front==Q.rear==0 Q.front==Q.rear==0来判断队列是否为空，但是我们不能用 Q . r e a r = = M a x S i z e Q.rear==MaxSize Q.rear==MaxSize作队满的条件，如上图(d)所示。

### 循环队列 ###

为了克服顺序队列的缺点，引出了循环队列，将顺序队列臆造为一个环状空间。

![2.png][]

**出队入队时，指针按顺时针方向进1**，如下图所示：

![3.png][]

为了区分 Q . f r o n t = = Q . r e a r Q.front==Q.rear Q.front==Q.rear为队空还是队满，有三种处理方式：

1.  入队时，少用一个队列单元，**队头指针在队尾指针的下一个位置时队满**

> **队满条件**： ( Q . r e a r + 1 ) (Q.rear+1) (Q.rear\+1)% M a x S i z e = = Q . f r o n t MaxSize==Q.front MaxSize==Q.front  
> **队空条件**： Q . f r o n t = = Q . r e a r Q.front==Q.rear Q.front==Q.rear  
> **队列中元素个数**： ( Q . r e a r − Q . f r o n t + M a x S i z e ) (Q.rear-Q.front+MaxSize) (Q.rear−Q.front\+MaxSize)% M a x S i z e MaxSize MaxSize

1.  增设表示元素个数的数据成员

> **队空**： Q . s i z e = = 0 Q.size==0 Q.size==0  
> **队满**： Q . s i z e = = M a x S i z e Q.size==MaxSize Q.size==MaxSize

1.  增设tag成员，区分队满还是队空（**tag表示下一个存储空间是否为空**）

> \*\*tag=0,出队：\*\*因为删除导致 Q . f r o n t = = Q . r e a r Q.front==Q.rear Q.front==Q.rear (**队空**)  
> \*\*tag=1,进队：\*\*因为插入导致 Q . f r o n t = = Q . r e a r Q.front==Q.rear Q.front==Q.rear (**队满**)

**循环队列的基本操作如下：**

//初始化
    void InitQueue(&Q){
        
        Q.rear=Q.front=0;
    }
    //判断队列是否为空
    bool isEmpty(Q){
        
        if(Q.rear==Q.front)
            return true;
        else
            return false;
    }
    //入队
    bool EnQueue(SqQueue &Q,ElemType x){
        
        if((Q.rear+1)%MaxSize==Q.front)
            return false;
        else
            Q.data[Q.rear]=x;
        	Q.rear=(Q.rear+1)%MaxSize;
        	return true;
    }
    //出队
    bool DeQueue(SqQueue &Q,ElemType &x){
        
        if(Q,rear==Q.front)
            return false;
        x=Q.data[Q.front];
        Q.front=(Q.front+1)%MaxSize;
        return true;
    }

### 队列的链式存储结构 ###

本质上是一个**同时带有队头指针和队尾指针的单链表**。头指针指向队头结点，尾指针指向队尾结点。

**队列的链式存储类型可以描述如下：**

typedef struct{
        
        ElemType data;
        struct LinkNode *next;
    }LinkNode;
    typedef struct{
        
        LinkNode *front,*rear;
    }LinkQueue;

Q . f r o n t = = N U L L Q.front==NULL Q.front==NULL且 Q . r e a r = = N U L L Q.rear==NULL Q.rear==NULL,链式队列为空  
\*\*出队：\*\*首先判空，若队列不为空，取出队头元素，删除，让 Q . f r o n t Q.front Q.front指向下一个结点  
\*\*进队：\*\*建立新结点，将该结点插入链表尾部，并让 Q . r e a r Q.rear Q.rear指向这个新插入的结点

**通常将链式队列设计成一个带头结点的单链表，这样可以统一插入和删除操作**。

**链式队列的基本操作**

//初始化
    void InitQueue(LinkQueue &Q){
        
        Q.front=Q.rear=(LinkNode *) malloc (sizeof(LinkNode));
        Q.front->next=NULL;
    }
    //判断队列是否为空
    bool IsEmpty(LinkQueue Q){
        
        if(Q.front==Q.rear)
            return true;
        else
            return false;
    }
    //入队
    void EnQueue(LinkQueue &Q,ElemType x){
        
        s=(LinkNode *) malloc (sizeof(LinkNode));
        s->data=x; 
        s->next=NULL;
        Q.rear->next=s;
        Q.rear=s;
    }
    //出队
    bool DeQueue(LinkQueue &Q,ElemType &x){
        
        if(Q.front==Q.rear)
            return false;
        p=Q.front->next;
        x=p->next;
        Q.front->next=p->next;
        if(Q.rear==p)
            Q.rear=Q.front;
        free(p);
        return true;
    }

### 双端队列 ###

双端队列是指允许两端都可以进行入队和出队操作的队列。

![4.png][]

\*\*进队：\*\*前端进的元素在后端进的元素前面  
\*\*出队：\*\*无论前端还是后端出队，先出的元素排在后出的元素前面  
\*\*输出受限：\*\*允许一端进行插入和删除，另外一端只能插入  
\*\*输入受限：\*\*允许一端进行插入和删除，另外一端只能删除

**栈和队列的应用：**（以后会详细讲解）

1.  栈：**括号匹配**、**表达式求值**、**递归**、进制转换、迷宫求解…
2.  队列：**二叉树的层次遍历**、缓冲区、页面替换算法、广度优先搜索图

### 特殊矩阵的压缩存储 ###

\*\*数组与线性表的关系：\*\*数组是线性表的推广。一维数组可以看做是一个线性表，二维数组可以看做元素是线性表的线性表。**数组只有存取元素和修改元素操作**。

**数组的存储结构**

![5.png][]

**矩阵的压缩存储**

![6.png][]

[1.png]: /images/20220225/4f8b4ed0375141d8886e2bcb85953df9.png
[2.png]: /images/20220225/a1c9b6ab1be9423593eb9552ff4ab9da.png
[3.png]: /images/20220225/cd77f750afc04840baf92ead70d29b4f.png
[4.png]: /images/20220225/f88f129d7e864638a7bb060087a20ed6.png
[5.png]: /images/20220225/41646f4a957d4105942f3c8cec45ebaa.png
[6.png]: /images/20220225/eb5e8f31c8b44f3ba3a34749faadd141.png