栈的各种操作

落日映苍穹つ 2022-05-16 01:29 277阅读 0赞

> **栈（stack）又名堆栈，是仅允许在表的一端进行插入和删除运算。**  
> 表尾一端被称为**栈顶**，相对地，表头称为**栈底**。  
> Push：向一个栈插入新元素又称作进栈、**入栈**或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。  
> Pop：从一个栈删除元素又称作**出栈**或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

### 流程如下 ###

1.  **初始化**：初始化一个栈的大小为STACK\_SIZE，并且将容量size设置为STACK\_SIZE。
2.  **入栈操作**： 每次向栈中压入一个数据，此时top指针+1。直到栈满。当栈满时，再申请更多空间。
3.  **出栈操作**： 弹出栈顶数据，并且下移pop指针
4.  **清空栈**： 清空数据，但是不改变物理地址。只是改变指针。类似硬盘格式化，只是清空文件列表而不是重新覆盖。所以我们可以硬盘恢复。
5.  **销毁栈**： 完全释放掉栈占据的内存空间。和清空有本质区别。

--------------------

> 欢迎进一步交流本博文相关内容：  
>   
> 博客园地址 : [http://www.cnblogs.com/AsuraDong/][http_www.cnblogs.com_AsuraDong]  
>   
> CSDN地址 : [http://blog.csdn.net/asuradong][http_blog.csdn.net_asuradong]  
>   
> 也可以致信进行交流 : [xiaochiyijiu@163.com][xiaochiyijiu_163.com]  
>   
> **欢迎转载** , 但*请指明出处  :  )*

--------------------

## 代码实现 ##

#include<iostream>
    #include<cstddef>
    #include<cstdio>
    
    using namespace  std;
    typedef int ElemType;
    const int STACK_SIZE = 1;
    
    struct Stack{
        ElemType *base;
        ElemType *top;
        int size;
    };
    
    void InitStack(Stack *&s){
        s = new Stack ;
        s->base = new ElemType [STACK_SIZE];
        s->top  = s->base; // 刚开始的时候就是栈顶指向栈底
        s->size  =  STACK_SIZE;
    }
    
    void Push(Stack *&s,ElemType e){
        //如果栈满，动态增容，容量增大STACK_SIZE 
        if(s->top-s->base >= s->size ){
            //s->base = (ElemType *)realloc(s->base,(s->size+STACK_SIZE)*sizeof(ElemType)); c++弃用了realloc 
            cout<<"空间不够,重新申请中，请等待：\nPlease wait..."<<endl;
            //下面自己实现relloc
            ElemType *tem = new ElemType [s->size];
            for(int i=0;i<s->size;++i)
                tem[i] = s->base[i];
            delete [] s->base;
            s->base = tem;
            s->top = s->base + s->size; //重新设置栈顶 (注意之前已经满了)
            s->size = s->size + STACK_SIZE; //重新设置最大容量 
            cout<<"申请成功。"<<endl; 
        }
        *(s->top) = e;
        ++(s->top);
    }
    
    void Pop(Stack *&s){
        if(s->top != s->base)
            cout<<(*--(s->top))<<endl; //先用再减  
        else
            return ; // 如果没有元素的话 
    }
    
    //拿到当前容量 
    int NowSize(Stack *s){
        return s->top - s->base;
    }
    //清空栈 
    void ClearStack(Stack *&s){
        s->top = s->base;
    }
    
    void DestroyStack(Stack *&s){
        s->size = 0;
        delete [] s->base;
        //delete [] s->top; 等效的 
        s->base = s->top = NULL; //栈顶和栈底重新指向NULL 
    } 
    
    int main(){
        Stack *stack= NULL;
        InitStack(stack);
        Push(stack,1);
        Push(stack,2);
        cout<<"Now size is: "<<NowSize(stack)<<endl;
        Pop(stack);
        cout<<"Now size is: "<<NowSize(stack)<<endl;
        ClearStack(stack);
        cout<<"Now size is: "<<NowSize(stack)<<endl;
        DestroyStack(stack); 
        cout<< stack<<endl; 
        return 0;
    }

[http_www.cnblogs.com_AsuraDong]: http://www.cnblogs.com/AsuraDong/
[http_blog.csdn.net_asuradong]: http://blog.csdn.net/asuradong
[xiaochiyijiu_163.com]: mailto:xiaochiyijiu@163.com