2013-08-30 20:58 

1876人阅读 

(0) 

 

          链栈是借用单链表实现的栈。其不同于顺序栈之处在于:

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;