第四节 数据结构基础（1）栈，队列和链表

  接下来的章节会介绍简单的数据结构，包括线性表（栈、队列、链表等）、二叉树和图。这些这些内容可能在我们今后要学习的算法中经常出现，都是需要去掌握的概念和内容。如果数据结构的基础没有打好，那么我们就很难设计出准确、高效的算法。

  这一节我们要介绍三个基础的概念，栈、队列和链表。他们是最简单、最基础，同时也是最常用的数据结构。他们同属于线性表：n（n>=0）个具有相同属性（数据类型一致）的数据元素的有限序列。我们之前学习过的数组，就是经常用来记录线性表的一种常用工具。

栈（Stack）

  栈是一种运算受到限制的线性表，它的插入和删除操作都只能在同一端进行。如果非要在生活中举个例子的话，那么栈的话，就像是一桶薯片。无论是拿出一片还是放进去一片，都只能从一个口里进行。这个口我们称之为栈顶（Top）。这样的规定会让先进去的元素后出来，我们称之为先进后出。（FILO）

  向栈顶插入新元素成为入栈，反之为出栈。栈的存储结构的C语言表述为：

1
2
3
4
5
typedef struct
{
	int a[N];
	int top;
}SeqStack;

  栈为空时，我们将Top赋值-1；非空时，我们将可以使用下标0以上的元素。类似的表述方式我们在之前讲过的二分法中提到过。当存入一个元素或取出一个元素时，我们对结构体中的top进行相应的自增和自检，记录当前栈顶的位置。

  我们在处理先进后出的问题时，推荐使用栈。比如，我们在进行进制换算时，将十进制转为八进制需要进行多次相除求余数。算出来的数越早，它的位置就越低。比如：十进制数字1835转化为八进制需要除以四次才能将商变为0，得到的余数分别为3 5 4 3，转化为十进制就是3453。所以对于这种问题来说，使用栈来存储计算结果是再好不过的了，我们不需要对存入的数据进行反转再输出。

  令人可喜的是，在C++的STL中给我们提供了栈这种容器，我们在使用的时候不需要再用语言来构造出来这种结构以及对这种结构的操作函数了。以后介绍的数据结构中，我们也会提到相应的STL。

头文件： #include “stack”
声明方法：stack<类型> s;
成员函数：
    s.push(x)  无返回值，将元素x压栈
    s.pop();  退栈，无返回值
    s.top();  取栈顶元素，返回栈顶元素
    s.empty();  判断栈是否为空，如果是空，返回1，否则返回0
    s.size();  返回栈中元素的个数

  大家可以思考一下怎么把栈里所有的元素打印出来，也可以试着做一下上面的进制转换问题。

队列（Queue）

  刚刚我们提到的栈，是一种先进后出的线性表，那么这里的队列也是线性表的一种，不过是先进先出（FIFO）型的。我想这个名字应该比较形象，就像我们在超市排队付款一样，先到的先来。我们把允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front），没有元素的队列称为空队列。元素的插入和删除分别称为入队和出队。

  为了便于理解，我们来看一下队列的的存储结构吧。

1
2
3
4
5
typedef struct
{
	int a[N];
	int rear,front;
}SeQueue;

  我们看，它的结构和栈类似，但是在结构中比栈多了一个用来表示不同出口的“指针”。在空队列时，两个“指针”的初值都为-1。当有入队操作时，我们的队尾（rear）就要进行自增；有出队操作时，队头（front）自增。（思考一下为什么会这样）

  经过这样的操作，我们的队列可能会浪费很多的存储空间，所以在常用的队列存储方式中，我们经常使用首尾相连的数据结构，这就变成了一个“循环队列”。当然，我们的STL为我们已经做好了一切，我们只要用就好了。

头文件：#include “queue”
声明方式：queue Q;
常用成员函数：
    Q.push()  入队
    Q.size()  返回队列中元素的个数
    Q.front()  显示队头元素
    Q.back()  显示最后一个元素
    Q.pop()  出队
    Q.empty()  判断队列是否为空，如果是空，返回1，否则返回0

链表（List）

  用数组存储的元素具有空间上的连续性。那么如果我们需要一个逻辑上联系很紧密的结构，比如说树或者是图的话，就有可能要使用链表了。这里只是简单介绍一下链表的概念和基本类型，在后面我们会具体研究这种重要的数据结构。

  首先我们来看一个链表节点的存储结构：

1
2
3
4
5
typedef struct Node //结点类型定义
{
	int data;
	struct Node *next;
}LinkList;

  我们看，在定义链表节点的时候，我们使用了一个类似于递归的方法，不过我们发现，它存放的是下一个结点的指针。我们来看一下简单的单链表的结构吧。

结点结构：

┌───┬───┐

│data │next │

└───┴───┘

链表结构：

  除了单链表，还有我们刚刚提到过的队列要用到的循环链表以及双链表、静态链表等。下一节我们将对链表进行专门的研究。比起线性表，除了链表的结构关系比较强之外，还能提高存储空间的利用率。链表的存储密度小、存储内存随机。但是在查找的时候，链表必须按照顺序。所以我们应该根据需求来选择相应的数据结构。

  理解了链表的结构之后，我们并不需要像在上数据结构课的时候那样搞得那么清楚，同样，会使用STL中的链表就可以了。

头文件：#include “list”
声明方式：
    list l; //空链表
    list l(3); //长度为3的链表
    list l2(3,4); //有两个确定元素的链表

常用成员函数：
push_front/pop_front和push_back/pop_back
在开头和结尾插入或删除元素

begin() 返回指向第一个元素的迭代器
end() 返回末尾的迭代器
sort() 对链表中的数据进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>   
#include <list>   
#include <numeric>   
#include <algorithm>   
using namespace std;   
  
//创建一个list容器的实例LISTINT   
typedef list<int> LISTINT;   
//创建一个list容器的实例LISTCHAR   
typedef list<int> LISTCHAR;   
  
void main()   
{   
    //用list容器处理整型数据    
    //用LISTINT创建一个名为listOne的list对象   
    LISTINT listOne;   
    //声明i为迭代器   
    LISTINT::iterator i;   
      
    //从前面向listOne容器中添加数据   
    listOne.push_front (2);   
    listOne.push_front (1);   
      
    //从后面向listOne容器中添加数据   
    listOne.push_back (3);   
    listOne.push_back (4);   
      
    //从前向后显示listOne中的数据   
    cout<<"listOne.begin()--- listOne.end():"<<endl;   
    for (i = listOne.begin(); i != listOne.end(); ++i)   
        cout << *i << " ";   
    cout << endl;   
      
    //从后向后显示listOne中的数据   
    LISTINT::reverse_iterator ir;   
    cout<<"listOne.rbegin()---listOne.rend():"<<endl;   
    for (ir =listOne.rbegin(); ir!=listOne.rend();ir++) {   
        cout << *ir << " ";   
    }   
    cout << endl;   
      
    //使用STL的accumulate(累加)算法   
    int result = accumulate(listOne.begin(), listOne.end(),0);   
    cout<<"Sum="<<result<<endl;   
    cout<<"------------------"<<endl;   
      
    //--------------------------   
    //用list容器处理字符型数据   
    //--------------------------   
      
    //用LISTCHAR创建一个名为listOne的list对象   
    LISTCHAR listTwo;   
    //声明i为迭代器   
    LISTCHAR::iterator j;   
      
    //从前面向listTwo容器中添加数据   
    listTwo.push_front ('A');   
    listTwo.push_front ('B');   
      
    //从后面向listTwo容器中添加数据   
    listTwo.push_back ('x');   
    listTwo.push_back ('y');   
      
    //从前向后显示listTwo中的数据   
    cout<<"listTwo.begin()---listTwo.end():"<<endl;   
    for (j = listTwo.begin(); j != listTwo.end(); ++j)   
        cout << char(*j) << " ";   
    cout << endl;   
      
    //使用STL的max_element算法求listTwo中的最大元素并显示   
    j=max_element(listTwo.begin(),listTwo.end());   
    cout << "The maximum element in listTwo is: "<<char(*j)<<endl;   
}