《C++多线程编程实战》——1.9 链表、队列和栈示例ifndef _QUEUE _define _QUEUE _include "CList.h"endif` include include "CQueue.h"include "CStack.h"include include "CList.h"

本节书摘来自异步社区出版社《c++多线程编程实战》一书中的第1章，第1.9节，作者： 【黑山共和国】milos ljumovic（米洛斯 留莫维奇），更多章节内容可以访问云栖社区“异步社区”公众号查看。

下面的示例将演示线性链表（可包含任何泛型类型t）的oop用法。该示例背后的思想是把继承作为表示“b是一种a”这种关系的模型。

线性链表是一种线性排列元素的结构，第1个元素链接第2个元素，第2个元素链接第3个元素，以此类推。线性链表的基本操作是，在线性链表中插入元素（put）和获取元素（get）。队列是一种线性链表，其中的元素按先进先出的次序排列，即fifo（first in first out）。因此，从队列的顶部获取元素，从队列的底部插入新元素。栈也是一种线性链表，从栈中获取元素的顺序与放入元素的顺序相反，也就是说，栈中的元素按先进后出的次序排列，即lifo（last in first out）。

线性链表是按顺序排列的元素集合。每个链表都有用于设置元素值、从链表获取元素或简单查看元素的方法。链表可储存任何类型的对象。但是，为了满足链表类、队列和栈的特殊化，线性链表定义了插入元素和获取元素的精确位置。因此，作为泛化对象的链表是一个基类。

读者应该意识到，以这种方式设计的链表可实现为静态结构或动态结构。也就是说，这种链表可以实现为某种数组或结构，其中的各元素通过指针与相邻的元素链接。用指针来实现，可操作性强。

下面的示例中，将把线性链表实现为指针集合，这些指针指向用链表中的方法放置在链表中的原始对象。这样设计是为了实现链表元素的多态性，而不是把原始对象拷贝给链表。从语义上来看，这需要把更多的精力放在设计上。

准备就绪

确定安装并运行了visual studio。

操作步骤

执行以下步骤。

1．创建一个新的空c++控制台应用程序，名为<code>linkedlist</code>。

2． 添加一个新的头文件<code>clist.h</code>，并输入下面的代码：

template

class cqueue : clist

{

public:

　　cqueue() : clist(){ }

　　cqueue(t* telement) : clist(telement){ }

　　virtual ~cqueue(){ }

　　virtual void enqueue(t* telement)

　　{

　　　　append(head(), telement);

　　}

　　virtual t* dequeue()

　　　　t* telement = getfirst();

　　　　remove(telement);

　　　　return telement;

　　virtual t* peek()

　　　　return getfirst();

　　clist::count;

protected:

　　cqueue(const cqueue&amp; cqueue);

　　cqueue&amp; operator = (const cqueue&amp; cqueue);

};

4．类似地，再创建<code>cstack</code>。右键单击【头文件】，创建一个新的头文件<code>cstack.h</code>，并输入下面的以下代码：

using namespace std;

int main()

　　cqueue* cqueue = new cqueue();

　　cstack* cstack = new cstack();

　　for (int i = 0; i &lt; 10; i++)

　　　　cqueue-&gt;enqueue(new int(i));

　　　　cstack-&gt;push(new double(i / 10.0));

　　cout &lt;&lt; "queue - integer collection:" &lt;&lt; endl;

　　for (; cqueue-&gt;count();)

　　　　cout &lt;&lt; *cqueue-&gt;dequeue() &lt;&lt; " ";

　　cout &lt;&lt; endl &lt;&lt; endl &lt;&lt; "stack - double collection:" &lt;&lt; endl;

　　for (; cstack-&gt;count();)

　　　　cout &lt;&lt; *cstack-&gt;pop() &lt;&lt; " ";

　　delete cqueue;

　　delete cstack;

　　cout &lt;&lt; endl &lt;&lt; endl;

　　return system("pause");

}<code>`</code>

示例分析

首先，解释一下<code>clist</code>类。为了更方便地处理，该链表由<code>cnode</code>类型的元素组成。<code>cnode</code>类有两个特征：<code>telement</code>指针（指向用户自定义的元素）和<code>next</code>指针（指向链表下一个项）；实现了两个方法：<code>element</code>和<code>next</code>。<code>element</code>方法返回当前元素地址的指针，<code>next</code>方法返回下一个项地址的引用。

从文字方面看，构造函数称为<code>ctor</code>，析构函数称为<code>dtor</code>。<code>clist</code>的默认构造函数是公有函数，创建一个空的链表。第2个构造函数创建一个包含一个开始元素的链表。具有动态结构的链表必须有析构函数。<code>append</code>方法在链表的末尾插入一个元素，也是链表的最后一个元素。<code>count</code>方法返回链表当前的元素个数。head方法返回链表开始节点的引用。

<code>getfirst</code>方法返回链表的第1个元素，如果链表为空，则返回<code>null</code>。<code>getlast</code>方法返回链表的最后一个元素，如果链表为空，则返回<code>null</code>。<code>getnext</code>方法返回链表的下一个项，即相对于地址由t*<code>telement</code>参数提供的项的下一个项。如果未找到该项，<code>getnex</code>方法返回<code>null</code>。

<code>find</code>方法显然是一个高级特性，针对未定义类型t和未定义的<code>function</code>方法（带<code>tparameter</code>参数）设计。假设要使用一个包含学生对象的链表，例如迭代数据（如，使用<code>getnext</code>方法）或查找某个学生。如果有可能为将来定义的类型实现一个返回<code>unsigned long</code>类型（<code>dword</code>）的方法，而且该方法要把未知类型数据与<code>dwvalue</code>参数做比较，应该怎么做？例如，假设要根据学生的id找出这名学生，可以使用下面的代码：

dword predicate(int* ielement)

　　return (dword)(*ielement);

}

　　clist* list = new clist();

　　list-&gt;insert(new int(1));

　　list-&gt;insert(new int(2));

　　list-&gt;insert(new int(3));

　　int* ielement = list-&gt;find(predicate, 2);

　　if (ielement != null)

　　　　// 找到ielement

　　return 0;

回到我们的示例。为何要把拷贝构造函数和<code>perator=</code>都声明为<code>protected？</code>要知道，我们在这里实现的链表中储存着指针，而这些指针指向那些在链表外的对象。如果用户能随意（或无意）地通过拷贝构造函数或=运算符来拷贝链表，会非常危险。因此，要把把拷贝构造函数和=运算符设置为protected，不让用户使用。为此，必须先把两个函数声明为<code>protected</code>，然后在需要时再实现它们；否则，编译器在默认情况下会把这两个函数设置为<code>public</code>，然后逐个拷贝指针，这样做是错误的。把它们声明为<code>private</code>也不够。在这种情况下，<code>clist</code>基类的派生类依旧会遇到同样的问题。派生类仍需要要把拷贝构造函数和=运算符声明为<code>protected</code>，否则编译器还是会把这些方法默认生成<code>public</code>。如果基类包含拷贝构造函数和=运算符，派生类就会默认调用它们，除非派生类能显式调用自己的版本。但是，我们的初衷是让派生类用上<code>clist</code>基类中的拷贝构造函数和=运算符，所以将其声明为<code>protected</code>。

<code>clist</code>类的<code>private</code>部分包含了把链表实现为线性链表所需的对象。这意味着链表中的每个元素都指向下一个元素，头节点指向第1个元素。

<code>cqueue</code>和<code>cstack</code>类分别实现为队列和栈。不难看出，设计好<code>clist</code>基类以后（尤其是设计了<code>enqueue</code>、<code>dequeue</code>、<code>push</code>、<code>pop</code>和peek方法），实现这两个类有多么简单。只要<code>clist</code>类设计得当，设计<code>cqueue</code>、<code>cstack</code>，甚至其他类都非常简单。