链栈及（C++）实现

链栈的建立是基于链表而不是数组。基于链表的栈相对于基于数组的栈提供了两个优点：

• 不需要指定栈的起始大小。链栈只需要从一个空的链表开始，然后每次压入一个值时即扩展一个结点；
• 只要系统具有足够的可用内存，链栈将永远不会满。

本节将可以看到一个链栈类 DynlntStack，该类的声明如下所示：

//DynIntStack.h 的内容
class DynlntStack
{
    struct StackNode
    {
        int value;
        StackNode *next;
        // Constructor
        StackNode(int value1, StackNode *next1 = nullptr)
        {
            value = value1; next = next1;
        }
    };
    StackNode *top;
  public:
    DynlntStack() { top = nullptr; }
    ~DynlntStack();
    void push(int);
    void pop(int &);
    bool isEmpty() const;
    // Stack Exception
    class Underflow {};
};

StackNode 类是链表中每个结点的数据类型。因为在链表的开始处添加和删除项目都很容易，所以将链表的开头作为栈顶，并使用 top 指针指向链表中的第一个结点。这个指针被栈构造函数初始化为 nullptr，表示栈被创建为空。链栈没有静态分配的数组要填充，所以不会有溢出的异常。但是，该类会定义一个 underflow 异常，当 pop 函数被调用而栈为空时就会抛出该异常。

DynIntStack 栈类的成员函数如下所示：

//DynIntStack.cpp 的内容
#include <iostream>
#include "DynIntStack.h"
#include <cstdlib>
using namespace std;
void DynIntStack::push(int num)
    top = new StackNode(num, top);
}
void DynIntStack::pop(int &num)
{
    StackNode *temp;
    if (isEmpty()) { throw DynIntStack::Underflow(); }
    else {
        // Pop value off top of stack
        num = top->value;
        temp = top;
        top = top->next;
        delete temp;
    }
}
bool DynIntStack::isEmpty() const
{
    return top == nullptr;
}
DynIntStack::~DynIntStack()
{
    StackNode * garbage = top;
    while (garbage != nullptr)
    {
        top = top->next;
        garbage->next = nullptr;
        delete garbage;
        garbage = top;
    }
}

push 函数特别简单。它只是创建一个新的结点，结点的值就是要 push 到栈上的数字，其后继指针是当前栈顶的结点，然后使新创建的结点成为栈的新顶部：

top = new StackNode(num, top);

请注意，即使栈在 push 操作之前为空，以上语句也能正常工作，因为在这种情况下，栈顶部新结点的后继指针将被正确设置为 nullptr。

接下来看一看 pop 函数。就像 push 函数必须在链表头部插入结点一样，pop 函数也必须删除链表头部的结点。首先，该函数调用 isEmpty 来确定栈中是否有任何结点。如果没有，则拋出一个异常：

if (isEmpty())
{
    throw DynlntStack::Underflow();
}

如果 isEmpty 返回 false，则执行以下语句：

else //弹出栈顶的值
{
    num = top->value;
    temp = top;
    top = top->next;
    delete temp;
}

首先，栈顶结点的 value 成员的副本将保存在 num 引用形参中，然后临时指针 temp 被设置为指向要删除的结点，即当前位于栈顶的结点。接下来将 top 指针设置为指向当前栈顶结点之后的结点。如果当前位于栈顶的结点之后没有结点，则相同的代码会将 top 设置为 nullptr，然后就可以通过临时指针安全地删除栈顶结点。

下面的程序是一个驱动模块程序，它演示了 DynlntStack 类：

// This program demonstrates the dynamic stack class DynIntStack.
#include <iostream>
#include "DynIntStack.h"
using namespace std;

int main()
{
    DynIntStack stack;
    int popped_value;
    // Push values 5, 10, and 15 on the stack
    for (int value = 5; value <= 15; value = value + 5)
    {
        cout << "Push: " << value << "\n";
        stack.push(value);
    }
    cout << "\n";
    // Pop three values
    for (int k = 1; k <= 3; k++)
    {
        cout << "Pop: ";
        stack.pop(popped_value);
        cout << popped_value << endl;
    }
    // Stack is now empty, a pop will cause an exception
    try
    {
        cout << "\nAttempting to pop again...";
        stack.pop(popped_value);
    }
    catch (DynIntStack::Underflow)
    {
        cout << "Underflow exception occured.\n";
    }
    return 0;
}

程序输出结果：

Push: 5
Push: 10
Push: 15

Pop: 15
Pop: 10
Pop: 5
Attempting to pop again...Underflow exception occurred.

该程序将创建一个栈并且将 3 个值压入该栈，所有这 3 个值随后又被弹出栈并打印。第 4 次（最后一次）调用 pop 执行出栈操作时，栈已经是空的了，所以拋出了一个异常。程序会捕获异常和打印一条消息。