数据结构（九） -- C语言版 -- 栈和队列 - 队列的特殊实现

小鱼儿 2023-07-08 02:54 15阅读 0赞

### 我让你知道我有啥 ###

*   *   *  零、读前说明
         *  一、概述
         *  二、模型搭建
         *  三、代码实现
         *   *  3.1、代码工程的目录结构
             *  3.2、队列的存储结构定义
             *  3.3、出队入队实现过程分析说明
             *   *  3.3.1、入队实现过程分析说明
                 *  3.3.2、出队实现过程分析说明
                 *  3.3.3、几个特殊点的说明
             *  3.4、代码实现 - comqueue.h文件
             *  3.5、代码实现 - comqueue.c文件
         *  四、效果测试
         *  五、说明

### 零、读前说明 ###

*  本文中没有涉及到很多的相关理论知识，也没有做深入的了解，所以，您如果是想要系统的学习、想要多学习关于理论的知识等，那么本文可能并不合适您。
 *  本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。
 *  设计的代码并非全部公开，部分无关紧要代码并没有贴出来。
 *  如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。
 *  由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。
 *   嘻嘻。。。。 。。。。。。。。收！

### 一、概述 ###

根据上文 [队列的设计与实现][Link 1] 的说明以及后面的简单的总结，我们可以知道栈和队列均可以由顺序表和链表来实现。但是由于队列 **先进先出** 的特性导致不管是用**顺序表**还是**链表**都会出现有一端（入队或者出队）的操作需要循环遍历整个顺序表或者链表。那这种实现方式的操作的效率确实是很值得考虑的一方面。  
  基于上面的描述，我们现在考虑用其他的方式来实现队列的功能，但是能够在效率上比上面提到的顺序表和链表优秀的方式。那么下面的才想可能就是实现的一个方式和过程。

### 二、模型搭建 ###

我们已经知道，栈的操作不管是用顺序表还是链表都可以实现时间复杂度为O(1)。并且对于**栈的先进后出**的特性，我们可以使用两个栈来组成一个模型，正好组成了类似于先进先出的模型，也就是用来实现队列。  
  所以，我们基本可以画出这种模型的图示效果。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70]  
  上面的图片基本上已经很明确的显示了具体的模型内涵，其实就是：  
    一个栈（栈1）负责的队列的**入队列**操作  
    一个栈（栈2）负责的队列的**出队列**操作

对于两个栈来实现一个队列的情况也是一样的情况。组合成队列的情况就有下面的四种情况。

<table> 
 <thead> 
  <tr> 
   <th align="center">队列模型的特征</th> 
   <th align="center">实现入队列的栈1</th> 
   <th align="center">实现出队列的栈2</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">顺序结构队列</td> 
   <td align="center">顺序结构栈</td> 
   <td align="center">顺序结构栈</td> 
  </tr> 
  <tr> 
   <td align="center">顺序结构队列</td> 
   <td align="center">顺序结构栈</td> 
   <td align="center">链式结构站</td> 
  </tr> 
  <tr> 
   <td align="center">顺序结构队列</td> 
   <td align="center">链式结构栈</td> 
   <td align="center">顺序结构栈</td> 
  </tr> 
  <tr> 
   <td align="center">链式结构队列</td> 
   <td align="center">链式结构栈</td> 
   <td align="center">链式结构栈</td> 
  </tr> 
 </tbody> 
</table>

众所周知，**顺序表存在着最大容量的问题**。由于顺序队列用数组来模拟，所以存在着**最大容量**的问题 ，如果采用链表栈来实现，那么就不会有这样的问题。  
  本文为了实验测试效果，本次队列实现以及测试都使用的是 **顺序结构栈（入队列） + 链式结构栈（出队列） = 队列**的模型。

### 三、代码实现 ###

#### 3.1、代码工程的目录结构 ####

如果你看过之前的文章，那么下面的这种的目录结构你也不会陌生。没错，和之前的还是一模一样的结构形式。

$ tree comqueue/
    comqueue/
    ├── CMakeLists.txt
    ├── README.md
    ├── build
    ├── main
    │   └── main.c
    ├── runtime
    └── src
        ├── comqueue
        │   ├── comqueue.c
        │   └── comqueue.h
        ├── linklist
        │   ├── linklist.c
        │   └── linklist.h
        ├── linkstack
        │   ├── linkstack.c
        │   └── linkstack.h
        ├── seqlist
        │   ├── seqlist.c
        │   └── seqlist.h
        └── seqstack
            ├── seqstack.c
            └── seqstack.h
    
    9 directories, 13 files

#### 3.2、队列的存储结构定义 ####

那这个就比较简单了，由于是直接使用原本现成的栈的代码进行组合实现特殊的队列，那么这个队列的存储结构也就随之而来了。如下所示就成了。

typedef void ComQueue;
    typedef void ComQueueNode;
    
    typedef struct _tag_ComQueue
    { 
        SeqStack *enStack;
        LinkStack *deStack;
    
    } TComQueue;

#### 3.3、出队入队实现过程分析说明 ####

##### 3.3.1、入队实现过程分析说明 #####

正常情况来说，用两个栈中的其中一个栈来实现队列的入队列操作，其实也就是入栈的操作。  
  如果我们用的是顺序结构的栈来实现入队列的操作，那么必定涉及到 **顺序结构栈的  满** 的情况，此时应该如何进行操作可以人为去规定一下。  
  1、第一种情况  
  实现入队列的顺序结构**栈1出现了栈满**的情况，但是后面的链式结构的**栈2目前为空栈**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 1]  
  那对于这种情况，我们可以有两种方式去处理这个问题。  
    1）栈满 ==> 队列满，后续入栈（队列）直接报错返回  
    2）直接将所有的栈1的元素出栈到栈2中，此时栈1变成空栈又可以进行入栈（入队列）的操作了

2、第二种情况  
  实现入队列的顺序结构**栈1出现了栈满**的情况，但是后面的链式结构的**栈2目前不为空栈**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2]  
  那对于这种情况，**我们首先要保证的是队列的先进先出的特性**，那么此时对于栈2中的元素是肯定不能动了，但是又没有出队列的操作，所以此后出现的入队列的所有数据，就只能是队列满然后返回错误的操作了。

是的，如果使用的是链式结构的栈，那就不会这种情况（如果你要杠，我也没办法。咱就说的是一般情况下）。

##### 3.3.2、出队实现过程分析说明 #####

出队就简单了，不管你是什么结构的栈实现的，只要是出队列，那么就是出栈的操作，但是两种情况需要弄一下哈。  
  1、第一种情况  
  如果栈2为空栈，那么就从栈1中去要了  
    1）如果栈1为空，那就是一个空队列无疑了  
    2）如果栈1不为空，那么就需要将栈1中的所有的元素都弄过来  
  2、第二种情况  
  如果栈2不为空栈，那么就从栈2中出栈就是了

##### 3.3.3、几个特殊点的说明 #####

看了上面的描述是不是感觉好简单，很简单的那种简单。那么下面简答的说明一下本测试中采用与处理的方式。  
  1、如果出现栈1为满的情况，那么在后续的入栈（队列）的操作将直接返回错误。有需要改正的小伙伴请自行改正并食用。  
  2、由于入队列的实现的栈为顺序结构的栈，所以存在最大容量的约束。定义入队列的实现栈的容量为 **Capacity**， 那么本文采用的队列的容量也为 **Capacity** ，当然你也可以定义为两个栈组合成的队列的总容量为 **Capacity \* 2** 。  
  3、如果你使用链表栈的话，就不会有这样的问题出现了（如果你要杠，我也没办法。咱就说的是一般情况下）。

#### 3.4、代码实现 - comqueue.h文件 ####

**conqueue.h**文件中定义了业务节点的类型，所有涉及的操作函数的定义以及申明。具体内容如下。

#ifndef __COMQUEUE_H__
    #define __COMQUEUE_H__
    
    #include "../seqstack/seqstack.h"
    #include "../linkstack/linkstack.h"
    
    typedef void ComQueue;
    typedef void ComQueueNode;
    
    typedef struct _tag_ComQueue
    { 
        SeqStack *enStack;
        LinkStack *deStack;
    
    } TComQueue;
    
    typedef struct func_ComQueue
    { 
        ComQueue *(*create)();
        int (*destroy)(ComQueue *);
        int (*clear)(ComQueue *);
        int (*length)(ComQueue *);
        int (*append)(ComQueue *, ComQueueNode *);
        ComQueueNode *(*header)(ComQueue *);
        ComQueueNode *(*subtract)(ComQueue *);
    
        int (*capacity)(ComQueue *);
    
    } func_ComQueue;
    
    #endif

#### 3.5、代码实现 - comqueue.c文件 ####

**conqueue.c**文件为具体的队列的功能的实现文件，具体内容如下。

#include "comqueue.h"
    
    /** * 包含顺序栈和链式栈的类 **/
    extern func_SeqStack fun_SeqStack;
    extern func_LinkStack fun_LinkStack;
    
    /** * 功 能： * 创建一个队列 * 参 数： * 无 * 返回值： * 成功：操作句柄 * 失败：NULL **/
    ComQueue *ComQueue_Create(int capacity)
    { 
        TComQueue *queue = (TComQueue *)malloc(sizeof(TComQueue));
        if (queue == NULL)
            return NULL;
    
        queue->enStack = fun_SeqStack.create(capacity);
        queue->deStack = fun_LinkStack.create();
        if (queue->enStack == NULL || queue->deStack == NULL)
        { 
            fun_SeqStack.destroy(queue->enStack);
            fun_LinkStack.destroy(queue->deStack);
    
            free(queue);
            return NULL;
        }
    
        return queue;
    }
    
    /** * 功 能： * 清空一个队列 * 参 数： * queue：要操作的队列 * 返回值： * 成功：0 * 失败：-1 **/
    int ComQueue_Clear(ComQueue *queue)
    { 
        int ret = -1;
        TComQueue *temp = (TComQueue *)queue;
        if (temp == NULL)
            return -1;
    
        ret = fun_SeqStack.clear(temp->enStack);
        if (ret != 0)
            return ret;
    
        ret = fun_LinkStack.clear(temp->deStack);
        if (ret != 0)
            return ret;
    
        return ret;
    }
    
    /** * 功 能： * 销毁一个队列 * 参 数： * queue：要操作的队列 * 返回值： * 成功：0 * 失败：-1 **/
    int ComQueue_Destroy(ComQueue *queue)
    { 
        int ret = ComQueue_Clear(queue);
        if (queue != NULL)
            free(queue);
    
        return ret;
    }
    
    /** * 功 能： * 获取队列的长度 * 参 数： * queue：要操作的队列 * 返回值： * 成功：队列的长度 * 失败：-1 **/
    int ComQueue_Length(ComQueue *queue)
    { 
        TComQueue *tqueue = (TComQueue *)queue;
        if (tqueue == NULL)
            return -1;
    
        int len = fun_SeqStack.length(tqueue->enStack) +
                  fun_LinkStack.length(tqueue->deStack);
    
        return len;
    }
    
    /** * 功 能： * 插入元素，压队列 * 参 数： * queue：要操作的队列 * item : 要插入的元素，队列的业务节点 * 返回值： * 成功：0 * 失败：-1 **/
    int ComQueue_Append(ComQueue *queue, ComQueueNode *item)
    { 
        TComQueue *tqueue = (TComQueue *)queue;
        if (tqueue == NULL)
            return -1;
    
        int ret = fun_SeqStack.push(tqueue->enStack, (SeqStackNode *)item);
    
        return ret;
    }
    
    /** * 功 能： * 获取队列头的元素 * 参 数： * queue：要操作的队列 * 返回值： * 成功：操作句柄 * 失败：NULL **/
    ComQueueNode *ComQueue_Header(ComQueue *queue)
    { 
        TComQueue *tqueue = (TComQueue *)queue;
        if (tqueue == NULL)
            return NULL;
    
        ComQueueNode *ret = NULL;
        if (fun_LinkStack.length(tqueue->deStack) == 0)
        { 
            while (fun_SeqStack.length(tqueue->enStack) > 0)
            { 
                fun_LinkStack.push(tqueue->deStack,
                                   (LinkStackNode *)fun_SeqStack.pop(
                                       tqueue->enStack));
            }
        }
    
        ret = fun_LinkStack.top(tqueue->deStack);
    
        return ret;
    }
    
    /** * 功 能： * 弹出队列元素 * 参 数： * queue：要操作的队列 * 返回值： * 成功：删除后的元素 * 失败：NULL **/
    ComQueueNode *ComQueue_Subtract(ComQueue *queue)
    { 
        TComQueue *tqueue = (TComQueue *)queue;
        if (tqueue == NULL)
            return NULL;
    
        ComQueueNode *ret = NULL;
        if (fun_LinkStack.length(tqueue->deStack) == 0)
        { 
            while (fun_SeqStack.length(tqueue->enStack) > 0)
            { 
                fun_LinkStack.push(tqueue->deStack,
                                   fun_SeqStack.pop(
                                       tqueue->enStack));
            }
        }
    
        ret = fun_LinkStack.pop(tqueue->deStack);
    
        return ret;
    }
    
    /** * 功 能： * 获取队列的最大容量 * 参 数： * Queue：要操作的队列 * 返回值： * 成功：队列得容量 * 失败：-1 **/
    int ComQueue_Capacity(ComQueue *queue)
    { 
        TComQueue *tqueue = (TComQueue *)queue;
        return fun_SeqStack.capacity((SeqStack *)tqueue->enStack);
    }
    
    func_ComQueue fun_ComQueue = { 
        ComQueue_Create,
        ComQueue_Destroy,
        ComQueue_Clear,
        ComQueue_Length,
        ComQueue_Append,
        ComQueue_Header,
        ComQueue_Subtract,
        ComQueue_Capacity};

### 四、效果测试 ###

本次测试是在**Linux**环境下进行，详细说明在**README.md**中查看。  
  1、使用Cmake编译，使用下面指令

$ cd build
    $ cmake -G"MinGW Makefiles" .. # 注意 .. ,表示上级目录
    $ make

实际在运行指令过程效果如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3]

2、经过**cmake**编译之后，配置**cmake**将**可执行文件放在固定目录runtime**下，可以使用在当前目录下使用指令 **`./../runtime/comqueue`来运行可执行程序，也可以进入到目录runtime**中，然后使用指令 **`./comqueue`** ，即可运行测试程序。实际测试的结果如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 4]  
  至此，代码全部运行完成并且也貌似符合代码的运行期望。

### 五、说明 ###

请注意，入队列或者说成入栈的数据为 **数组 a** 和 **数组 b** 中的数据，但是实际上栈或者队列中存放的是**数组a**和**数组b**中各个成员的地址。  
  本例程中的**数组a**和**数组b**可以为任何形式的数据，而在入栈或者入队列的时候，只是记录了他的地址而已。  
  如果外部力量改变了**数组a**或者**数组b**中的成员的值，那么在出栈或者出队列的时候，输出的值将会是外部力量修改后的值。这可能出现与你入队列的时候的值不符。  
  这些特征，正是我的说的通用链表，通用顺序表、通用栈、通用队列的主要表现，他可以包含万事万物（是有点吹的成分，但是确实是通用，我只关心的要给我插入的节点的地址。。。。）。

看到我巴巴的眼睛了吗，求点赞，求关注。。。。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 5]

上一篇：[数据结构（八） – C语言版 – 栈和队列 - 队列的设计与实现][Link 1]  
下一篇：[数据结构（十） – C语言版 – 树 - 基础知识][_ C_ _ _ -]

[Link 1]: https://blog.csdn.net/zhemingbuhao/article/details/104486957
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200315015417989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020031520030880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020031520121237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200315194447745.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200315194646633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200315223905184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70
[_ C_ _ _ -]: https://blog.csdn.net/zhemingbuhao/article/details/104888752