栈的建立【包括入栈出栈显示】（基于单链表实现）

一般来说，c++有专门的STL，可以直接调用接口。怕自己忘记，我还是po出来了

C++标准库（STL）栈（stack）、队列（queue）、双向队列（deque）、容器（vector）的基本操作_云帆之路Tony的博客-CSDN博客

上面那个博客很赞很简洁，上面这些也不用刻意记，因为用多了自然熟。。。

顺序表建栈：栈的实现（顺序表实现）_inbSorryMaker的博客-CSDN博客

现在我们看看通过单链表建立栈的操作（如有问题请指正！）

目录

建立链式栈（声明）

清空栈

入栈

出栈（删除栈顶元素）

取栈顶元素（不删除栈顶元素）

输出栈所有元素（递归）

//基本栈的结构
template         //模板
class Stack {			//栈的类定义
public:
     Stack(){ };			//构造函数
     virtual void Push(E x) = 0;             //进栈
     virtual bool Pop(E& x) = 0;	     //出栈
     virtual bool getTop(E& x) = 0;	     //取栈顶
     virtual bool IsEmpty() = 0;	     //判栈空
     virtual bool IsFull() = 0;		     //判栈满
}；

建立链式栈（声明）

#include 
#include “stack.h”
template 
struct StackNode {                    //栈结点类定义
    E data;			          //栈结点数据
    StackNode *link;            //结点链指针
};  

template 
class linkedStack : public Stack { //链式栈类定义   
private:
	 StackNode *top;		            //栈顶指针
	 void output(ostream& os,StackNode  *ptr, int& i);
	//递归输出栈的所有元素
public:
     linkedStack() : top(NULL) {}	   //构造函数
	 ～linkedStack() { makeEmpty(); }   //析构函数
	 void Push(E x);		             	   //进栈
	 bool Pop(E& x);			   //退栈
     bool getTop(E& x) const;		//取栈顶  	
     bool IsEmpty() const { return top == NULL; }
     void makeEmpty();			//清空栈的内容
     int k = 1;
     void output(ostream& os, StackNode *ptr, int& i);
     friend ostream& operator << (ostream& os,linkedStack& s) 
     { output(os, s.top, k); }				//输出栈元素的重载操作 <<
};

清空栈

template 
linkedStack::makeEmpty() {	
//逐次删去链式栈中的元素直至栈顶指针为空。
    StackNode *p;
	while (top != NULL)		//逐个结点释放
        { p = top;  top = top->link;  delete p; }
};

入栈

template 
void linkedStack::Push(E x) {
//将元素值x插入到链式栈的栈顶,即链头。
    StackNode *next;
    next = new StackNode;	//创建新结点
    next->data=x;
    top=next;
    assert (top != NULL);		//创建失败退出
};

出栈（删除栈顶元素）

template 
bool linkedStack::Pop(E& x) {
//删除栈顶结点, 返回被删栈顶元素的值。
     if (IsEmpty() == true) return false;   //栈空返回
  	 StackNode *p = top;		//暂存栈顶元素
	 top = top->link;			//退栈顶指针
	 x = p->data;   delete p;		//释放结点
   	 return true;	
};

取栈顶元素（不删除栈顶元素）

template 
bool linkedStack::getTop(E& x) const {	
	 if (IsEmpty() == true) return false;   //栈空返回
	 x = top->data;                       //返回栈顶元素的值
     return true;
};

输出栈所有元素（递归）

template 
void linkedStack::output(ostream& os, StackNode *ptr, int& i) {
//递归输出栈中所有元素（沿链逆向输出）
	if (ptr != NULL) {
         if (ptr->link != NULL) 
              output(os, ptr->link, i++);//递归
         os << i << “ : ” << p->data << endl;	
                  //逐个输出栈中元素的值
	  }
};