基于《啊哈！算法》和《数据结构》（人民邮电出版社）

本博客篇幅较多，读者根据目录选择，不理解的可留言和私信。

栈、队列、链表都是线性结构。

三者都不是结构体、数组这种数据类型，我认为更像是一种算法。

针对问题：

1.相较于数组的优点

2.模板，结合结构体

3.栈、队列、链表之间的结合

4.STL库容器

一、队列

原则：先进先出

        队列，顾名思义就像是买东西排队先到的人先出，我们先看一道《啊哈！算法》上的例子：

解密QQ号：

        “6 3 1 7 5 8 9 2 4”是小哈给小哼的加密数字，规则是：首先将第一个数删除，紧接着将第二个数放到这串数的末尾，再将第三个数删除并将第四个数放到这串数的末尾，再将第五个数删除……直到剩下最后一个数。将最后一个数删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的QQ号。

        对于这道题，这些加密数字就满足“先进先出”的原则。解题思路如图：

非队列思路 

         在不知道队列的时候，我的C解题思路如下：（其实也有队列的影子）

#include <stdio.h>int main()
{int q[100]={0,6,3,1,7,5,8,9,2,4};int m[10]={0};int len=10;int i=0;for ( i = 1; q[i] != 0; i++)//条件最后一个数被删除{// printf("%d\n",q[i]);if(i%2==1)//删除{printf("%d",q[i]);}else if(i%2 == 0)//放到数组的末尾{q[len]=q[i];len++;}}// for(i=0;i<len-1;i++)// printf("%d",m[i]);return 0;
}

        当i为奇数时，则删除就，为偶数时就移到末尾，直到删除到最后一个，及q[i]==0。

        引入队列的定义：队列主体，队首，队尾；队首出队即删除，队尾进队即插入。

队列思路

我认为队列可以更加优雅的完成一些问题。队列的解题思路如下：

#include<stdio.h>
int main()
{int q[102]={0,6,3,1,7,5,8,9,2,4};int head = 1;int tail =10;while(head<tail){//打印队首并将队首出队printf("%d ",q[head]);head++;//先将新队首的数添加到队尾q[tail]=q[head];tail++;//再将队首出队head++;}return 0;
}

现在有九个数，9个数全部放入队列之后，head=1，tail=10(队尾指向的是尾元素的后一位，1-9为有效元素，这样写防止了“假溢出”)，此时head和tail之间的数就是队列的有效数，如果要删除一个数的话。就将head++就行了，这样可以保证head和tail之间的数为有效数，及“排队的数”，这样做虽然浪费了一个空间，却节省了大量的空间，这是非常划算的，新增一个数也很简单，把需要增加的数放到队尾即q[tail]之后再tail++就行了。 

定义一个结构体，即可认定为一个新的数据类型：队列，如下：

struct queue
{int data[100];    //队列的主体，用来排队int head;        //队首      int tail;         //队尾
};

结构体模板

 下面这段代码就是使用结构体来实现队列操作：

#include<stdio.h>struct queue
{int data[100];    //队列的主体，用来排队int head;        //队首      int tail;         //队尾
};int main()
{struct queue q;int i=0;q.head = 1;q.tail = 1;for ( i = 1; i <= 9; i++){scanf("%d",&q.data[q.tail]);q.tail++;}while(q.head<q.tail)    //当队列不为空的时候执行循环{//打印队首并将队首出队printf("%d ",q.data[q.head]);q.head++;//先将新队首的数添加到队尾q.data[q.tail]=q.data[q.head];q.tail++;//再将队首出队q.head++;}return 0;
}

 另外C++的STL库已经有队列的实现。

队列的基本操作
q.push(x)：将元素 x 放入队尾。
q.pop()：将队头元素出队。(只能删除，不能返回队首的值)
q.empty()：判断队列是否为空，为空返回 t r u e，否则返回 f a l s e 。（头尾队列重合为空）
q.size()：返回队列长度。
q.front()：返回队头元素，不出队。（返回的是队首元素的值）
q.back()：返回队尾元素。

STL库队列容器

使用STL库的queue容器实现：

#include <bits/stdc++.h>
using namespace std;int main()
{queue<int> q;for (int i = 1; i <= 9; i++){int x=0;scanf("%d",&x);q.push(x);}while(q.empty() == 0)    //当队列不为空的时候执行循环{//打印队首并将队首出队printf("%d ",q.front());q.pop();//先将新队首的数添加到队尾int x=q.front();q.push(x);//再将队首出队q.pop();}return 0;
}

其它还有：优先队列，双向队列。 

扩展： 

       （一）循环队列

        通过取“模”实现。

        假设当前队列分配的最大空间为6，则当队列处于如图（d）所示(队首经过删除得到)的状态时不可再继续插入新的队尾元素，否则会出现溢出现象。但实际上，队列的实际可用空间只用了两个，这称为“假溢出”。是由“队尾入队，队头出队”这种限制造成的。

        一个巧妙的办法是将顺序队列变为一个环状的空间，成为循环队列。如图所示3.13：

        头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作通过模实现。通过取模，头尾指针可以在顺序表空间内以头尾衔接的方式循环移动。

        如图3.14（a）队头位置是q[5](从1-6共六个数),队尾位置是q[5]（队头队尾重合）,队尾插入一位，通过模运算，q[(5+1)%6]==q[0],即实现循环，又多“开辟”了6-1-2-3-4这五个空间，并且实现了循环。

                那么我们如何判断队列空间是满还是空呢？

        （1）少用一个元素，即当队列空间大小为m时，有m-1个元素就认为是队满。这样判断对空的条件不变，即当头尾指针的值相同时；而当尾指针在循环意义上加1后等于头指针时，则认为队满。如下：

队空：Q.front == Q.rear（一定要记得Q。rear指向的是队尾元素的后一个）

队满：Q.(Q.rear + 1)%m == Q.front

        (2)另设一个标记位，队列本来就是类似算法，灵活性高，大家可以自己定义。

                求循环队列的长度

        (Q.rear-Q.front+m)%m;（前面经过了取模，所以Q.rear的范围为1-m）

        情况d来举例，（4-5+6）%6=5；是J5-J9。

        （二）链队列

        顾名思义，相比前面的线性结构，这里是链式结构实现的队列。（具体实现了解链表便可领会）

                特点：

（1）不需要判断队满（不受最大空间容量的限制）

（2）可以插队

（3）队首为链表的头部

二、栈

原则：后进先出

        栈限定为只能在一端进行插入和删除工作，就像是一个小桶，直径只能放一个球，先放进去的球最后取，后放进去的球先取。如图（来自《啊哈！算法》）

          栈的实现只需要一个一维数组和一个指向栈顶的变量top就行了。我们通过top来对栈进行插入和删除

        我们来看一道例题：解密回文。

        “xyzyx”是一个回文字符串，所谓回文字符串就是指正读和反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文，通过栈这个数据结构我们将很容易的判断一个字符串是否为回文。

        栈思路

        假设判断“ahyha”

        先求出字符串长度，如果一个字符串为回文的，那么必将中心对称，中心点‘y’左面的从左向右依次入栈入栈为“a h”，栈顶指向‘h’，然后从栈顶依次出栈与中心点右边的“h a”比较。

#include <stdio.h>
#include <string.h>int main()
{char str[100]={'\0'},s[100]={'\0'};int len=0,i=0,next=0,top=0,mid=0;gets(str);len=strlen(str);// 读取字符串和长度mid=len/2-1;// 如果回文则必将从中间对称，我们取中心点for ( i = 0; i <= mid; i++)// 加等于号，预防输入的是两个字符{s[++top]=str[i];}// 将mid之前的字符存入栈if (len%2==0) // 判断回文为奇数还是偶数{next=mid+1; //偶数}elsenext=mid+2; //奇数for ( i = next; i <= len-1; i++){if (str[i]!=s[top])// 判断是否为中心对称{break;}top--;// 不能简写s[top--],应该先判断为1后再--}// 如果top为0，则说明栈内所有的字符都被一一匹配了if(top == 0)printf("YES");elseprintf("NO");return 0;
}

结构体模板 

        栈也有结构体模板，解密回文具体思路不再展示。

struct stack
{int data[100];    //栈的主体int top;        //栈顶      
};

 STL栈容器

使用STL库的stack容器实现：       

#include <bits/stdc++.h>
using namespace std;int main()
{stack<int> s;char str[100]={'\0'};int len=0,next=0,mid=0;gets(str);len=strlen(str);// 读取字符串和长度mid=len/2-1;// 如果回文则必将从中间对称，我们取中心点for (int i = 0; i <= mid; i++)// 加等于号，预防输入的是两个字符{s.push(str[i]);}// 将mid之前的字符存入栈if (len%2==0) // 判断回文为奇数还是偶数next=mid+1; //偶数elsenext=mid+2; //奇数for (int i = next; i <= len-1; i++){if (str[i]!=s.top())// 判断是否为中心对称{break;}s.pop();// 不能简写s[top--],应该先判断为1后再--}// 如果top为0，则说明栈内所有的字符都被一一匹配了if(s.size() == 0)printf("YES");elseprintf("NO");return 0;
}

stack容器和queue容器 成员函数差不多，两种容器均自动管理内存，无容量限制；均不允许遍历操作。

1、s.emplace();                在栈顶构造元素，避免复制或者移动等操作影响性能

2、s.empty();                      判断栈是否为空

3、s.pop();                          从栈顶出栈

4、s.push();                      从栈顶入栈

5、s.size();                         返回栈元素数量

6、s.swap();                       交换堆栈

7、s.top();          访问栈顶元素，返回引用

扩展：

（一）链栈

        链表与栈结合，链式结构的栈。

        特点：

（1）不需要判断栈满（不受最大空间容量的限制）

（2）栈顶为链表的头部        

（二）栈与递归

        栈有一个重要的应用是在程序设计语言中实现递归。递归与栈有很多相似之处

        所谓递归是指，若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称其是递归的，或者是递归定义的。在以下三种情况，常常使用递归的方法：

1.定义是递归的

 阶乘函数

求解代码（  n！）

long Fact(long n)
{if( n == 0) return 1;    // 递归终止条件else return n*Fact(n-1); // 递归步骤
}

二阶斐波那契数列

求解代码

long Fib(long n)
{if(n==1 || n==2) return 1;      //递归终止条件else return Fib(n-1)+Fib(n-2);  //递归步骤
}

计算4！时先计算3！，再进一步分解求解进行求解，这种分解求解的策略叫做“分治法”

采取分治法的条件：

（1） 能将一个问题转变成一个新问题，并且新问题与原问题解法相同或相似。不同的仅是处理对象，并且其处理对象更小且变化规律。

（2）可以通过上述转化而使问题简化。

（3）必须有一个明确的递归出口，或者称递归的边界。

“分治法”求解递归问题算法的形式如下：

void p(参数表)
{if(递归结束条件成立) 可直接求解；    // 递归终止的条件else p(较小的参数)；                // 递归步骤
}

2.数据结构是递归的

        链表

3.问题的解法是递归的

        有一类问题，问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，经典如Hanoi（汉诺）塔问题、八皇后问题、迷宫问题等。

        

Hanoi塔问题的递归算法（问题不再赘述）

【算法步骤】

1.如果 n = 1, 则直接将编号为1的圆盘从塔座A移到塔座C，递归结束。

2.否则：

• 递归，将塔座A上编号为1至n-1的圆盘移到塔座B，塔座C作为辅助塔座；
• 直接将编号为n的圆盘从塔座A移到塔座C，塔座A为辅助塔座。
• 递归，将塔座B上编号为1至n-1的圆盘移到塔座C，塔座A作为辅助塔座。

#include <stdio.h>int m=0;
void move(char A,int n,char C)
{printf("%d,%d,%c,%c\n",++m,n,A,C);
}void Hanoi(int n, char A,char B,char C)
{//将塔座A上的n个圆盘按规格搬到塔座C上，塔座B作为辅助塔座if(n == 1) move(A,1,C);else{Hanoi(n-1,A,C,B); //将塔座A上编号为1至n-1的圆盘移到塔座B，塔座C作为辅助塔座；move(A,n,C);      //直接将编号为n的圆盘从塔座A移到塔座C，塔座A为辅助塔座。Hanoi(n-1,B,A,C); //递归，将塔座B上编号为1至n-1的圆盘移到塔座C，塔座A作为辅助塔座。}}
int main()
{char A='A',B='B',C='C';Hanoi(2,A,B,C);return 0;
}

递归过程和递归工作站

        我们可以发现，当有多个函数构成嵌套调用时，按照“先调用后返回”的原则，上述函数之间的信息传递和控制必须通过“栈”来实现，系统将整个程序运行所需的数据空间安排在一个栈中，没调用一个函数就在栈顶为它分配一个储存空间，每从一个函数退出，就释放它的储存区。如此，当前正运行的函数的数据区必在栈顶。

递归算法的效率分析

        时间复杂度分析

        当一个算法中包含递归调用时，其时间复杂度的分析可以转化为一个递归求解方程，就是数学上求解渐近阶的问题。

        迭代法时求解递归方程的一种常用方法，其基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端的估计。

例如求阶乘函数Fact（4）：（来自《数据结构》）

        设Fact(n)的执行时间是T(n)。此递归函数中语句： if( n == 0) return 1 的执行时间是o(1),递归调用Fact(n-1)的执行时间是T(n-1)，所以else return n*Fact(n-1)的执行时间是O(1)+T(n-1)。其中，设两数相乘和赋值操作的时间为O(1),则对某常数C、D有如下递归方程：

 采用这种方法计算斐波那契数列和Hanoi塔问题递归算法的时间复杂度，可得到结果均为O(2^n)。

        空间复杂度分析

        S(n) = O(f(n))

        其中，f(n)为“递归工作栈”中工作记录的个数与问题规模n的函数关系。

        斐波那契数列和Hanoi塔问题递归算法的空间复杂度，可得到结果均为O(n)。

  

利用栈将递归转换为非递归的方法

        递归程序在执行时需要系统提供隐式栈这种数据结构来实现，对于一般的递归过程，仿照递归算法执行过程中递归栈的状态变换可直接写出相应的非递归算法，具体实例不再叙述，想要了解的直接可以去试试。

三、链表 

链表是一种递归的数据结构，学会链表的前提是你要懂得指针和结构体。

        有一串已经排好大小的数字“2 3 5 8 9 10 18 26 32”，现在要向这段数字中插入‘6’，使其新的序列仍符合从大到小排列，如果我们用数组来实现这一操作，则需要将8和8后面的数都依次往后挪一位，而对于链表，只需要将‘5’的指针指向‘6’，再将‘6’的指向‘8’就完成了插入。如下

       

        也正因为如此，链表相邻元素的地址可以是不连续的，就像发邮件，我不需要和你挨在一起，只需知道你的邮箱就行。所以链表中，我认为最重要的就是地址。

        代码示例

        废话不多说，我们先来理解一个简单点的的链表代码：（大家可以结合注释看一下代码。代码实现的功能是将n个数字存入链表）

#include<stdio.h>
#include<stdlib.h>struct node //定义链表
{int data;struct node *next;
};int main()
{struct node *head, *p, *q, *t;int i,n,a;scanf("%d",&n);head =NULL;for ( i = 0; i < n; i++)  //将数据存入链表{scanf("%d",&a);p=(struct node *)malloc(sizeof(struct node));  //分配动态内存，给p分配一个地址p ->data=a;                                    //将a存入这个地址p->next=NULL;                                  //分配下一个节点if (head ==NULL)        //如果这是创建的第一个节点，则将头指针指向这个节点，理解为火车头{head=p;printf("head=%d",head->data);}else                    //不是第一个节点,就与上一个节点连接，就是连接车厢，如果上节车厢为A，这节为B，那么就是把B连接到Aq->next=p;q=p;                    //保证下一个车厢连接的是B不是A// printf("%d \n",q->data);// t=q->next;// printf("%d\n",t->data);}t=head;while (t!=NULL){printf("%d ",t->data);//从火车头向后跑，把连接的车厢依次输出。t=t->next;}free(p);p=NULL;return 0;
}

         把这个理解了，链表的“增 删 改 查”就没有什么问题了。要理解最重要的是地址，这些步骤都是围绕将数字存入地址进行的，这几个结构体变量都是只能存储一个节点。链表是通过地址连接的。

结构体模板

struct node //定义链表
{int data;struct node *next;
};

         结构体只包含两个变量，一个是存储的数据data，另一个就是该节点的地址。多个节点相连接，便构成了链表。

头节点、首元节点、头指针

        这是链表中比较容易混淆的三个概念。

        （1）首元节点是指链表中储存第一个数据元素的结点，

        （2）头结点是首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不储存任何信息，也可储存与数据元素类型相同的其它附加信息。

        （3）头指针是指向链表中第一个节点的指针。若链表设有头结点，这头指针指向它，若没有则指向首元结点。

        本代码中，head为头指针，head指向的是首元结点，没有头结点。

前插法与后插法

        同样得到“1 2 3 4”，前插法需要输入“4 3 2 1”，后插法输入“1 2 3 4”.

        如果我们把第一个创建的结点称为第一结点。

        那么前插法便是将结点插入到第一结点的前面，而后插法就是将结点插入到第一结点的后面。

        

        本套代码便是后插法，多了一个尾指针q。

增

        正确代码

        下面我们展示一套代码往链表中插入‘6’。

#include<stdio.h>
#include<stdlib.h>struct node //定义链表
{int data;struct node *next;
};int main()
{struct node *head=NULL, *p=NULL, *q=NULL, *t=NULL;int i,n,a;scanf("%d",&n);head =NULL;for ( i = 0; i < n; i++)  //将数据存入链表{scanf("%d",&a);p=(struct node *)malloc(sizeof(struct node));  //分配动态内存，给p分配一个地址p ->data=a;                                    //将a存入这个地址p->next=NULL;                                  //分配下一个节点if (head ==NULL)        //如果这是创建的第一个节点，则将头指针指向这个节点，理解为火车头{head=p;}else                    //不是第一个节点,就与上一个节点连接，就是连接车厢，如果上节车厢为A，这节为B，那么就是把B连接到Aq->next=p;q=p;                    //保证下一个车厢连接的是B不是A}t=head;                              while(t!=NULL)  //将数据存入链表{if (t->next == NULL || t->next->data > 6 )         //此节点是结尾或下一个节点大于6      {p=(struct node *)malloc(sizeof(struct node));  //分配动态内存，给p分配一个地址p ->data=6;                                    //将6存入这个地址//******************* p->next=t->next;                               t->next=p;//*******************将存储6的节点插入链表break;}      t=t->next;  }t=head;while (t!=NULL){printf("%d ",t->data);//从火车头向后跑，把连接的车厢依次输出。t=t->next;}free(p);p=NULL;return 0;
}

这段代码与上一段代码就差了一段：（看注释理解）

    t=head;                              while(t!=NULL)  //将数据存入链表{if (t->next == NULL || t->next->data > 6 )         //此节点是结尾或下一个节点大于6      {p=(struct node *)malloc(sizeof(struct node));  //分配动态内存，给p分配一个地址p ->data=6;                                    //将6存入这个地址//******************* p->next=t->next;                               t->next=p;//*******************将存储6的节点插入链表break;}      t=t->next;  }

 野指针问题

        再写代码的时候出现了一个问题：（大家注意这段代码与前面的差别）

 t=head;                              while(t!=NULL)  //将数据存入链表{if ( t->next->data > 6 || t->next == NULL )         //此节点是结尾或下一个节点大于6      {p=(struct node *)malloc(sizeof(struct node));  //分配动态内存，给p分配一个地址p ->data=6;                                    //将6存入这个地址//******************* p->next=t->next;                               t->next=p;//*******************将存储6的节点插入链表break;}      t=t->next;  }

        没错！就是if条件的改变，把||两端的条件调换了位置。

        如果大家不能看出来什么问题，不妨试试输入：

情况一：

3

1 2 3 

情况二： 

3

1 2 8 

        看看这两套代码有什么区别。情况一中，两套代码结果一样。 而情况二，第一套代码中正常输入结果，而第二套代码中就没有了结果，代码‘崩’了。

        在解决问题之前，大家首先要知道‘||’这个符号的作用：（A || B），如果A为真，便不会检查B了，情况二中，把“t->next->data > 6”放在了后面，运行中发现“t->next == NULL”为真，便不会执行“t->next->data > 6”了，而第二套代码会先执行“t->next->data > 6”。

        这就会导致野指针的问题出现。与下面这套代码相似：

#include<stdio.h>
#include<stdlib.h>int main()
{int *p;printf("%d",p);printf("这个不会输出！");return 0;
}

 造成这个原因就是*p是野指针，它指的是无效内存！具体原因参考博客：【C语言基础】野指针与空指针_野指针和空指针-CSDN博客

删

        删除6

    t=head; while (t!=NULL){if (t->next->data == 6){p=t->next;t->next=t->next->next;free(p);//释放删除节点空间}t=t->next;}

改

        将6改为7

    t=head; while (t!=NULL) //改{if (t->data == 6){t->data = 7;}t=t->next;}

查

        查找6在链表的哪一个节点。

    int s=1;t=head; while (t!=NULL) //查{if (t->data == 6){printf("在链表的第%d个节点\n",s);break;}s++;t=t->next;}

拓展

        模拟链表

        使用数组来实现链表，叫做模拟链表。通过两个数组实现，数值data[]存每个数，另一个right[]我认为可以理解为存储的下一个节点的地址，不过是是用序号来模拟地址。

        

        例如，data[1]地址是1，他的right是right[ 1 ]为2，即下一个节点的地址是2；

        我们把“6”插入，只需达到data[10]=6,'6'的地址是10，在5的右边现在的地址right[3]是4，改为10即可，将right[10]存为8的地址‘4’。

示例代码 

#include <stdio.h>int main()
{int data[101]={0},right[101]={0};int i=0,n=0,t=0,len=0;scanf("%d",&n);  //初始链表的个数for ( i = 1; i <= n; i++){scanf("%d",&data[i]); // 存入链表每个节点的数据}len=n;for (i = 0; i <=n; i++) //存入链表每个节点的模拟地址{if (i!= n){right[i]=i+1;}elseright[i]=0;}// 直接在数组data末尾增加一个数len++;scanf("%d",&data[len]);// 从链表头部开始遍历t=1;while (t!=0){if (data[right[t]]>data[len])//找到要插入的地方{right[len]=right[t];right[t]=len;break;}t=right[t]; //不能写t++}t=1;while (t!=0){printf("%d ",data[t]);t=right[t];}return 0;
}

循环链表

        与循环队列相似，整个链表形成一个环，由此从表中的任一结点出发均可找到表中其它结点。

        循环链表的操作与单链表一致，差别仅在于：当链表遍历时判别当前指针p是否向表尾结点的终止条件不同。在单链表中，判别条件为p！=NULL或 P->next ！=NULL，而循环链表的为p

!=NULL或p->next !=NULL。

       我们还可以将两个或者多个链表连接在一起。将第一个表的尾指针指向第二个表的第一个结点，将第二个尾指针连接在第一链表的第一个结点就构成了一个循环链表。

        p= B->next->next;//B的第一个结点

        B->next = A->next;

        A -> next =p;

        时间复杂度为

双向链表 

        双向链表就是一个结点具有两个指针域，一个指向前结点，一个指向后结点。

struct node //定义链表
{int data;struct node *next;struct node *prior;
};

        双向链表的插入和删除需同时修改两个方向的指针。 

参考文章

C++——STL标准模板库——容器详解——stack+queue_stl栈-CSDN博客