精华内容
下载资源
问答
  • 栈 栈的定义 ...生活后进先出的例子:子弹夹中子弹。 栈的表示和实现 1.顺序栈 #define STACKSIZE 50 struct SeqStack { int elem[STACKSIZE]; int top; }; //初始化顺序栈 void InitStack(SeqStack

    栈的定义

    1.栈是一种限定性线性表,将线性表的插入和删除限制为仅在表的一端进行,表中允许插入删除操作的一端称为栈顶,因此栈顶的当前位置是动态变化的,由一个位置指示器(栈顶指针)来指示。
    2.栈是后进先出的线性表,简称为LIFO表。生活中后进先出的例子:子弹夹中子弹。

    栈的表示和实现

    1.顺序栈

    #define STACKSIZE 50
    struct SeqStack
    {
    int elem[STACKSIZE];
    int top;
    };
    //初始化顺序栈
    void InitStack(SeqStack *s)
    {
    s->top=-1; //top=-1表示空栈
    }
    //入栈
    void Push(SeqStack *s,int x)
    {
    s->top++; //修改栈顶指针
    s->elem[s->top]=x;//x进栈
    }
    //出栈
    void Pop(SeqStack *s,int *x)
    {
    *x=s->elem[s->top]; //将栈顶元素赋值给x
    s->top–;//修改栈顶指针
    }
    //判断栈空
    int StackEmpty(SeqStack s)
    {
    if(s.top==-1)
    {
    return 1;
    }
    return 0;
    }

    2.链栈

    struct LinkStackNode
    {
    char data;
    LinkStackNode *next;
    };
    typedef LinkStackNode *LStack;
    //初始化顺序栈
    void InitStack(Stack *s)
    {
    *s=new LinkStackNode;
    (*s)->next=NULL;
    }
    //入栈
    void Push(LStack s,int e)
    {
    LinkStackNode *temp;
    temp=new LinkStackNode;
    temp->data=e;
    temp->next=s->next;
    s->next=temp;
    }
    //出栈
    void Pop(LStack s,int *ch)
    {
    *ch=s->next->data;
    s->next=s->next->next;
    }
    //判断栈空
    bool StackEmpty(LStack s)
    {
    if(s->next==NULL)
    {
    return true;
    }
    return false;
    }

    栈的应用举例

    1.括号匹配
    2.表达式求值

    栈与递归的实现

    1.递归是指定义自身的同时又出现了对自身的引用。
    2.递归问题需要有:
    (1)基值的判断,循环终止的条件
    (2)递归调用函数
    (3)调用后的返回处理
    3.一些本身具有固有递归特性的数据结构:广义表,二叉树,树,快速排序法,图的深度优先搜索
    4.使用递归算法的前提
    (1)原问题可以分解成子问题,且子问题规模更小
    (2)规模最小的子问题有直接解
    5.设计递归算法的原则
    (1)寻找分解算法:原问题转换为子问题 eg:n!=n(n-1)!
    (2)设计递归出口:用规模最小的子问题确定循环终止的条件 eg:求n!, n=1时,n!=1
    6.递归算法的特性
    (1)分而治之,复杂问题简单化
    (2)效率低(原因:递归执行时需要系统提供隐式栈来实现)
    7.消除递归的方法
    (1)简单递归问题:用循环结构的算法代替单向递归和尾递归
    单向递归:递归函数虽有一处以上递归调用语句,但各次递归调用语句的参数只和主调函数有关,相互之间参数无关,且这些递归调用语句处于算法最后。
    (2)基于栈的方式:将递归中隐含的栈结构转换为用户直接控制的明显的栈
    8.有递归特性的问题
    (1)斐波那契数列
    (2)Ack函数
    (3)n的阶乘
    (4)汉诺塔问题

    展开全文
  • 简单介绍

    2020-10-16 11:20:11
    这种先进后出,后进先出的结构称为“栈”。 2、栈的特点 “先进后出,后进先出” 3、栈的操作 栈的操作就两种,分别为出栈和入栈。那我们上边的例子,我们往柜子里放东西的过程称为入栈;我们在柜子里拿东西的过程...

    1、什么是栈

    我们用一种最简单的生活常识描述一下,比如我们往柜子里放东西,先放的东西是需要放到柜子最里边,后放的东西在柜子的最外边;如果我们要取东西,先要取柜子最外边的东西,才能取到柜子最里边的东西。这种先进后出,后进先出的结构称为“栈”。
    在这里插入图片描述

    2、栈的特点

    “先进后出,后进先出”

    3、栈的操作

    栈的操作就两种,分别为出栈和入栈。那我们上边的例子,我们往柜子里放东西的过程称为入栈;我们在柜子里拿东西的过程称为出栈。

    注意:柜子只有一个出口和入口,而且出口和入口是一样的。如果两端都有开口,就变成了队列

    4、栈的实现

    栈的实现主要有两种,一种是数组的实现,叫做顺序栈,另外一种是链表的实现,叫做链式栈

    4.1、顺序栈

    在这里插入图片描述

    基于数组的顺序栈

    public class ArrayStack {
       private String[] items;  // 数组
       private int count;       // 栈中元素个数
       private int n;           // 栈的大小
    
       // 初始化数组,申请一个大小为 n 的数组空间
       public ArrayStack(int n) {
         this.items = new String[n];
         this.n = n;
         this.count = 0;
       }
    
       /**
        * 功能:入栈
        * 说明:数组入栈的入口为数组尾部
        * @param item :入栈数据元素
        * @return:是否入栈成功
        */
       public boolean push(String item) {
         // 数组空间不够了,直接返回 false,入栈失败。
         if (count == n) return false;
         // 将 item 放到下标为 count 的位置
         items[count] = item;
         //数组长度+1
         ++count;
         //入栈成功
         return true;
       }
    
       /**
        * 功能:出栈
        * @return:返回出栈元素
        */
       public String pop() {
         // 栈为空,则直接返回 null
         if (count == 0) return null;
         // 返回下标为 count-1 的数组元素
         String tmp = items[count-1];
         //数组长度-1
         --count;
         //返回出栈数据元素
         return tmp;
       }
     }
    

    4.2、链表栈

    在这里插入图片描述

    /**
     * 功能:基本链表实现栈,入栈、出栈、输出栈
     * @author : 小鹿
     *
     */
     6public class StackBasedLinkedList {
        //定义栈顶指针
        private Node top = null;
    
        //定义栈结点
        private static class Node {
            //栈结点数据域
            private int data;
            //栈结点指针域
            private Node next;
            //构造函数
            public Node(int data, Node next) {
              this.data = data;
              this.next = next;
            }
            //get 获取数据域方法
            public int getData() {
              return data;
            }
        }
    
        /**
         * 功能:入栈
         * @param value:要入栈的数据元素
         */
        public void push(int value) {
            //创建一个栈结点 
            Node newNode = new Node(value, null);
            // 判断栈是否为空
            if (top == null) {
              //如果栈为空,就将入栈的值作为栈的第一个元素
              top = newNode;
            } else {
              //否则插入到top栈结点前(所谓的就是单链表的头插法)
              newNode.next = top;
              top = newNode;
            }
        }
    
        /**
         * 功能 : 出栈
         * @return: -1 为栈中没有数据
         */
        public int pop() {
            // 如果栈的最顶层栈结点为null,栈为空
            if (top == null) return -1;
    
            //否则执行出栈操作,现将栈顶结点的数据元素赋值给 Value
            int value = top.data;
            //将 top 指针向下移动
            top = top.next;
            //返回出栈的值
            return value;
        }   
    
        /**
         * 功能:输出栈中所有元素
         */
        public void printAll() {
            //将栈顶指针赋值给p
            Node p = top;
            //循环遍历栈(遍历单链表)
            while (p != null) {
              System.out.print(p.data + " ");
              //指向下一个结点
              p = p.next;
            }
            System.out.println();
        }
    }
    
    展开全文
  • 根据“后进先出”特性,生活的例子比比皆是,本文举3例。 1数制转换 2括号匹配验证 3表达式求值

    根据“后进先出”特性,生活中的例子比比皆是。

    1数制转换


    假设要讲十进制转换为二进制。以 52 为例,如图:


    在上述计算过程中,第一次求出的X值为最低位,最后一次求出的X值为最高位。而打印时应从高位到低位进行,恰好与计算过程相反。根据这个特点,我们可以通过入栈出栈来实现,即将计算过程中依次得到的二进制数码按顺序进栈,计算结束后,再顺序出栈,并按出栈顺序打印输出。即可得到给定的二进制数。这是利用栈后进先出特性的最简单例子。

    void Conversion(int N){
        /*对于任意的一个非负十进制数N,打印出与其对应的二进制数*/
        Stack S;
        int x;
        InitStack(&S);
        while (N>0) {
            x=N%2;
            Push(&S,x); //将余数压入栈S
            N=N/2;
        }
        while (!IsEmpty(&S)) {
            Pop(&S,&X);
            printf("%d",x);
        }
    }
    

    2括号匹配问题


    假设表达式有三种括号:圆括号“()”,花括号“{}”,方括号“[]”。它们可互相嵌套,如{([])}或{([])()[]}均为正确格式。而{)),{[()]均为不正确格式。如何检测其正确性?可以应用栈。

    我们以“{[()]}”为例,依次读取括号,如图:


    注意,上面写的双双出栈其实是,左括号出栈。

    void BrackerMatch(char *str){
        Stack S;
        int i;
        char ch;
        InitStack(&S);
        for (i=0;str[i]!='/0';i++)
        {
            switch (str[i]) {
                case '(':
                case '[':
                case '{':
                    Push(&S,str[i]);
                    break;
                case ']':
                case '}':
                case ')':
                    if (IsEmpty(&S)) {
                        printf("\n 右括号多余!");
                        return;
                    }else{
                        GetTop(&S,&ch);
                        if(Match(ch,str[i])) //用 Match 判断两个括号是否匹配
                            Pop(&S,&ch);     //已匹配的左括号出栈
                        else{
                            printf("\n对应的左右括号不同类");
                            return;
                        }
                    }
                default:
                    break;
            }
            if (IsEmpty(&S))
                printf("\n括号匹配!");
            else
                printf("\n左括号多余!");
        }
    }

    3表达式求值


    表达式求值是高级语言编译中的一个基本问题,是栈的典型应用实例。

    1+2*3/(1+5)=2

    任何一个表达式都是由数(操作数)和符号(运算符+-*/,界限符())组成。

    而符号又有优先级,优先计算得到的值再作为数继续运算,当符号用尽后,值即为所得。


    1+2*3/(1+5)   -->   1+6/(1+5)   -->   1+6/6   -->   1+1   -->   2

    优先级规则:

    (1)先左后右

    (2)先乘除,后加减

    (3)先括号内,后括号外

    此时需要两个栈,一个称作operator,用以存放符号。一个称作operand,用于存放操作数或中间结果。下图,为即将要用到的算符之间的优先关系。


    算法的基本过程如下:

    初始化两个栈,然后讲表达式起始符“#”压入operator栈。

    输入表达式,以“#”结尾。

    依次读取表达式,读取过程中,若是操作数,直接入栈operand。若是符号,则与operator栈顶运算符进行比较。

    (1)若 栈顶符<刚读运算符 : 刚读运算符 进栈;

    (2)若 栈顶符>刚读运算符 : 进行计算,operator栈顶符退栈,送入x,同时将operand栈退栈两次,得到a,b,对a,b,x进行运算后,将结果作为中间结果推入operand栈;

    (3)若 栈顶符=刚读运算符 : 说明是左右括号相遇,栈顶符退栈即可;

    当operator栈的栈顶符和当前符都为“#”时,说明求值完毕。

    以(10+2)*3# 为例,如图:


    当栈顶符和当前符都是“#”,计算结束

    int ExpEvaluation(){
        /*operator为符栈,operand为数栈,OPS为运算符集合*/
        InitStack(&operand);
        InitStack(&operator);
        Push(&operator,'#');
        printf("\n输入一个表达式(以#结束)");
        ch=getchar();
        while(ch!='#'||GetTop(operator)!='#'){ //GetTop 取栈顶
            if (!In(ch,OPS)) {                  //不是操作符,是操作数
                int temp;
                temp=ch-'0';                //数的临时变量,并转换为十进制
                ch=getchar();
                while (!In(ch,OPS)) {        //数可能不只有一位,如100就要读三次
                    temp=temp+10+ch-'0';
                    ch=getchar();
                }
                Push(&operand,temp);
            }
            else
                switch (Compare(GetTop(operator),ch)) {
                    case '<':
                        Push(&operator,ch);
                        ch=getchar();
                        break;
                    case '=':
                        Pop(&operator,&x);
                        ch=getchar();
                        break;
                    case '>':
                        Pop(&operator,&op);
                        Pop(&operand,&b);
                        Pop(&operand,&a);
                        v=Execute(a,op,b);   //对a和b进行op运算
                        Push(&operand,v);    //注意这里没有 ch=getchar()
                        break;
                }
        }
        v=GetTop(&operand);
        return v;
    }
    


    以上均为学习耿国华的《数据结构-c语言》笔记

    展开全文
  • 栈 栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。...这就是后进先出的实际例子。 栈的创建: 我们创建一个类来表示栈。先声明...

    栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈顶。

    现实生活中就有很多栈的例子。如下图的书本,这一摞书如果要取肯定是先去最上面的那一本,但它是最后一个放上去的,也就是栈顶的元素都是待添加或是待删除的。这就是后进先出的实际例子。

     

    栈的创建:

    我们创建一个类来表示栈。先声明:

    function Stack() {
    
      //各种属性和方法的声明
    
    }

    然后我们需要一种数据结构来保存栈里的元素:

    var items = [];

    接下来,我们给栈声明一些方法:

    • push(element):添加一个或几个新元素到栈顶
    • pop():移除栈顶的元素,同时返回被移除的元素
    • peek():返回栈顶的元素,不对栈做任何修改
    • isEmpty():判断栈里有无元素
    • clear():移除栈里的所有元素
    • size():返回栈里的元素个数。和数组length属性类似。

    我们利用这些方法来实现一个栈:

    function Stack() {
        var items = [];
        this.push = function(element) {
            items.push(element);
        }
        
        this.pop = function() {
            return items.pop();
        }
    
        this.peek = function() {
            return items[items.length - 1];
        }
    
        this.isEmpty = function() {
            return items.length === 0;
        }
    
        this.size = function() {
            return items.length;
        }
    
        this.clear = function() {
            items = [];
        }
    
        this.print = function() {
            console.log(items.toString());
        }
    }

    我们来测试下:

    var stack = new Stack();
    console.log(stack.isEmpty()); // true
    stack.push(5);
    stack.push(8);
    console.log(stack.peek()); // 8 
    stack.push(11); 
    console.log(stack.size()); // 3 
    stack.pop(); 
    console.log(stack.size()); // 2 
    stack.print(); // 5,8

    参考链接: 学习JavaScript数据结构与算法

    展开全文
  • 栈是一种“后进先出”的线性表,我们在线性表的尾部进行添加和删除元素。很常见的生活中的例子,就是洗盘子。我们所用过得盘子,都是最后收拾的盘子在上面,所以第一个要洗的就是第一个盘子。还有火车进站出站等等。...
  • 准确讲,栈就是一种可以实现“先进后出(或者叫后进先出)”存储结构。 学过数据结构人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做...
  • 是一种数据结构,能够实现后进先出的一种业务场景。即栈中的元素被处理时,按后进先出的顺序进行。所以栈又叫做后进先出表(LIFO); 例子生活中的叠放在厨房桌子上的碗就是一种栈结构。放的时候只能把碗放在最...
  • 概念以及实现堆

    2017-09-12 17:04:05
    普通队列就是遵循时间原则,先进先出后进出的一种队列结构;而优先队列则是按照优先级来决定出队的次序,与何时进入队列无关,实际生活中有很多优先队列的例子:医院候诊病人中,急诊病人优先看病,而不是按照...
  • 操作

    2016-07-27 14:26:49
    准确讲,栈就是一种可以实现“先进后出(或者叫后进先出)”存储结构。 学过数据结构人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做...
  • 特点:先进先出后进后出 以下代码,只是比较简单实现队常用形式,队还可以是循环队,还可以设置队最大长度,队满等方法属性。 代码: class Queue: def __init__(self): self.queue = [] self.fr.....
  • 基本思想:后进先出(先进后出)即栈中元素被处理时,按后进先出的顺序进行,栈又叫后进先出表(LIFO)。 举例: 日常生活中有很多栈的例子。例如,放在书桌上的一摞书,只能从书顶上拿走一本书,书也只能放在顶上。...
  • JS栈结构简单封装

    2021-05-17 18:05:29
    栈:是一种遵循后进先出(Last In First Out / LIFO) 原则一种有序集合。  新添加或者要删除元素都会保存在栈同一端,我们把它叫做栈顶,另外一端叫做栈底。  在栈中所有新元素都接近栈顶,而所有旧...
  • C++ 栈(Stack)基本操作

    万次阅读 2019-01-03 17:40:37
     一种可以实现“先进后出(后进先出)”存储结构  生活的例子:玩具枪子弹夹,后进来子弹先射出。   二、分类:  静态栈:使用数组  动态栈:链表 三、算法:  出栈:push  压栈:pop  ...
  • 栈是一种遵从后进先出(LIFO)原则有序集合。新添加或者待删除元素都保存在栈同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。 我们在生活中常能看到栈的例子。整齐堆起来...
  • 每日一题之栈实现

    2017-07-20 22:44:01
    栈:在生活很多例子都...所以我们可以知道栈中元素都必须遵循“后进先出”原则。我们现在实现放椅子与拿椅子过程,即入栈(push)与出栈(pop)。栈中一些接口如图所示: 实现入栈与出栈原理如图所示:
  • 栈(stack)是一种操作受限...在日常生活中,有许多栈的例子,进制转换、表达式求值、括号匹配使用等都是栈后进先出”设计思想。 【定义】  栈(stack),也叫堆栈,它是限定仅在表尾进行插入和删除操作线...
  • 该订单可以是LIFO(后进先出)或FILO(后进先出)。 有很多现实生活的例子。 链接列表: 链接列表由节点组成,其中每个节点包含一个数据字段和一个指向列表中下一个节点refernece(link)。
  • 队列和栈非常的类似,但是他们采用了不同的原则,栈采用的是后进先出,队列正好相反,采用的是先进先出的原则。队列的定义如下 队列是遵循FIFO(先进先出)原则的有序集合,新添加的元素保存在队列的尾部,要移除的...
  • python数据结构之栈(stack)

    万次阅读 2018-01-12 09:39:48
    1.栈定义栈遵循后进先出(Last In First Out),现实生活中也有不少这样的例子,比如在学校食堂吃完饭时,你把盘子放到桌子上,叠起来之后,阿姨过来拿盘子出去洗,假如是手洗,那肯定是先从最上面盘子开始拿来洗...
  • 就像我们刚才的例子,栈这种后进先出的数据结构应用是非常广泛的。 在生活中,例如我们的浏览器,每点击一次“后退”都是退回到最近的一次浏览网页。例如我们Word,Photoshop等的“撤销”功能也是如此。 再例如我们...
  • 关于栈,我们先想一个生活中的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;...栈的操作是按照后进先出的原则进行。 顺序队列 基于数组实现顺序队列 public c...
  • C# 队列和栈 线程安全

    2017-06-07 17:29:00
    栈是和队列非常类似另一个容器,栈和队列最大区别是后进先出(LIFO),也可以说成先进后出。 队列在现实生活的例子数不胜数。例如:排队打饭,排队购买机票,打印队列中等待处理打印业务等 栈在生活的例子...
  • 关于栈,我们先想一个生活中的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;...栈的操作是按照后进先出的原则进行。 顺序栈 采用顺序存储结构的栈称为顺序栈,需要一块...
  • 栈是一种遵从后进先出(LIFO)原则有序集合。 新添加或待删除元素都保存在栈末尾,称为栈顶,另一端叫栈底。 在栈里,新元素都靠近栈顶,旧元素都接近栈底 现实中的例子生活中也能发现很多栈的例子。...
  • 栈和队列   让编程改变世界 Change the world by program   ...栈是一种重要的线性结构,可以这样讲,栈是...就像我们刚才的例子,栈这种后进先出的数据结构应用是非常广泛的。   在生活中,例如我们的浏览器

空空如也

空空如也

1 2 3 4
收藏数 72
精华内容 28
关键字:

后进先出的生活例子