在这篇文章里，我们来实现自定义的链式栈。首先我们来看看链式栈的结构及操作定义。
链式栈结构定义
首先，新建两个文件，分别为 mystack.h 和 mystack.cpp。在 mystack.h 中给出链式栈的结构定义及接口声明。
#ifndef _MYSTACK_H_
#define _MYSTACK_H_
#include <iostream>
using namespace std;
typedef char ELEMTYPE;
struct Node;
typedef struct Node *PNode;
struct Node {
ELEMTYPE info;
PNode link;
};
struct stStack {
PNode top;
size_t length;
};
typedef struct stStack *PLStack;
PLStack create();
bool destroy(PLStack *pstack);
bool print(PLStack pstack);
bool clear(PLStack pstack);
bool push(PLStack pstack, ELEMTYPE x);
bool pop(PLStack pstack);
bool top(PLStack pstack, ELEMTYPE *x);
bool isEmpty(PLStack pstack);
bool isFull(PLStack pstack);
#endif
从本次实验开始，我们使用 C++语言 的标准输入输出流进行程序的输入输出操作。
要使用 C++语言的标准输入输出流，我们需要在 mystack.h 头文件中加入如下语句：
#include <iostream>
using namespace std;
C++语言中头文件均不需要加 .h 作为后缀。iostream 头文件对C++语言的 I/O 流进行了定义及声明。此外，C++语言还引入了 命名空间 的概念，其本质上就是定义一个新的作用域，在该作用域范围内再定义类、变量及函数等，从而避免不同开发者因类、变量及函数命名同名而导致的冲突问题。
因为C++的标准输入输出流在 std 命名空间内进行定义，因此我们需要加入using namespace std;这条语句，以便引入 std 这个命名空间。
我们接下来解释一下 mystack.h 头文件中各数据结构及函数声明的含义。
首先，我们定义了两个结构体，分别是 struct Node 与 struct stStack 。其中 Node 结构用于表示链式栈中的节点，其包含数据域 info 以及指针域 link。而 stStack 结构体表示链式栈对象，其包含指向链式栈栈顶的 top 指针，以及表示链式栈包含节点元素个数的 length 变量。
其次，对于链式栈，我们定义其所能进行的操作如下：
- 创建栈 : create
- 销毁栈 : destroy
- 清空栈 : clear
- 打印栈元素 : print
- 元素入栈 : push
- 元素出栈 : pop
- 取栈顶元素 : top
- 判断栈是否为空 : isEmpty
- 判断栈是否为满 : isFull
当然对于链式栈而言，判满操作应该返回 true。我们在本文中给出该操作只是为了兼容性的目的。
链式栈接口实现
接下来我们依次来实现链式栈的各个接口。首先实现 create、 destroy 操作。
创建栈-create接口
创建栈接口原型如下所示：
PLStack create();
接口返回值为 PLStack 类型，该类型是 struct stStack 结构体指针，因此我们需要在接口中动态分配该结构体空间，并初始化该结构体。
由于 struct stStack结构体包含两个域：
- top 为链式栈节点指针，指向链式栈栈顶节点；
- length 为链式栈节点元素计数器，用于记录链式栈中当前节点元素个数；
初始化时，top 指针直接赋值为 NULL 即可，而由于初始化链式栈时，栈内无元素，因此 length 计数器直接置为 0 即可。以下是 create 接口的实现：
PLStack create()
{
PLStack pstack = (PLStack) malloc (sizeof(struct stStack));
if (pstack != NULL)
{
pstack->top = NULL;
pstack->length = 0;
return pstack;
}
return NULL;
}
销毁栈-destroy接口
接下来，我们来完成销毁栈的操作。因为是链式栈，元素在入栈时均需要分配新的节点空间用于存储栈元素。因此在销毁栈时，需要将其中每个节点的空间都释放掉。完成节点空间释放操作后，还需要将栈结构体(struct stStack)分配的空间也一并释放掉。
因此这两步操作可以分解为：
- 释放栈中所有节点(清空栈节点)；
- 释放栈结构体指针指向的内存空间；
其中第一步操作可以利用我们后续将实现的 clear 操作来完成，而释放栈结构体指针这直接使用 free 函数即可。以下给出销毁栈的接口实现：
bool destroy(PLStack pstack)
{
if (pstack == NULL)
{
return false;
}
clear(pstack);
free(pstack);
return true;
}
在销毁栈时，我们首先判断 pstack 指针是否为空，如果为空则不做任何操作。否则调用 clear 接口清空该栈，接着调用 free 函数释放 pstack 指针指向的内存空间。
我们在之前的文章中讲过，尽快使项目的原型运行起来，不要试图将所有代码编写完成后再进行编译。目前我们实现了 create 和 destroy两个接口，但由于在 destroy 接口中还调用了 clear 接口，因此我们先实现 clear 接口后再进行编译工作。
清空栈-clear接口
清空栈操作，需要依次将元素从栈顶逐个弹出(元素出栈，pop)，直到栈为空为止(isEmpty)。可见，在 clear 接口中我们还需要调用pop、isEmpty接口。以下给出 clear 接口的实现：
bool clear(PLStack pstack)
{
if (pstack == NULL)
{
return false;
}
while (!isEmpty(pstack))
{
pop(pstack);
}
return true;
}
判断栈是否为空-isEmpty接口
既然清空栈 clear 接口使用到了判断栈是否为空操作，我们接着实现 isEmpty 及 isFull 两个接口。
判断栈是否为空，可以根据以下两个情况：
- top 指针指向为空；
- length 计数器为 0；
以上两种情况均可用于判断栈是否为空。以下给出 isEmpty 接口的实现：
bool isEmpty(PLStack pstack)
{
if (pstack == NULL)
{
return true;
}
return (pstack->length == 0);
}
判断栈是否为满-isFull接口
判断栈是否未满，只有在顺序栈中才具有实际意义。链式栈因其节点均是在元素入栈时进行内存空间动态分配的。因此，此处给出的判满接口仅仅为了兼容性的需求。
bool isFull(PLStack pstack)
{
if (pstack == NULL)
{
return true;
}
return true;
}
元素出栈-pop接口
链式栈进行 pop 操作的示意图如下：
首先判断栈是否为空，若不为空则更新栈顶 top 指针，其次释放原栈顶元素内存空间(由 tmp 指针指向)，最后更新 length 计数器。
以下我们给出链式栈元素出栈操作的实现：
bool pop(PLStack pstack)
{
PNode p;
if (pstack == NULL)
{
return false;
}
if (!isEmpty(pstack))
{
return false;
}
p = pstack->top;
pstack->top = pstack->top->link;
pstack->length = pstack->length - 1;
free (p);
return true;
}
元素入栈-push接口
链式栈进行 push 操作的示意图如下：
首先尝试分配新节点空间用于新入栈元素，其次更新 top 指针指向新栈顶元素，最后更新 length 计数器。
据此，我们给出链式栈 push 操作接口的实现：
bool push(PLStack pstack, ELEMTYPE x)
{
if (pstack == NULL)
{
return false;
}
PNode p = (PNode) malloc (sizeof(struct Node));
if (p != NULL)
{
p->info = x;
p->link = pstack->top;
pstack->top = p;
pstack->length = pstack->length + 1;
return true;
}
return false;
}
注： 在 push 接口中，我们还应该考虑判断栈是否为满的情况(该情况在顺序栈中需要进行考虑)。
取栈顶元素-top操作
获取栈顶元素时，需要首先判断栈是否为空，只有栈不为空时才可获取栈顶元素，否则应返回操作失败。以下是 top 操作的函数声明：
bool top(PLStack pstack, ELEMTYPE *x);
需要引起我们注意的是，top 操作返回值为bool类型，也就是说栈顶元素并不通过函数返回值获取，而是通过参数 ELEMTYPE 指针类型返回。这样设计的原因很简单，因为当栈为空时，当然无法取得栈顶，从而通过 top 操作的返回值即可知道操作是否成功。
当 top 操作返回为true时，可以直接通过 ELEMTYPE *x获取到栈顶元素；但当 top 操作返回为false时，ELEMTYPE *x指针指向无意义的内存空间。
打印栈当前元素-print接口
在完成了链式栈的所有核心操作后，我们来完成帮助函数 print 接口的实现。 print 接口主要用于打印栈当前的所有元素，以便我们对栈的状态有所了解。它可以在建栈后、元素入栈、元素出栈、清空栈等操作前后进行调用，以方便我们通过输出结果观察、判断这些操作的业务逻辑是否正确。
如何实现 print 接口以及该接口需要输出什么信息，取决于你需要观察的栈状态信息。以链式栈为例，我除了需要知道当前栈中所有元素以及其在栈中的位置外，我还希望知道每个栈元素的内存地址。以下给出 print 接口的实现：
bool print(PLStack pstack)
{
PNode p;
size_t i;
char buffer[255];
if (pstack == NULL)
{
return false;
}
p = pstack->top;
i = length(pstack);
#ifdef DEBUG
cout << "--------- STACK ----------" << endl;
sprintf(buffer, "------- %ld ELEMENTS ---------", i);
cout << buffer << endl;
#endif
while (p != NULL)
{
sprintf(buffer, "%ld [%p] : %c", i, p, p->info);
cout << buffer << endl;
i--;
p = p->link;
}
#ifdef DEBUG
cout << endl;
#endif
return true;
}
在 print 接口中，我们通过一个 while 循环依次遍历从栈顶到栈底的所有元素，并将每个栈元素在栈中的 节点序号 、 节点结构体内存地址、 节点数据域均打印输出。
此外，在 print 接口中通过条件编译语句#ifdef、#endif语句用于在调试模式下额外输出更多信息。
测试链式栈各操作接口
在讲解 create、destroy 两个操作接口的过程中，我们将链式栈的剩余操作接口的实现思路及过程都做了详细的讲解。
与我们之前所说的 尽可能早的让程序跑起来 不同的事，这次实验过程中，我们依据每个接口的实现及嵌套调用关系依次实现了所有的接口。不过这并不影响我们后续的测试工作。
以下我们给出测试主文件 main.cpp的代码：
#include <iostream>
#include "mystack.h"
using namespace std;
int main ()
{
PLStack pstack;
ELEMTYPE x;
pstack = create();
push(pstack, 'a');
push(pstack, 'b');
push(pstack, 'c');
print(pstack);
while (!isEmpty(pstack))
{
top(pstack, &x);
cout << "stack top element: " << x << endl;
pop(pstack);
}
print(pstack);
destroy(pstack);
return 0;
}
在 main.cpp 中，我们对链式栈的绝大多数接口进行了测试，且 clear 接口在 destroy 接口中被调用。我们来看看编译后的运行结果：
[localhost@lab02:stack xgqin]$ ls
a.out main.cpp mystack.cpp mystack.h
[localhost@lab02:stack xgqin]$ vim mystack.cpp
[localhost@lab02:stack xgqin]$ g++ -DDEBUG main.cpp mystack.cpp
[localhost@lab02:stack xgqin]$ ./a.out
--------- STACK ----------
------- 3 ELEMENTS ---------
3 [0x7fc6ded00030] : c
2 [0x7fc6ded00020] : b
1 [0x7fc6ded00010] : a
stack top element: c
stack top element: b
stack top element: a
--------- STACK ----------
------- 0 ELEMENTS ---------
从运行结果结合 main.cpp 文件源码来看，链式栈的各操作接口均正常，但这并不能说明我们编写的代码没有问题，你可以尝试编写几个额外的测试用例对接口进行测试。
总结
在本文中，我们首先给出了链式栈结构的定义，并给出了需要实现的接口声明形式；其次，在各个不同接口中，我们通过嵌套调用等形式复用了不少接口，这需要大家对栈的逻辑结构保持清晰的概念；最后，我们通过一段测试代码，对所编写的程序进行了测试。
