算法7.链式栈// 07_链式栈.cpp : 此文件包含 main 函数。程序执行将在此处开始并结束。//#includeiostream#includestring#includestackusingnamespacestd;// 比较符号优先级的boolPriority(charch,chartopch){if((ch*||ch/)(topch||topch-))returntrue;if(topch(ch!))returntrue;returnfalse;}// 中缀表达式 后缀表达式stringMiddleToEndExpr(string expr){string result;stackchars;for(charch:expr){if(ch0ch9){result.push_back(ch);}else{for(;;){// 处理符号了if(s.empty()||ch(){s.push(ch);break;}// 比较当前符号ch和栈顶符号top的优先级chartopchs.top();// Priority:true ch topch false ch topchif(Priority(ch,topch)){s.push(ch);break;}else{s.pop();if(topch()// 如果遇见)一直出栈直到(break;result.push_back(topch);}}}}// 如果符号栈还存留符号直接输出到后缀表达式里面 /while(!s.empty()){result.push_back(s.top());s.pop();}returnresult;}intmain(){coutMiddleToEndExpr((12)*(34))endl;coutMiddleToEndExpr(2(46)/26/3)endl;coutMiddleToEndExpr(26/(4-2)(46)/2)endl;}#if0// 链式栈classLinkStack{public:LinkStack():size_(0){head_newNode;}~LinkStack(){Node*phead_;while(p!nullptr){head_head_-next_;deletep;phead_;}}public:// 入栈 O(1) 把链表头节点后面第一个有效节点的位置当作栈顶位置voidpush(intval){// head_ - 1// head_ - 2 - 1Node*nodenewNode(val);node-next_head_-next_;head_-next_node;size_;}// 出栈 O(1)voidpop(){if(head_-next_nullptr)throwstack is empty!;Node*phead_-next_;head_-next_p-next_;deletep;size_--;}// 获取栈顶元素inttop()const{if(head_-next_nullptr)throwstack is empty!;returnhead_-next_-data_;}// 判空boolempty()const{returnhead_-next_nullptr;}// 返回栈元素个数 遍历一遍链表记录节点个数O(n) 想达到O(1)intsize()const{returnsize_;}private:structNode{Node(intdata0):data_(data),next_(nullptr){}intdata_;Node*next_;};Node*head_;intsize_;};intmain(){intarr[]{12,4,56,7,89,31,53,75};LinkStack s;for(intv:arr){s.push(v);}couts.size()endl;while(!s.empty()){couts.top() ;s.pop();}coutendl;couts.size()endl;}#endif