精华内容
下载资源
问答
  • 为什么称栈和队列是运算受限制的线性表呢,就是因为这俩哥们和普通的线性表不太一样。那么具体不一致的点在哪呢? 我们都知道不管是顺序表还是链表都是可以在其任意位置进行插入和删除操作的(前提是在其索引范围内)...

    数据结构系列第二篇栈和队列,本文依旧会以伪代码和真实代码进行示例的编写。

    为什么称栈和队列是运算受限制的线性表呢,就是因为这俩哥们和普通的线性表不太一样。那么具体不一致的点在哪呢?

    我们都知道不管是顺序表还是链表都是可以在其任意位置进行插入删除操作的(前提是在其索引范围内),插入和删除操作时栈和队列都支持的,但是不同就不同在这个任意位置上。
    一、栈--后入先出表

    我们先看栈的定义:栈-->是只能在表的一端(栈尾)进行【插入】和【删除】操作的线性表,其中允许允许【删除】和【插入】的一端称为栈顶(top),另一端称为栈底

    栈这家伙比较流氓,他的思想是先进入的数据反而后被操作(因为越后入,越靠近栈顶),所以叫后入先出表。举个例子,就是你医院看病,明明是最早进行排队的,反而却是最后才见到医生。

    实例,比如现在有一组数 :S = (1,2,3,4,5),那么它入栈的顺序就是如下图所示这样!

    聪明的同学应该已经发现了,这种思想其实和递归是一样的(将大问题不断的拆解成可执行的小问题,然后先执行小问题,最后执行大问题)

    既然线性表是分为顺序表和链表的,那么栈也能这样分么?答案是肯定的,接下来我们就看伪代码实现过程。

    1.1-栈的顺序表实现

    1.1.1-创建结构体

    int maxsize;    //定义可存储的最大元素个数
    typedef struct seqstack{
        DataType data[maxsize];    
        int top;    // 栈顶top  
    }SeqStk;
    SeqStk *stk;    // 实例化栈结构 s
    

    1.1.2-判空

    int EmptyStack(SeqStk *stk){
        if(s->top==0){    // 判断栈空,就看栈顶这个索引是不是0,如果是0,则代表没元素
            error("栈空");
            return 1;
        }else{
            return 0;
        };
    };

    1.1.3-进栈

    int Push(SeqStk *stk,DataType x){ // x:进栈的值
        if(stk->top==maxsize-1){    // 对于顺序表操作,进行插入操作时一定要校验上溢情况
            error("栈满");
            return 0;
        }else{        // 栈未满情况
            stk->top++;        // top先增加,占据新栈顶位置
            stk->data[stk->top] = x;    // 将值赋值给新栈顶位置
            return 1;
        };
    };

    1.1.4-出栈

    int Pop(SeqStk *stk){
        if(stk->top == 0){   // 对于出栈,一定要校验下溢情况,不能出现栈已经空了,还要进行出栈操作
            error("栈空!");
        }else{
            stk->top--;    // 对于出栈操作,只需要将top值自减即可,相当于原top值不在栈里了
            return 1;
        };
    };

    1.1.5-获取栈顶元素

    DataType GetTop(SeqStk *stk){
        if(stk->top==0){    // 栈空情况就表示没有栈顶元素
            return NULL; 
        }else{
           return stk->data[stk->top];     // 直接返回top对应的元素值即可
        };
    };

    1.2-栈的链式实现

    定义:栈的链式实现-链栈是一个操作受限的单链表,受限行为表现在插入和删除只能在链表表头进行,头指针就是栈顶top指针。

    1.2.1-结构体实现(单链表结构体怎么实现,链栈结构体就怎么实现)

    typedef struct Node{
        DataType data;      // 数据域
        Node *next;        // 指针域
    }LKstk;

    1.2.2-初始化

    void InitStack(LKstk *LS){
        LS = (LKstk*)malloc(sizeof(LKstk));   // 申请内存空间,强不强转有没有都行,具体看场景
        LS->next = NULL;    //  这是一个空表,栈顶指针域指向NULL
    };

    1.2.3-判空

    int EmptyStack(LKstk *Lstk){
        if(Lstk->next == NULL){    // 链栈的判空条件就看头指针的next域有没有节点
            error(“栈空”);
            return 1;
        }else{
            return 0;
        };
    };

    1.2.4-进栈

    int Push(LKstk *Lstk,DataType x){
        // 对于链栈,进栈操作不需要判断上溢(可参考链表-不向顺序表有空间限制)
        temp = malloc(siazeof(LKstk));    // 创建新结点
        temp->data = x;    // 将值赋给新节点数据域
        temp->next =Lstk->next;    // 对于链表插入,一定是先搭上后面,再连接前面节点
        Lstk->next = temp;
        return 1;
    };

    1.2.5-出栈

    int Pop(LKstk *Lstk){
        if(Lstk->next == NULL){
            error("栈空");    // 出栈校验下溢
            return 0;
        }else{
            LKstk *temp;    // 创建新结点用于存储原栈顶结点信息
            temp = Lstk->next;    // 存储原栈顶信息
            Lstk->next = temp->next;    // 将头指针指向新的栈顶(原栈顶的next域)
            free(temp);    // 是否原栈顶内存空间
            retun 1;
        };
    };

    1.2.6-取栈顶值

    DataType GetTop(LKstk *Lstk){
        if(Lstk->next == NULL){    // 判断下溢
            error("空栈");
            return NULLData;
        }else{
            return Lstk->next->data; // 直接返回头指针指向的数据
        };
    };

    二、队列--先进先出表

     队列也是运算受限的线性表,但是这家伙不像栈那样流氓,它呢比较提倡公平,提倡先进先出,就像一根水泥管子,从一端进入,再从另一端出去。

    所以这就是队尾(real)进行新增(插入)数据,队头(front)进行取数据(删除)。

    思考🤔:既然出现了队尾和队头的概念,那么这俩家伙有什么作用呢?

    从两个问题来看:

    1.空队列怎么判断?

    2.满队列怎么判断?

    第一个问题,对于顺序队列来说,当队尾real和队头front指向同一个位置时,就意味着该队列为空。

    第二个问题,对于顺序队列来说,当队尾插入一个新数据时,real+1(自增的目的是为了让real始终指向未存放数据的新位置);当队头存在数据出队列时,front+1(front自增的目的是为了让front始终指向新的对头位置)

    具体过程可参考图一图二

    real和front进行的都是自增操作,但是顺序表又有一个特点就是存储空间是有限的,这就必然会带来一个如图三的问题--假溢出

    为了解决假溢出问题,特引出循环队列概念(前提:还是要提前确定maxsize)

    循环队列入队列出队列过程如图四所示。

    1).队列为空时,real = front(指向同一位置)

    2).a1、a2、a3入队列时,real不断进行自增操作(目的:real指向空闲空间位置)

    3.)出队列时,front进行自增(目的:front指向新栈顶元素)

    4).栈满的条件,又图可知,应该是real+1 == front,但实际我们知道这个等式是不可能成立的(毕竟4+1!=0恒成立)

       所以此地用模运算更合适--使用 (real+1)%maxsize==front 来校验栈是否满

     

    2.1-队列的顺序表实现

    2.1.1-创建结构体

    int maxsize;
    typedef struct SeqQueue{
        DataType data[maxsize];
        int real,front;
    }SeqQue;
    SeqQue sq;

    2.1.2-初始化

    void creatLkQueue(SeqQue*sq){
        sq->real = 0;        // 默认是个空队列,real、front都指向0位置
        sq->front = 0;
    };

    2.1.3-判空

    int EmptyQueue(SeqQue *sq){
        if(sq->real ==sq->front){    // Lk->real == Lk->front 表示空队列
            printf("栈空");
            return 1; 
        }else{
            return 0;        
        };
    };

    2.1.4-入队列

    int EnterQue(SeqQue *sq,DataType x){
        if((sq->real+1)%maxsize == sq->front){
            printf("队列满");
            return 0;
        }else{
            sq->data[sq->real] = x;    // 将real指向的位置存入新值
            sq->real = (sq->real+1)%maxsize;   // real自增,执行新地址
            return 1;
        };
    };

    2.1.5-出队列

    int OutQueue(SeqQue *sq){
        if(sq->real == sq->front){
            printf("空队列");
            return 0;
        }else{
            sq->front = (sq->front+1)%maxsize;    // 出队列直接将front指向下一个元素即可
            return 1;
        };
    };

    2.1.6-获取队首元素

    DataType GetQueue(SeqQue *sq){
        if(sq->real == sq->front){
            printf("空队列");
        }else{
            x = sq->data[sq->front];
            return x;
        };
    };

    链式队列-使用单链表表示队列,但是单链表只有一个指针,无法即指向对首又指向队尾,所以我们设想原指针执行对首,新增一个指针用于指向队尾。

    上溢:链表结构没必要考虑上溢

    下溢:当尾指针(real)==头指针(front)时,即为空队列(除此之外还有另一个判断条件:就是当front->next==NULL时,也是空队列)

    2.2-队列的链式实现

    2.2.1-构造结构体

    typedef struct LinkListQueueNode{    // 结点
        DataType data;            // 数据域
        LinkListQueueNode *next;  // 指针域
    }LKQueNode;
    
    typedef struct  LkQueue{    // 链表
        LKQueNode *real,*front;    // 创建头尾指针
    }LkQue;
    
    LKQueNode Lk;
    LkQue Lq;

    2.2.2-初始化

    int InitLinkQueue(LkQue *Lq){
        LKQueNode *temp;    // 创建结点
        temp = (LKQueNode*)malloc(sizeof(LKQueNode));    
        Lq->front = temp;        // 新创建的队列是个空队列,front和real均指向头结点即可
        LQ->real = temp;
        (LQ->front)->next = NULL;    
    };

    2.2.3-判空

    int EnptyLkQueue(LkQue *Lq){
        if(Lq->real==Lq->front){    // 头指针和尾指针相等,表明空队列
            printf("空队列");
            return 1;
        }else{
            return 0;
        };
    };

    2.2.4-入队列

    // 链表进行插入操作时,一定要先搭上目标后驱,再连接目标前驱
    int insertLkQueue(LkQue *Lq,DataType x){
        // 链表插入新结点 不需要考虑上溢情况
        LKQueNode *temp; // 创建新结点,用于存储新数据
        temp = (LKQueNode *)malloc(sizeof(LKQueNode)); // 申请存储空间
        temp->data = x;         // 将值赋给新结点data域
        temp->next = NULL;      // 尾部新插入的结点是最后一个,其next指向null
        (Lq->real)->next = temp; // 将原最后一个结点的next指向新插入的结点
        Lq->real = temp;     // 将real指针下移,指向新插入的结点(表示新插入的结点是最后结点)
    };

    2.2.5-出队列

    int outLkQueue(LkQue *Lq){
        if(Lq->real==Lq->front){    // 出队列校验下溢
            printf("空队列");
            return 0;
        }else{
            LKQueNode *temp;
            temp = (Lq->front)->next;    // temp用于存放要出队列的结点信息
            (Lq->front)->next = temp->next;   //将front指向新的队首结点 
            if(temp->next==NULL){    // 这里要校验队列是不是空
                Lq->real = Lq.front; // 如果是,尾指针和头指针相等
            };
            free(temp);    // 释放temp
            return 1;
        };
    };

    2.2.6-获取对首元素

    DataType GetLkQueue(LkQue *Lq){
        if(Lq->real==Lq->front){    // 出队列校验下溢
            printf("空队列");
            return NULL;
        }else{
            LkQueNode *temp;    // 新建结点
            temp = (Lq->front)->next;
            return temp->data;
        };

    未完待续~

    展开全文
  • 线性表——顺序表

    2021-04-08 16:40:28
    线性表的一个元素便占据这一个内存,我们节点,线性表要求每一个节点只能够拥有一个前驱节点和一个后继节点,到底是怎样的呢?我们看下图便能明白: 顺序表 顺序表是线性表的一种,它和数

    线性表

    线性表是什么?线性表就是n个具有相同特性的数据元素的有限序列,注意其概念,是具有相同特性,也就是说线性表中的数据元素需要是相同类型的数据;
    线性表是一种在实际中广泛应用的数据结构,常见的线性表有顺序表,链表,栈,队列等等。其中相对重要也相对基础的是顺序表和链表。
    线性表的一个元素便占据这一个内存,我们称之为节点,线性表要求每一个节点只能够拥有一个前驱节点和一个后继节点,到底是怎样的呢?我们看下图便能明白:
    在这里插入图片描述

    顺序表

    顺序表是线性表的一种,它和数组有一些类似,顺序表是数据结构中更加广义的概念,而数组是java语法中的,是更加具体的概念,我们可以这么说:数组是顺序表实现的一种典型方法。数组有的功能顺序表有,而顺序表所能实现的功能,数组不一定能实现(数组想要实现顺序表的功能需要自己动手敲代码,而顺序表的功能则是标准库中有的,可以直接拿来使用),但是有一点需要注意,数组所特有的“[ ]”取下标是顺序表所不具备的。
    顺序表是一个泛型表,即它可以实现多种类型的顺序表,在下面的文章中统一以整型顺序表举例。
    创建顺序表
    两种创建方法,但是建议使用第一种,因为 ArrayList 是一个类,它实现了List这个接口,可以与链表区分开来。

            List<Integer> A = new ArrayList<>();
            ArrayList<Integer> B = new ArrayList<>();
    

    增删改查

    线性表的核心功能是增删改查,顺序表作为线性表中的一员,必然也是具备的。
    插入元素——add
    add()方法传入的参数不同也有不同插入方法,传过去的是元素的值,则表示进行尾插;而如果在传元素的值以外还有下标位置,则表示根据下标位置插入;

    		//public boolean add(int e){}
            A.add(1);
            //public void add(int index, int e){}
            A.add(1,1);
    

    删除元素——remove
    remove()与add()一样也有重载方法,有按下标删除,和按内容删除;在 Integer 类型的顺序表中,删除的时候如果不加上 Integer.valueOf(1) 的话系统会默认为下标删除。

    		//public int remove(int index){}
            int i = A.remove(0);//按下标删除
            //public boolean remove(int e){} 
            boolean a = A.remove(Integer.valueOf(1));//按内容删除
    

    修改元素——set
    set()没有重载方法只有一种使用方法——set(int index, 元素类型 e),index 表示下标,后面的参数表示要插入的值

    		//public int set(int index, int e){}
    		A.set(0, 2);
    

    查找元素
    查找元素的方法很多——get()、contains()、indexOf()、lastindexOf(),这里不一一介绍了,只演示一种特别常见的方法——get(),get()是获取对应下标的值

    		//public int get(int index){}
    		A.get(0);
    

    打印顺序表
    打印顺序表的方法很多,讲其中最简单的就是直接打印顺序表,这是 ArrayList类 中重写了 toString() 的功劳。

    		System.out.println(A);
    
    		[0, 1, 2, 3]
    

    遍历

    顺序表的遍历其实和数组的遍历差不多

            for(int i  = 0; i < A.size(); i++){
                System.out.println(A.get(i));
            }
            for(int x : A){
                System.out.println(x);
            }
    

    在打印的时候是使用方法get(),这就是顺序表遍历和数组遍历一个比较明显的差别。

    用数组实现顺序表

    要想了解顺序表,自己写一个顺序表是最能够清楚的,实现顺序表使用到的是数组。在写代码的时候有一个实现数组的时候明显区别的方法——expansion(),其是被private的修饰的方法,是一个扩容方法,虽然实现简单但却是一个不可获缺的方法,因为顺序表和数组有一个本质上的区别——数组的容量在一开始便是确定,后期不可再更改;而顺序表的容量是可以更改的。
    具体实现如下:

    public class ArrayList<E> {
        //创建一个数组
        private E[] data;
        private int size = 0;
        private int capacity = 100;
    
        //由于E的类型不清楚,所以不能够实例化,所以先创建一个Object类型的通用的数组,
        //然后再将其强转为 E 类型
        public ArrayList(){
            data = (E[]) new Object[capacity];
        }
    
        @Override
        public String toString() {
            E[] arr = (E[]) new Object[size];
            for(int i = 0; i < size; i++){
                arr[i] = data[i];
            }
            return  "[" + Arrays.toString(arr) + "]";
    
        }
    
        //数组和顺序表的区别,当容量不够的时候增加容量
        private int expansion(int capacity){
            capacity = capacity * 2;
            return capacity;
        }
        //增
        //从尾部直接增加
        public void add(E record){
            //如果已存储的数据大于或等于容量,那么扩充容量
            if(size >= capacity ){
                expansion(capacity);
            }
            //先将size + 1,再将要添加的数据放到数组中去
            this.data[size++] = record;
        }
    
        //中间插入
        public void add(int index, E record){
            //如果已存储的数据大于或等于容量,那么扩充容量
            if(size >= capacity ){
                expansion(capacity);
            }
            size++;
            //将index的数值都往后移将其中的空出来
            for(int i = size - 1; i > index; i--){
                data[i] = data[i - 1];
            }
            this.data[index] = record;
        }
        //删
        //删除即为遍历数组找出相同的,然后将其移到最后一个元素的位置,再将size减一;
        public void remove(E record){
            int i = 0;
            for(; i < size; i++){
                if(data[i].equals(record)){
                    break;
                }
            }
            if(i >= size){
                System.out.println("查无次数据,无法删除!");
                return;
            }
            for(int j = i; j < size - 1; j++){
                E tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
            }
            size--;
        }
    
        //改
        //修改值需要知道修改的坐标位置,第二个修改成什么内容
        public void set(int index, E record){
            data[index] = record;
        }
        //查
        //查询是否存在这个数据
        public boolean contains(E record){
            int i = 0;
            for(; i < size; i++){
                if(data[i].equals(record)){
                    break;
                }
            }
            if(i >= size){
                return false;
            }
            return true;
        }
    
        //查询对应内容得下标
        public int IndexOf(E record){
            int i = 0;
            for(; i < size; i++){
                if(data[i].equals(record)){
                    break;
                }
            }
            if(i >= size){
                return -1;
            }
            return i;
        }
    
        //从后面开始查找,找出与所找元素相同的第一个元素
        public int lastIndexOf(E record){
            int i = size - 1;
            for(; i >= 0; i--){
                if(data[i].equals(record)){
                    break;
                }
            }
            if(i < 0){
                return -1;
            }
            return i;
        }
    
        //查询对应下标的内容
        public E get(int index){
            return data[index];
        }
    
        //查询链表长度
        public int Size(){
            return size;
        }
    
        //清空顺序表
        public void clear(){
            size = 0;
        }
    
        //判断顺序表是否为空,为空输出 true ,反之输出false
        public boolean isEmpty(){
            if(size == 0){
                return true;
            }else{
                return false;
            }
        }
    }
    
    
    展开全文
  • 1.什么

    2019-07-09 20:26:34
    中没有数据元素时,空栈。的插入操作通常称为进栈或入栈,的删除操作通常称为退或出栈。 1.简易理解: 客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,局部变量...

    什么是栈

    百度这么说:

    栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的,对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时,称之为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。

    1.简易理解:

    客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,局部变量和中断/调用子程序程序的返回地址。程序中栈主要是用来存储函数中的局部变量以及保存寄存器参数的,如果你用了操作系统,栈中还可能存储当前进线程的上下文。设置栈大小的一个原则是,保证栈不会下溢出到数据空间或程序空间.CPU在运行程序时,会自动的使用堆栈,所以堆栈指针SP就必须要在调用C程序前设定。

    CPU的内存RAM空间存放规律一般是分段的,从地址向高地址,依次为:程序段(.text),BSS段,然后上面还可能会有堆空间,然后最上面才是堆栈段,这样安排堆栈,是因为堆栈的特点决定的,所以堆栈的指针SP初始化一般在堆栈段的高地址,也就是内存的高地址,然后让堆栈指针向下增长(其实就是递减)。这样做的好处就是堆栈空间远离了其他段,不会跟其他段重叠,造成修改其他段数据,而引起不可预料的后果,还有设置堆栈大小的原则,要保证栈不会下溢出到数据空间或者程序空间。所谓堆栈溢出,是指堆栈指针SP向下增长到其他段空间,如果栈指针向下增长到其他段空间,称为堆栈溢出。堆栈溢出会修改其他空间的值,严重情况下可造成死机.

    2.堆栈指针的设置

    开始将堆栈指针设置在内部RAM,是因为不是每个板上都有外部RAM,而且外部RAM的大小也不相同,而且如果是SDRAM,还需要初始化,在内部RAM开始运行的一般是一个小的引导程序,基本上不怎么使用堆栈,因此将堆栈设置在内部RAM,但这也就要去改引导程序不能随意使用大量局部变量。

    片内4K的SRAM,SDRAM大小64M,从0x30000000到0x33FFFFFF,当程序在片内SRAM运行的时候,sp的值设置为4096,当程序在SDRAM内运行的时候sp设置为0x34000000,当然当程序在内部SRAM运行,若已经初始化SDRAM,此时也可以将堆栈指针设置为0x34000000,更加防止了堆栈溢出。

    3. 栈的整体作用

    1. 保存现场;

    2. 传递参数:汇编代码调用 C 函数时,需传递参数;

    3. 保存临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量;

    4. 保存现场
      现场,意思就相当于案发现场,总有一些现场的情况,要记录下来的,否则被别人破坏掉之后,你就无法恢复现场了。而此处说的现场,就是指 CPU 运行的时候,用到了一些寄存器,比如 r0,r1 等等,对于这些寄存器的值,如果你不保存而直接跳转到子函数中去执行,那么很可能就被其破坏了,因为其函数执行也要用到这些寄存器。因此,在函数调用之前,应该将这些寄存器等现场,暂时保持起来(入栈 push),等调用函数执行完毕返回后(出栈 pop),再恢复现场。这样CPU就可以正确的继续执行了。保存寄存器的值,一般用的是 push 指令,将对应的某些寄存器的值,一个个放到栈中,把对应的值压入到栈里面,即所谓的压栈。然后待被调用的子函数执行完毕的时候,再调用 pop,把栈中的一个个的值,赋值给对应的那些你刚开始压栈时用到的寄存器,把对应的值从栈中弹出去,即所谓的出栈。其中保存的寄存器中,也包括 lr 的值(因为用 bl 指令进行跳转的话,那么之前的 PC 的值是存在 lr 中的),然后在子程序执行完毕的时候,再把栈中的 lr 的值 pop 出来,赋值给 PC,这样就实现了子函数的正确的返回

    5. 传递参数

    C 语言进行函数调用的时候,常常会传递给被调用的函数一些参数,对于这些 C 语言级别的参数,被编译器翻译成汇编语言的时候,就要找个地方存放一下,并且让被调用的函数能够访问,否则就没发实现传递参数了。对于找个地方放一下,分两种情况。一种情况是,本身传递的参数不多于 4 个,就可以通过寄存器 r0~r3 传送参数。因为在前面的保存现场的动作中,已经保存好了对应的寄存器的值,那么此时,这些寄存器就是空闲的,可以供我们使用的了,那就可以放参数。另一种情况是,参数多于 4 个时,寄存器不够用,就得用栈了。

    1. 临时变量保存在栈中
      包括函数的非静态局部变量以及编译器自动生成的其他临时变量。
    展开全文
  • 关于的一些新的理解 的定义:(stack)又名堆栈,它是一种运算受限的...从一个删除元素又出栈或退,它是把栈顶元素删除掉,使其邻居的元素成之新的栈顶元素。 的特点:先入后出。符合这...

    • 栈的定义:栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称为进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称之为出栈或退栈,它是把栈顶元素删除掉,使其邻居的元素成之为新的栈顶元素。

    • 栈的特点:先入后出。符合这个特征的数据才可以在栈中存储。

    • 在计算机系统中,栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中,也可以将数据从栈顶弹出。

    • 栈在程序的运行中有举足轻重的作用,最重要的是栈保存了一个函数调用时所需要的维护信息,这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息:

    1. 函数的返回地址和参数。
    2. 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量

    栈的作用原理

    • 一个函数设计里面,有2个问题:
    1. 参数传递
    • 传递参数的目的,是为了代码可以重用,让一种方法可以应用到更多的场合,而不需要为N种情况写N套类似的代码。
    • 那用什么方法来做参数的传递?可以选择:
    • 为了速度快,使用cpu的寄存器传递参数。这会碰到一个问题,cpu寄存器的数量是有限的,当函数内再想调用子函数的时候,再使用原有的cpu寄存器就会冲突了。想利用寄存器传参,就必须在调用子函数前把寄存器存储起来,然后当函数退出的时候再恢复。
    • 利用某些ram(随机存取存储器)的区域来传递参数。这和上面a的情况几乎一样,当函数嵌套调用的时候,还是会出现冲突,依然面临要把原本数据保存到其他地方,再调用嵌套函数。并且保存到什么地方,也面临困难,无论临时存储到哪里,都会有上面传递参数一样的困境。
    1. 函数里面也有可能要使用到局部变量,而不能总是用全局变量。则局部变量存储到哪里合适,即不能让函数嵌套的时候有冲突,又要注重效率。
    • 以上问题的解决办法,都可以利用栈的结构体来解决:
    1. 寄存器传参的冲突,可以把寄存器的值临时压入栈里面,非寄存器传参也可以压入到栈里面。
    2. 局部变量的使用也可以利用栈里面的内存空间,只需要移动下栈指针,腾出局部变量占用的空间。最后利用栈指针的偏移来完成存取。于是函数的这些参数和变量的存储演变成记住一个栈指针的地址,每次函数被调用的时候,都配套一个栈指针地址,即使循环嵌套调用函数,只要对应函数栈指针是不同的,也不会出现冲突。
    3. 利用栈,当函数不断调用的时候,不断的有参数局部变量入栈,栈里面会形成一个函数栈帧的结构,一个栈帧结构归属于一次函数的调用。栈的空间也是有限的,如果不限制的使用,就会出现典型的栈溢出的问题。有了栈帧的框架在,我们在分析问题的时候,如果能获取到当时的栈的内容,则有机会调查当时可能出现的问题。
    • 然而栈存在的意义还不止这点,有了它的存在,才能构建出操作系统的多任务模式。

    总结

    • 栈的作用分为以下几点:
    1. 栈是每个函数架构的基础,实现了函数的重复利用。
    2. 问题发生的时候,可以利用栈来了解问题发生的情况。
    3. 栈是构建出操作系统多任务模式的基础。
    展开全文
  • java实现

    2019-07-30 09:19:00
    2.不包含任何数据元素的栈称空栈 特点:先进后出,后进先出 注意:1.栈也称之lifo结构 2.栈的插入操作称之进栈,也称之压栈,入栈 3.栈的删除操作。称之出栈,也称之弹栈 3.实现细节和注意要点 ...
  • 的使用

    2020-06-07 23:42:03
    中没有数据元素时,空栈。的插入操作通常称为进栈或入栈,的删除操作通常称为退或出栈。 简易理解: 客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,局部变量和中断/调用子程序...
  • 和队列都是特殊的线性表,是限制存取位置的线性结构;可以由顺序表实现,也可以由链表实现。...设给定s=(a0,a1,……,an-1),a0为栈底,an-1栈顶。 又称作后进先出(LIFO:Last In
  • 和队列都是特殊的线性表,是限制存取位置的线性结构;可以由顺序表实现,也可以由链表实现。...设给定s=(a0,a1,……,an-1),a0为栈底,an-1栈顶。 又称作后进先出(LIFO:Last In First O
  • 编程基础——

    2018-08-05 23:25:47
    1、什么是一种特殊的线性表,他的逻辑结构与线性表相同,其特殊性体现在运算上受限制。无论在删除或者添加元素,都必须在表端...向中插入元素入栈,删除中的元素操作称为出栈。 2、的存...
  • 数据结构 -

    2015-05-10 17:36:31
    如:S=(a1,a2,…,an),其中a1为栈底元素,an 栈顶元素 什么特点呢? 是一种线性结构 对的操作按照“后进先出”的原则进行 读栈顶元素 非空栈中,读取栈顶元素,不影响中元素之间的关系 入栈
  • 目录栈什么?...也可以很形象的这种结构后进先出(Last in First Out)LIFO结构。 一般有插入和删除操作,插入我们称为入栈,压栈,删除称为出栈,弹。 因为线性表的特例,所以依据线
  • 一、什么是限制在一端进行操作(插入、删除)的线性表;我们俗称堆栈;只不过是一种特殊的线性表,有顺序、也有链式 二、的特点 具有先进后出的特点,即先进的数据后出栈(LIFO);入栈出栈...
  • 和队列都是特殊的线性表,是限制存取位置的线性结构;可以由顺序表实现,也可以由链表实现。...设给定s=(a0,a1,……,an-1),a0为栈底,an-1栈顶。 又称作后进先出(LIFO:Last In First
  • (Java实现)

    2020-07-28 14:03:57
    1.什么 ...我们数据进入到的动作压栈,数据从中出去的动作。 2.的实现 2.1的API设计 类名 Stack<T> 构造方法 Stack():创建Stack对象 成员方法 1.public boolean i
  • 是一种特殊的线性表 ,只允许在固定的一端进行元素的插入和删除操作,且进行操作的那一段栈顶,另一端称为底; 2、的基本操作 (1)压栈 的插入操作,插入的数据在栈顶 (2)出栈 的删除操作,出栈...
  • 允许插入和删除的一端称为栈顶 (top),另一端 为栈底(base) 特点:后进先出 (LIFO, Last In, First Out) 二、顺序 2.1 顺序的顺序存储表示 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 ...
  • 计算机二级知识点——

    千次阅读 2019-11-30 14:09:16
    要搞懂这个知识点,我们首先要明白什么线性表线性表线性表,又线性结构,具有以下特征: 1.集合中必存在唯一的一个"第一个元素";(即数组元素a[0]) 2.集合中必存在唯一的一个"最后的元素";(即数组...
  • 这一端被称为栈顶,相对地,把另一端称为底,底固定,而站顶浮动,当中元素个数零时这个栈为空栈。向一个插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从...
  • 试图对一个空的队列执行出队的操作下溢(underflow)。 试图对一个满的队列执行入队的操作溢出(overflow)。 对列的抽象数据类型 主要的队列操作 enQueue(int data): 在对列的队尾插入一个元素 ...
  • C语言及ARM中堆栈指针SP设置的理解与总结

    万次阅读 多人点赞 2017-03-31 22:31:37
    1.首先来看什么,百度这么说: ...当中没有数据元素时,空栈。的插入操作通常称为进栈或入栈,的删除操作通常称为退或出栈。 客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,局部
  • 什么是栈帧

    2019-05-31 15:37:00
    栈帧 那先有个问题,什么? 在数据结构中, 是限定仅在表尾进行...在计算机系统中,也可以为栈内存是一个具有动态内存区域,存储函数内部(包括main函数)的局部变量和方法调用和函数参数值,是...
  • C 语言及 ARM 中堆栈指针 SP 设置的理解与总结 1 什么 百度这么说 是一种特殊的线性表 是一种只允许在表的一端进行插入或删除操作的线 性表表中允许进行插入删除操作的一端称为栈顶表的另一端称为底栈顶的...
  • ARM堆栈指针sp(r13)详解

    千次阅读 2018-09-15 15:15:20
    1.什么 ...当中没有数据元素时,空栈。的插入操作通常称为进栈或入栈,的删除操作通常称为退或出栈。 简易理解: 客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,...
  • 1.什么 ...当中没有数据元素时,空栈。的插入操作通常称为进栈或入栈,的删除操作通常称为退或出栈。 简易理解: 客栈,即临时寄存的地方,计算机中的堆栈主要用来保存临时数据,...
  • 5.8(补)

    2019-05-10 23:48:46
    进行删除和插入的一端栈顶,另一端称栈底 插入称为进栈(PUSH) 删除称为退(POP) 一个可以用定长N的数组S来表示,用一个指针TOP指向栈顶。若TOP=0,表示空,TOP=N时满。进栈时TOP加1。退时TOP...
  • acm周中学习总结

    2019-05-08 21:57:21
    进行删除和插入的一端栈顶,另一堆称栈底。插入一般称为进栈(PUSH),删除则称为退(POP)。 也称为后进先出表(LIFO表)。 一个可以用定长N的数组S来表示,用一个指针TOP指向栈顶。若TOP=0,表示...
  • 栈帧

    2020-03-27 15:25:16
    在计算机系统中,也可以为栈内存是一个具有动态内存区域,存储函数内部(包括main函数)的局部变量和方法调用和函数参数值,是由系统自动分配的,一般速度较快;存储地址是连续且存在有限容量,会...

空空如也

空空如也

1 2 3
收藏数 44
精华内容 17
关键字:

栈称为什么线性表