精华内容
下载资源
问答
  • 的元素存储与利用是遵循后进先出(LIFO)的,如下图,我们可以用一个半开口的方框表示,开口的一端称为栈顶,就是这端进行着压栈(push)和出栈(pop)操作。 对于给定的待判断序列,比如这里的A选项453126,我们可以...

    今天有人问了我一道题,如下:
    在这里插入图片描述
    意思就是给定一个顺序为654321的栈,判断下面的栈是否是正确的。

    解题思路

    栈的元素存储与利用是遵循后进先出(LIFO)的,如下图,我们可以用一个半开口的方框表示栈,开口的一端称为栈顶,就是这端进行着压栈(push)和出栈(pop)操作。
    在这里插入图片描述
    对于给定的待判断序列,比如这里的A选项453126,我们可以依次按照这个序列的顺序进行推演,

    • 首先是第一个元素4,我们可以用这个元素"4"将原栈一分为二,即第一步,左边为原栈wt,右边为st_tmp,注意st_tmp开口方向相反。
    • 然后我们先判断st的栈顶是否是当前遍历的元素"4",如果是就pop掉,并遍历下一个元素"5",如第二步,
    • 按照相同操作我们来到第三步。此时遍历到元素"3",此时左边st的栈顶并不等于元素"3",因此我们需要从st_tmp中依次从栈顶找到并push到左边的st然后再pop掉,这一步可以简化为直接pop掉。
    • 到了第四步遍历"1"时,我们发现左边st的栈顶也没有,右边st_tmp的栈顶也没有,此时我们就要逐次把st_tmp的栈顶push到左边,直到发现st_tmp的栈顶等于此时遍历的元素"1"为止。如果此时不幸pop掉了st_tmp中的所有元素也没有找到元素"1",说明该序列并不是正确的序列
    • 幸运的是这里还是找到了元素"1"并pop掉,如第六步
    • 接下来的步骤都是类似的操作,如果最后成功pop掉st和st_tmp中的所有元素,说明该序列是正确的,即原栈654321可以通过一系列的push/pop步骤得到该序列。

    代码实现

    代码实现如下,这里不仅能实现654321的判断,还能实现其他个数比如4321的判断,只需要更改变量n即可,不仅仅是个数,对于任意栈如343453等同样适用,只需要更改栈的初始化即可。

    class StackUnderflow(ValueError):
        '''自定义栈相关的异常类
        '''
        pass
    
    class SStack:
        '''基于顺序表实现的栈类
        '''
    
        def __init__(self):
            self._elems = []  # 用list对象 _elems存储栈中元素
    
        def is_empty(self):
            return self._elems == []
    
        def top(self):  # 取得最后压入的元素,即栈顶
            if self._elems == []:
                raise StackUnderflow("in SStack.pop()")
            else:
                return self._elems[-1]
    
        def push(self, elem):  # 压栈
            self._elems.append(elem)
    
        def pop(self):  # 出栈
            if self._elems == []:
                raise StackUnderflow("in SStack.pop()")
            return self._elems.pop()
    
        def elems(self):
            elems = self._elems
            return elems
    
    
    st = SStack()
    flag = True
    # n = int(input("栈元素个数:"))
    n = 6 # n也可以改为其他的
    for i in range(n, 0, -1):
        st.push(i)
    st_tmp = SStack()
    input_series = input("输入待判断序列")
    series_list = list(map(int, input_series))
    print(series_list)
    
    while not st.top() == series_list[0]:  # 以待判断序列首元素为界,将原栈一分为二
        st_tmp.push(st.top())
        st.pop()
    
    for serie in series_list:
        if (not st.is_empty()) and serie == st.top():
            st.pop()
        else:
            if st_tmp.is_empty():
                flag = False
            else:
                while not serie == st_tmp.top():
                    st.push(st_tmp.top())
                    st_tmp.pop()
                    if st_tmp.is_empty():
                        break
                if st_tmp.is_empty():
                    flag = False
                else:
                    st_tmp.pop()
        if flag == False:
            break
    
    print(flag)
    

    后记

    如果觉得本文有帮助,欢迎点赞+收藏以提供博主源源不断的更文动力。另外欢迎关注个人公众号,二维码如下:
    Alt

    展开全文
  • 后进先出特性

    千次阅读 2018-04-01 19:48:21
    ,英文stack,特性是“先进后出”(很自然也就“后进先出”了),即First In Last Out,所以也称为Filo;就如楼上所说,仓库是个例子,再给你个更形象的例子,桶装薯片肯定吃过吧,假设薯片是机器一个一个放进去的...
    栈,英文stack,特性是“先进后出”(很自然也就“后进先出”了),即First In Last Out,所以也称为Filo;就如楼上所说,仓库是个例子,再给你个更形象的例子,桶装薯片肯定吃过吧,假设薯片是机器一个一个放进去的,你吃的第一个薯片肯定是最后放进去的(后进先出),而你吃的最后一片才是第一个放进薯片桶的(先进后出);由于栈的这种特性,可以暂时存储数据并以Filo的方式读取,所以是一个常用的数据结构并且可以在某些算法中提高效率。
    于此对应的是队列,英文queue,特性相反,为“先进先出”(自然后进后出了),First In first Out,固又名Fifo,就像你排队一样,先到先得,比如洗车通道,先进去的车,会先从出口出来,最后进的最后洗完。也是一种数据结构,可以提高效率。
    展开全文
  • 递归的本质(:后进先出)

    千次阅读 2019-03-26 20:43:19
    :就是后进先出的一种数据结构,所谓的后进先出就是:后入栈变量数据,先出栈计算处理. 递归:与类似,递归到最内层(到退出条件),开始从内层向外逐层调用函数自己计算处理. 帮助理解递归,写一个阶乘函数 ...

    栈:就是后进先出的一种数据结构,所谓的后进先出就是:后入栈变量数据,先出栈计算处理.

    递归:与栈类似,递归到最内层(到退出条件),开始从内层向外逐层调用函数自己计算处理.

    帮助理解递归,写一个阶乘函数

    factorial(4)    

            =    4 * factorial(3)
            =    4 * (3 * factorial(2) )
            =    4 * (3 * (2 * factorial(1) ) )
            =    4 * (3 * (2 * (1 * factorial(0) ) ) )

    本质自己调用自己4次,递归至factorial(0),先计算factorial(0)函数,然后逐层调用返回:factorial(1)、factorial(2)、factorial(3).

    #include<iostream>
    using namespace std;
    void Countdown(int n){  
      if(n>0){
        cout<<"Countdown:"<< n<< endl;
        Countdown(n - 1);
      }  
      cout<<"n:"<<n<< endl;
    }
    int main(){
      Countdown(4);
      return 0;
    }
    

    Countdown(n)函数不停的入栈(push),Countdown(4)先入的栈,所以在栈底,Coutdown(1)最后入的栈,所以在栈顶:如

                            Coutdown(1)     栈顶 后入栈,先处理

                            Coutdown(2)

                            Coutdown(3)

                            Coutdown(4)     栈底 先入栈,后处理

    栈是后进先出,一共调用4次Countdown()函数,这时先出栈(pop)的是栈顶Countdown(1),会打印n = 1;接着出栈(pop)的是Countdown(2),打印n = 2,依次类推3,4;注意打印的n=0是退出条件。

    Coutdown(4){ 
     Coutdown(3){ 
      Coutdown(2){
       Coutdown(1){ }  
      }  
     }
    }
    递归本质类似栈后进先出,递归至Coutdown(1)后,先计算Coutdown(1)函数,然后逐层调用返回:Coutdown(2)、Coutdown(3)、
    Coutdown(4).

    递归的本质和栈数据的存取(后进先出)很相似,都是后进去,但是往往先处理!再者对于递归函数的局部变量的存储是按照栈的方式去存的,对于每一层的递归函数在栈中都保存了本层函数的局部变量,一边该层递归函数结束时能够保存原来该层的数据。

    Reference

    展开全文
  • 具体而言,的数据结点必须后进先出。 宏观上来看,与数组或链表相比,的操作更为受限,那为什么我们要用这种受限的呢?其实,单纯从功能上讲,数组或者链表可以替代。然而问题是,数组或者链表的操作过于...

    1、栈是什么

    首先线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。
    是一种特殊的线性表。栈与线性表的不同,体现在增和删的操作。具体而言,栈的数据结点必须后进先出

    宏观上来看,与数组或链表相比,栈的操作更为受限,那为什么我们要用这种受限的栈呢?其实,单纯从功能上讲,数组或者链表可以替代栈。然而问题是,数组或者链表的操作过于灵活,这意味着,它们过多暴露了可操作的接口。这些没有意义的接口过多,当数据量很大的时候就会出现一些隐藏的风险。一旦发生代码 bug 或者受到攻击,就会给系统带来不可预知的风险。虽然栈限定降低了操作的灵活性,但这也使得栈在处理只涉及一端新增和删除数据的问题时效率更高。

    举个实际的例子,浏览器都有页面前进和后退功能,这就是个很典型的后进先出的场景。假设你先后访问了五个页面,分别标记为 1、2、3、4、5。当前你在页面 5,如果执行两次后退,则退回到了页面 3,如果再执行一次前进,则到了页面 4。处理这里的页面链接存储问题,栈就应该是我们首选的数据结构。

    栈既然是线性表,那么它也包含了表头表尾。不过在栈结构中,由于其操作的特殊性,会对表头和表尾的名字进行改造。表尾用来输入数据,通常也叫作栈顶(top);相应地,表头就是栈底(bottom)。栈顶和栈底是用来表示这个栈的两个指针。跟线性表一样,栈也有顺序表示和链式表示,分别称作顺序栈和链栈。

    2、栈的基本操作

    栈对于数据有增、删、查处理。对于栈的新增操作,通常也叫作 push 或压栈。对于栈的删除操作,通常也叫作 pop 或出栈。栈分为顺序栈和链栈。
    线性栈:
    栈的顺序存储可以借助数组来实现。一般来说,会把数组的首元素存在栈底,最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素,则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。当定义了栈的最大容量为 StackSize 时,则栈顶 top 必须小于 StackSize。

    当需要新增数据元素,即入栈操作时,就需要将新插入元素放在栈顶,并将栈顶指针增加 1。如下图所示:
    在这里插入图片描述
    删除数据元素,即出栈操作,只需要 top - 1 就可以了。

    对于查找操作,栈没有额外的改变,跟线性表一样,它也需要遍历整个栈来完成基于某些条件的数值查找。

    链栈:
    关于链式栈,就是用链表的方式对栈的表示。通常,可以把栈顶放在单链表的头部,如下图所示。由于链栈的后进先出,原来的头指针就显得毫无作用了。因此,对于链栈来说,是不需要头指针的。相反,它需要增加指向栈顶的 top 指针,这是压栈和出栈操作的重要支持。
    在这里插入图片描述
    对于链栈,新增数据的压栈操作,与链表最后插入的新数据基本相同。需要额外处理的,就是栈的 top 指针。如下图所示,插入新的数据,则需要让新的结点指向原栈顶,即 top 指针指向的对象,再让 top 指针指向新的结点。
    在这里插入图片描述
    在链式栈中进行删除操作时,只能在栈顶进行操作。因此,将栈顶的 top 指针指向栈顶元素的 next 指针即可完成删除。对于链式栈来说,新增删除数据元素没有任何循环操作,其时间复杂度均为 O(1)。

    对于查找操作,相对链表而言,链栈没有额外的改变,它也需要遍历整个栈来完成基于某些条件的数值查找。

    展开全文
  • -后进先出-java

    千次阅读 2017-01-14 16:11:37
    import java.util.Stack; /** * Created by yywang on 2017/1/14. */ public class f { ...用例 1,算术表达式求值 http://blog.csdn.net/u012063703/article/details/54427493
  • 后进先出(LIFO:last in first out) 例如:自助餐中的自取餐盘 面试题目:有六个元素6 5 4 3 2 1 的顺序进栈,哪一个不是合法的出栈序列: A. 5 4 3 6 1 2 B.4 5 3 2 1 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 ...
  • 1、是一种先进后出的顺序表,和顺序表的区别是:顺序表可以操作任意元素,但是只能对栈顶元素进行操作,即后进先出原则。 2、的操作就只有入栈和出栈两个。 3、实现入栈和出栈 的栈顶用top标识,入栈时...
  • (Stack)是一种特殊的线性表,其插入和删除操作均在表的一端进行,是一种运算受限的线性表 栈顶(top)是中允许插入和删除的一端。 底(bottom)是栈顶的另一端 #include<stdio.h> #include<stdlib.h&...
  • 后进先出”的

    2014-08-22 22:37:46
    的修改遵循后进先出的原则,因此又称为后进先出的线性表,简称LIFO结构。 一般采用数组作为其存储结构,这样做可以避免使用指针,简化程序,当然数组需要预先声明静态数据区的大小,但这不是问题,因为即便是...
  • 的操作就是针对栈顶元素,其特点就是后进先出。这里分别采用数组和单链表分别实现了一个顺序和链栈,并且共享了一个的应用: 单词逆序。
  • C#(后进先出)队列实现与解析

    千次阅读 2018-10-05 11:49:52
    集合类实现了【后入先出】(也是一种线性表),所有的插入(push)和删除(pop)(通常还有所有的访问)都在顶部进行。 Queue&lt;&gt;集合类实现了【先入先出队列】(也是一种线性表),所有的插入...
  • (LIFO:后进先出

    千次阅读 2017-07-20 21:55:56
    (一)LIFO  是一种限制插入和删除只能在一个位置上的表。这个位置就是栈顶(top)。普通的清空栈的操作和测试是否为空的操作,都是的指令系统的一部分。其中我们能对直接进行的操作只有基本操作:push...
  • 实现数据结构中的---后进先出LIFO

    千次阅读 2020-06-18 12:17:21
    书本整齐跨一叠在一起,最后放在最上面的那本最先拿走,生活中有很多后进先出的列子,就不一一说明了,用图来说明应该很好理解。 放在最上面的那本书的位置叫栈顶,栈顶是可变的,比如说你拿走了西游记,那么栈顶...
  • 形象点说,只有一个开口,先进去的就倒最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去,所以说先进后出,后进先出。 转自百度知道——影の黑骑士
  • //Stack 类表示后进先出(LIFO)的对象堆栈 //它提供了通常的 push 和 pop 操作,以及取顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到栈顶距离的 search 方法 //Stack 类表示...
  • 出栈:指数据的删除操作(数据也在栈顶)。 的实现:一般可以用数组或者链表,但是用数组实现更优一点,因为数组在尾插尾删上的代价较小。 下面,我们来实现支持动态增长的: typedef int STData...
  • 不得不知道的数据结构:
  • (stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为底。向一个插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶...
  • /*我们知道局部变量是保存在内存中,而内存是遵循“数据结构”即后进先出的*/ int a=10; // a进栈 int b=20; //b进栈 int c=30; //c进栈 System.out.println("b = "+b); //这里b被夹在a和c中间——这...
  • 有时也并称为“叠加”,因为最后压入的元素,第一个被“弹。经常用来类比的事物--装有弹簧的储物器中的自动托盘,最后装入的托盘总是最先取出。 Stack&lt;String&gt; stack = new Stack&...
  • "当前为空" ) else : self.stack.pop() def top (self) : if not self.stack: print( "当前为空" ) else : print(self.stack[- 1 ]) def bottom (self) : if not self.stack: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,944
精华内容 20,377
关键字:

栈后进先出怎么理解