链栈是借用单链表实现的栈。其不同于顺序栈之处在于:
1、链栈的空间是程序运行期间根据需要动态分配的，机器内存是它的上限。而顺序栈则是
静态分配内存的。
2、链栈动态分配内存的特性使得它一般无需考虑栈溢出的问题。
链栈的的组织结构如下图所示。容易发现其是架构的单链表的基础之上的。
下面介绍下我用C++实现的链栈，VC6下调试。
1、文件的组织结构
2、ls.h链栈类的说明
#ifndef _LS_H_
#define _LS_H_ typedef int dataType; struct node //链栈节点
{
dataType data; //数据域
node *next; //指针域
}; class ls
{
public:
ls();
~ls();
void push(dataType var); //压栈
void pop(); //出栈.出栈之前并不判断栈是否已空.需要通过isEmpty()判断
dataType stackTop(); //取栈顶元素,栈顶无变化.不提前判断栈是否为空
bool isEmpty(); //判空.空返回true,反之返回false
//bool isFull(); //判满.链栈是动态分配内存空间的,无需判满 private:
node *top; //栈顶指针.top=NULL表示为空栈
}; #endif
3、ls.cpp链栈类成员函数的定义
#include <iostream>
#include "ls.h"
using namespace std; ls::ls()
{
top = NULL; //top=NULL表示链栈为空
} ls::~ls()
{
node *ptr = NULL; while(top != NULL) //循环释放栈节点空间
{
ptr = top->next;
delete top;
top = ptr;
}
} void ls::push(dataType var)
{
node *ptr = new node; ptr->data = var; //新栈顶存值
ptr->next = top; //新栈顶指向旧栈顶 top = ptr; //top指向新栈顶
} void ls::pop()
{
node *ptr = top->next; //预存下一节点的指针
delete top; //释放栈顶空间
top = ptr; //栈顶变化
} dataType ls::stackTop()
{
return top->data; //返回栈顶元素,并不判断栈是否已空
} bool ls::isEmpty()
{
return top == NULL; //栈顶为NULL表示栈空
}
4、main.cpp
#include <iostream>
#include "ls.h"
using namespace std; int main()
{
ls exp;
int i = 0; for(i=0;i<3;++i)
{
exp.push(i);
} for(i=0;i<3;i++)
{
if(!exp.isEmpty())
{
cout<<exp.stackTop()<<endl;
exp.pop();
}
} return 0;
}