栈

栈定义

后进先出
主要操作：进栈出栈
应用：表达式求值消除递归深度优先搜索

不存在这样的输入序列i,j,k，能同时满足入栈顺序为i,j,k 和出栈顺序为 k,i,j

栈实现

　　1. 顺序实现

　　注意使用向量尾部作为栈顶，存在上溢下溢问题；

　　2. 链式实现

　　使用单链表存储，指针方向是从栈顶方向向下链接；

#include<iostream>
using namespace std;

template <class T>
class Stack{
    public:
        void  clear();
        bool  push(const T item);
        
        bool pop(T& item);
        bool top(T& item);
        bool isEmpty();
        bool isFull();
};

View Code

顺序实现：

 1 template<class T> class arrStack:: pulic Stack<T> {
 2     private:
 3         int mSize;  //栈最多存放元素个数 
 4         int top;    //栈顶位置,应该小于mSize;
 5         T *st;
 6     public:
 7         arrStack(int size){
 8             mSize = size;
 9             top = -1;
10             st = new T[size]; 
11         }
12         arrStack(){
13             top =-1;
14         }
15         ~arrstack(){
16             delete [] st;
17         }
18         void clear(){   //清空栈 
19             top = -1;   
20         }
21 }
22 
23 bool arrStack<T>::push(const T item){
24     if(top == mSize-1){
25         cout<<"栈已满"<<endl;
26         return false; 
27     }else{
28         st[++top] = item;
29         return ture;
30     }        
31 } 
32 
33 bool arrStack<T>::pop(T &item){
34     if(top==-1){
35         cout<<"栈为空"<<endl;
36         return false; 
37     }else{
38         item = st[top--];
39         return true;
40     }
41 }

View Code

链式实现：

 1 template<class T> class InkStack:: pulic Stack<T> {
 2     private:
 3         Link<T>* top;
 4         int  size;
 5         
 6     public:
 7         InkStack(int defSize){
 8             top = NULL; size = defSize;
 9         }
10         ~InkSize(){
11             clear();
12         }    
13 }
14 
15 bool InkStack<T>::push(const T item){
16     Link<T>* temp = new Link<T>(item,top);
17     top = temp;
18     size++;
19     return true; 
20 } 
21 /*具有两个参数的Link构造函数
22 Link(const T info,Link* nextValue){
23     data = info; next = nextValue;
24 }*/ 
25 
26 bool InkStack<T>::pop(T &item){
27      Link<T> *temp;
28      if(size ==0) return false;
29      item = top->data;
30      temp = top->next;
31      delete top;
32      top = temp;
33      size--;
34      return true;
35 }

View Code

思考：

在STL中，pop函数仅仅将栈顶元素弹出，没有将其返回。STL的top函数与 pop函数为什么分开？