本文共 3173 字，大约阅读时间需要 10 分钟。

何为栈？

栈(Stack)是一种线性存储结构，它具有如下特点：

栈中的数据元素遵守“先进后出”(First In Last Out)的原则，简称FILO结构。限定只能在栈顶进行插入和删除操作。

栈的相关概念与操作

1.栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

ps：压栈的过程中，栈顶为位置一直在向上移动，而栈底是固定不变的。

栈是一种线性结构，能以数组或链表作为底层数据结构来实现。

基于数组的栈实现

通常以数组头为栈底，数组尾为栈顶。

/*栈的抽象数据类型*/template 
   
    class ArrayStack{public:    //初始化，指定模拟栈的容量　和　目前大小    ArrayStack(int s,int a=0):maxsize(s),count(a) {}    //~ArrayStack();public:    T top();                //获取栈顶元素    void push(T a);         //压栈    T pop();                //弹栈    bool isEmpty();         //判断是否为空    int size();             //栈的大小private:    int count;      //栈的元素数量    int maxsize;    //栈的容量    T  array[10];   //底层数据结构为数组};
   

具体实现

template 
   
    bool ArrayStack
    
     ::isEmpty()       //栈的判空{    return count==0;  };template 
     
      int ArrayStack
      
       ::size()           //栈的大小{    return count;};template 
       
        void ArrayStack
        
         ::push(T a) //压栈{ if(count != maxsize) array[count++] = a;};template 
         
          T ArrayStack
          
           ::pop() //弹栈{ if(count != 0) return array[--count];};template 
           
            T ArrayStack
            
             ::top() //获取栈顶元素{ if(count != 0) return array[count-1];};
            
           
          
         
        
       
      
     
    
   

主函数

int main(){    ArrayStack
   
     p(5);    for(int i=0; i<5; i++)        p.push(i);    cout << "栈的大小为：" << p.size() << endl;    cout << "栈顶元素：" << p.top() << endl;    cout << "依次出栈: " << endl;    while(!p.isEmpty())    {        cout << p.pop() << endl;    }    return 0;}
   

输出结果：

栈的大小为：5栈顶元素：4依次出栈: 43210

本例中指定栈的大小后就不支持扩容，栈满后就无法再进行压栈操作。

基于链表的栈实现

以链表头作为栈顶，方便结点的删除和插入，压栈后的新结点将一直出现在链表的头部。如下图所示，很清晰直观，不再啰嗦。

链表结点

/*链表结点，即栈中的元素*/template 
   
    struct Node{    Node(T t):value(t),next(NULL) {}    Node():next(NULL){}public:    T value;        //结点元素的值    Node
    
     * next;  //链表结点指针};
    
   

栈的抽象数据类型

/*基于链表的栈的ADT*/template 
   
    class LinkStack{
   public:    //构造函数    LinkStack(int icount=0):count(icount) {}    //几种操作    bool isEmpty();    int size();    void push(T t);    T pop();    T top();private:    Node
    
     * phead; //头指针    int count;      //栈中元素的数量};
    
   

具体实现

/*返回栈的大小*/template 
   
    int LinkStack
    
     ::size(){    return count;};template 
     
      bool LinkStack
      
       ::isEmpty(){    return count==0;};template 
       
        void LinkStack
        
         ::push(T t){ Node
         
           *pnode = new Node
          
           (t); pnode -> next = phead -> next; phead -> next = pnode; count++;};template 
           
            T LinkStack
            
             ::pop(){ if(phead-> next != NULL) { Node
             
              * pdel = phead -> next; phead -> next = pdel -> next; T value = pdel -> value; delete pdel; count--; return value; }};template 
              
               T LinkStack
               
                ::top(){ if(phead -> next != NULL) return phead -> next -> value;};
               
              
             
            
           
          
         
        
       
      
     
    
   

上面具体操作的实现和基于数组的相似~

主函数实例

int main(){    LinkStack 
   
     lstack;    lstack.push("!!!");    lstack.push("linux");    lstack.push("hello");    cout << "栈的大小：" << lstack.size() << endl;    cout << "栈顶元素: " << lstack.top() << endl;    cout << "栈元素：" << endl;    while(!lstack.isEmpty())    {        cout << lstack.pop() << endl;    }    cout << "栈的大小：" << lstack.size() << endl;    return 0;}
   

　　本文简单的介绍了一下栈的相关概念，主要是用C++模板实现基于数组和链表的栈，希望对大家有所帮助。

转载地址：http://fluoi.baihongyu.com/