链式栈

定义：栈是一种后进先出的线性表或者说是只允许在表的末端进行插入和删除的线性表。

栈有顺序栈（基于数组的存储表示实现）和链式栈（基于链表的存储实现）。

这里实现的是链式栈，链式栈的栈顶是链表的表头，新节点的插入删除均在栈顶（表头）进行。

  1 #include<iostream>
  2 using namespace std;
  3 
  4 typedef int dataType;
  5 
  6 struct Node                //链栈节点
  7 { 
  8     dataType data;            //数据域
  9     Node *next;               //指针域
 10 };
 11 
 12 class LinkedStack 
 13 {
 14 public:
 15     LinkedStack();             //构造函数 
 16     ~LinkedStack();              //析构函数 
 17     void push(dataType var); //压栈
 18     void pop();              //出栈.出栈之前并不判断栈是否已空.需要通过isEmpty()判断
 19     dataType getTop();     //取栈顶元素,栈顶无变化.不提前判断栈是否为空
 20     bool isEmpty();          //判空.空返回true,反之返回false
 21     int getSize();
 22     void makeEmpty();
 23 
 24 private:
 25     Node *top;               //栈顶指针.top=NULL表示为空栈
 26 };
 27 
 28 LinkedStack::LinkedStack()
 29 {
 30     top = NULL;
 31 }
 32 
 33 LinkedStack::~LinkedStack()
 34 {
 35     makeEmpty();
 36 }
 37 
 38 void LinkedStack::push(dataType var) 
 39 {
 40     Node *p = new Node;            //首先新建一个结点 
 41     
 42     p->data = var;                //添加data域 
 43     p->next = top;                //链接栈 
 44     
 45     top = p;                     //更新栈顶指针 
 46 }
 47 
 48 void LinkedStack::pop()
 49 {
　　　　 if(IsEmpty() == true) return false;   //出栈时必须要考虑栈是否为空
 50     Node *p = top;                
 51     top = top->next;            //把栈顶指针向前移一位 
 52     delete p;                    //删除原来的栈顶指针 
 53 }
 54 
 55 dataType LinkedStack::getTop()
 56 {
 57     dataType k = top->data;
 58     return k;
 59 }
 60 
 61 bool LinkedStack::isEmpty()
 62 {
 63     return top == NULL;            //如果栈顶指针为空，则栈为空 
 64 }
 65 
 66 int LinkedStack::getSize()
 67 {
 68     Node *p = new Node;
 69     p = top;
 70     int count = 0;
 71     while(p!=NULL){                //遍历栈 并计数，返回计数值 
 72         count++;
 73         p = p->next;
 74     }
 75     return count;
 76 }
 77 
 78 void LinkedStack::makeEmpty()
 79 {
 80     Node *p = NULL;
 81     while(top != NULL){            //遍历栈 逐个删除 
 82         p = top->next;
 83         delete top;
 84         top = p;
 85     }
 86 }
 87 
 88 int main()
 89 {
 90     LinkedStack exp;
 91     int i = 0;
 92 
 93     for(i=0;i<3;++i)
 94     {
 95         exp.push(i);
 96     }
 97     cout<<"栈的大小为："<<exp.getSize()<<endl;
 98 //    exp.makeEmpty();
 99     for(i=0;i<3;i++)
100     {
101         if(!exp.isEmpty())
102         {
103             cout<<exp.getTop()<<endl;
104             exp.pop();
105         }
106     }
107     cout<<"栈的大小为："<<exp.getSize()<<endl;
108 
109     return 0;
110 }

运行截图：