注册 留言板
当前位置:首页 > 方法论 > 数据结构 > 正文

栈的各种操作

来源:CNBLOGS   发布时间: 2017-06-18   作者:网友   浏览次数:
摘要: 栈(stack)又名堆栈,是仅允许在表的一端进行插入和删除运算。 表尾一端被称为栈顶,相对地,表头称为栈底。 Push:向一个栈...

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

流程如下

  1. 初始化:初始化一个栈的大小为STACK_SIZE,并且将容量size设置为STACK_SIZE。

  2. 入栈操作: 每次向栈中压入一个数据,此时top指针+1。直到栈满。当栈满时,再申请更多空间。

  3. 出栈操作: 弹出栈顶数据,并且下移pop指针

  4. 清空栈: 清空数据,但是不改变物理地址。只是改变指针。类似硬盘格式化,只是清空文件列表而不是重新覆盖。所以我们可以硬盘恢复。

  5. 销毁栈: 完全释放掉栈占据的内存空间。和清空有本质区别。


欢迎进一步交流本博文相关内容:

博客园地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信进行交流 : 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;
}


我来说两句
评论内容:
验  证  码:
 
(网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
评论列表
已有 0 条评论(查看更多评论)
精彩专题
友情链接:
设为首页 - 加入收藏 Copyright @2016 Infocool 版权所有 粤ICP备16000626号