精华内容
下载资源
问答
  • 后进先出链表
    2021-07-25 03:40:56

    【导语】在事业单位考试中,计算机专业知识的复习向来是考生复习备考阶段的一大重点,其中中公为计算机基础知识的复习为考生提供知识点梳理,帮助考生备考!

    后进先出表:在建立单链表时,将每次生成的新结点,总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行符‘n’作为输入结束标志,则建立带表头结点的后进先出单链表的算法如下:

    LinkList CreateList_fr( )

    {

    LinkList H,p;

    char ch;

    H =(LinkList)malloc(sizeof(

    ListNode)); /*生成表头结点*/

    if(!H)

    {

    printf("n 存储分配失败");

    exit(1);

    }

    H->next=NULL; /*表初值为空*/

    while((ch=getchar())!='n')

    {

    p=(LinkList)malloc(sizeof(

    ListNode)); /*生成新结点*/

    if(!p)

    {

    printf("n 存储分配失败");

    exit(1);

    }

    p->data=ch;

    p->next=H->next;

    H->next=p;/*插入表头结点之后*/

    }

    return(H); /*返回头指针*/

    }

    更多相关信息请访问事业单位考试资料网

    更多相关内容
  • 栈具有后进先出的特性,当你面对的问题需要高频使用新增删除操作,且新增和删除操作的数据执行顺序具备后来居上的相反关系时,栈就是个不错的选择。例如浏览器的前进和后退等功能 内容来源:《拉勾教育–重学数据...

    什么是线性表?

    线性表是 n 个数据元素的有限序列,最常用的是链式表达,通常也叫作线性链表或者链表。链表中存储的数据元素也叫作结点,一个结点存储的就是一条数据记录。每个结点的结构包括两个部分:

    • 第一是具体的数据值;

    • 第二是指向下一个结点的指针。

    栈是什么?

    栈是一种特殊的线性表。栈与线性表的不同,体现在增和删的操作。具体而言,栈的数据结点必须后进先出。

    后进的意思是,栈的数据新增操作只能在末端进行,不允许在栈的中间某个结点后新增数据。

    先出的意思是,栈的数据删除操作也只能在末端进行,不允许在栈的中间某个结点后删除数据。

    也就是说,栈的数据新增删除操作只能在这个线性表尾进行,即在线性表的基础上加了限制。

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

    顺序栈

            栈的顺序存储可以借助数组来实现。一般会把数组的首元素存在栈底,最后一个元素放在栈顶。当需要新增数据元素,即入栈操作时,就需要将新插入元素放在栈顶,并将栈顶指针增加 1

    删除数据元素,即出栈操作,只需要 将栈顶指针减1 就可以了。

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

    链栈

            关于链式栈,就是用链表的方式对栈的表示。通常,可以把栈顶放在单链表的头部。

    新增数据的压栈操作,与链表最后插入的新数据基本相同。需要额外处理的,就是栈的 指针。插入新的数据,则需要让新的结点指向原栈顶。

    在链式栈中进行删除操作时,只能在栈顶进行操作。因此,将栈顶的指针指向栈顶元素的 next 指针即可完成删除。对于链式栈来说,新增删除数据元素没有任何循环操作,其时间复杂度均为 O(1)。

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

    总结

            不管是顺序栈还是链栈,数据的新增、删除、查找与线性表的操作原理极为相似,时间复杂度完全一样,都依赖当前位置的指针来进行数据对象的操作。区别仅仅在于新增和删除的对象,只能是栈顶的数据结点。

            栈具有后进先出的特性,当你面对的问题需要高频使用新增删除操作,且新增和删除操作的数据执行顺序具备后来居上的相反关系时,栈就是个不错的选择。例如浏览器的前进和后退等功能

    内容来源《拉勾教育–重学数据结构与算法》

    展开全文
  • Stack栈后进先出

    2022-02-26 20:12:40
    Stack栈后进先出 栈 (stack)只允许在有序的线性数据集合的一端(称为栈顶 top)进行加入数据(push)和移除数据(pop)。后进先出(LIFO)。在栈中,push 和 pop 的操作都发生在栈顶。 栈常用一维数组或链表来实现,...

    Stack栈后进先出

    栈 (stack)只允许在有序的线性数据集合的一端(称为栈顶 top)进行加入数据(push)和移除数据(pop)。后进先出(LIFO)。在栈中,push 和 pop 的操作都发生在栈顶。 栈常用一维数组或链表来实现,用数组实现的栈叫作 顺序栈 ,用链表实现的栈叫作 链式栈 。

    问题:检查符号是否成对出现

     输入一个只包括 '<','>','{','}','[',']'的字符串str,判断字符串是否有效。
      有效字符串需满足:
      左括号必须用相同类型的右括号闭合。
      左括号必须以正确的顺序闭合。
     
      示例 1:
      输入:str = "<>"
      输出:true
     
      示例2:
      输入:str = "<>[]{}"
      输出:true
     
      示例3:
      输入:str = "<]"
      输出:false
     
      示例4:
      输入:str = "<[>]"
      输出:false
     
      示例5:
      输入:str = "{[]}"
      输出:true
    

    解决:

     public static boolean checked(String str){
            HashMap<Character, Character> hashMap = new HashMap<>();
            hashMap.put(']','[');
            hashMap.put('}','{');
            hashMap.put('>','<');
    
            Stack<Character> characterStack = new Stack<>();
            char[] chars = str.toCharArray();
            if((chars.length % 2)!=0){
                return false;
            }
            for (int i = 0; i < chars.length; i++) {
                if(hashMap.containsKey(chars[i])){
                    char topElement = characterStack.empty() ? '#' : characterStack.pop();
                    if (topElement != hashMap.get(chars[i])) {
                        return false;
                    }
                }else {
                    characterStack.push(chars[i]);
                }
            }
            return characterStack.isEmpty();
        }
    
    
    展开全文
  • 你好我是久远,我们来复习一下上周我们讲的知识。 什么是链表? 在计算机科学中,链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。 ...

    从博客查看此篇文章
    你好我是久远,我们先来复习一下上周我们讲的知识。

    • 什么是链表?

    在计算机科学中,链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。

    • 链表的优点

    由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比数组快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

    什么是栈

    栈有时也被称作堆栈或者堆叠。栈是有序集合,它的添加,移除操作总是发生在同一端,设这一端为顶端,则未执行操作的一端为底端。
    栈中的元素离底端越近,代表其在栈中的时间越长,最新添加的元素将被最先移除。这种排序原则被称作 LIFO(last-in first-out),即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端,旧元素则靠近底端。

    生活中的例子:

    在我们的生活中也很常见关于栈的例子,假设我们有一个放羽毛球的球桶,我们只能从桶的上面取出球,底部是不能取的,靠近开口的球,更先被取到。

    既然有取出的先后,那么我们的栈也算是有顺序的,我们依旧使用列表来实现栈的一些操作。

    举例来说,对于列表[1, 5, 3, 7, 8, 6],只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端,所有的操作就可以利用 append 和pop 等列表方法来实现。

    在这里我们视列表的尾部为栈顶,因此当进行 push 操作时,新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。

    栈的操作

    我们前面已经介绍了栈的基本情况,既然我们要实现栈的操作,那我们肯定要新建一个栈,有了这个栈,我们肯定要做一些彰显出栈特性的事情————出栈,入栈。还有我们常见的操作,判断是否为空,判断栈的大小等等。

    以下是我们要实现的方法:

    • Stack()创建一个空栈。不传任何参数,返回空栈。
    • push(item)将一个元素添加到栈的顶端。它需要一个参数 item,且无返回值。
    • pop()将栈顶端的元素移除。它不需要参数,但会返回顶端的元素,并且修改栈的内容。
    • peek()返回栈顶端的元素,但是并不移除该元素。它不需要参数,也不会修改栈的内容。
    • isEmpty()检查栈是否为空。它不需要参数,且会返回一个布尔值。
    • size()返回栈中元素的数目。它不需要参数,且会返回一个整数。

    栈的定义

    class Stack:
        def __init__(self):
            self.items = []
    

    定义一个 stack 类来告诉计算机,我们现在定义了一个全新的类型叫做 stack ,每个类有一个定义方法即 init() ,我们使用 init 方法来定义栈的一些属性。我们新建一个栈,栈中最重要的就是元素,多个元素构成栈,而一开始当我们没有向栈中放入任何元素时,栈是空的,因此有 self.items = [],我们定义了一个空栈来作为栈的初始化。

    栈是否为空

    既然栈存在,我们就可以进行栈有无的判断,我们也像之前的数据结构类型一样,引入 isEmpty() 方法来判断栈中是否有元素,没有元素则为空栈,返回 true ;包含有元素,则说明栈不为空,返回 false。

    def isEmpty(self):
            return self.items == []
    

    栈的大小

    栈的大小实际上就是判断栈中有多少元素,而我们使用列表来进行栈的实现,因此我们只需要使用 len() 方法计算引入的列表的长度即可判断栈中元素的多少了,即栈的大小。

    def size(self):
            return len(self.items)
    

    入栈操作

    现在我们既可以判断栈中是否有元素,又可以判断栈的大小了,那么接下来就要实现栈最主要的两个操作了,入栈和出栈。

    进行入栈操作我们就要想到,既然要把元素加入到栈中,那么我们就要传入一个参数去表示要加入到栈中的元素,然后将这个参数加入到栈中即可。

    def push(self, item):
            self.items.append(item)
    

    我们传入一个 item 参数,为我们要加入到栈中的元素,然后将其加入到我们引入的 items 列表中即可完成栈中元素的加入了。

    出栈操作

    既然有元素加入到栈中,那我们就可以将元素从栈中删除,因此我们有了出栈的操作,出栈操作一般的思维是这样的:我们让栈顶的元素弹出,同时也要告诉大家,我弹出的是哪个元素。

    因此要返回弹出的那个元素。

    代码实现为:

    def pop(self):
            return self.items.pop()
    

    使用列表中的 pop方法,返回列表末尾的那个元素,并将该元素从列表中删除,实现出栈。

    查看栈顶

    我们的栈操作中通常还包含一项查看栈顶元素的操作,因为我们在此将引入的列表末尾视为栈顶,因此我们只需要返回所引入的列表的最后一个元素即可。

    def peek(self):
            return  self.items[len(self.items)-1]
    

    整体的代码如下:

    class Stack:
        def __init__(self):
            self.items = []
        def isEmpty(self):
            return self.items == []
        def size(self):
            return len(self.items)
        def push(self, item):
            self.items.append(item)
        def pop(self):
            return self.items.pop()
        def peek(self):
            return  self.items[len(self.items)-1]
    

    总结

    恭喜你又学完了一个知识点,栈是一个后进先出的数据类型,它有两个非常主要的操作,进栈和出栈:

    • 进栈:将资料放入栈的顶端,栈的顶端移到新放入的资料。
    • 出栈:将堆栈顶端资料移除,堆栈顶端移到移除后的下一笔资料。

    它可以用数组或者链表来实现,而由于 python 的特殊性,我们常使用列表来实现栈的操作。

    与栈相对的有队列,队列是一种先进先出的数据类型,我们下次会进行讲解。

    流沙团队联合AI悦创|久远·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!


    在这里插入图片描述

    展开全文
  • Python 栈(后进先出

    2020-11-26 04:08:05
    Python 栈,栈是含有一组对象的容器,支持快速后进先出(LIFO)的插入和删除操作。与列表或数组不同,栈通常不允许随机访问所包含的对象。插入和删除操作通常称为入栈(push)和出栈(pop)。现实世界中与栈数据结构...
  • 栈--后进先出的线性表

    千次阅读 2020-06-11 20:49:23
    具体而言,栈的数据结点必须后进先出。 宏观上来看,与数组或链表相比,栈的操作更为受限,那为什么我们要用这种受限的栈呢?其实,单纯从功能上讲,数组或者链表可以替代栈。然而问题是,数组或者链表的操作过于...
  • 一:先进先出 #include <iostream> using namespace std; struct student { long num; float score; student *next; }; student* create() //定义函数。此函数带回一个指向链表头的指针 { student...
  • 栈这种数据结构,不就后进先出

    千次阅读 2021-04-26 10:36:25
    原创不易 还请一键三连支持 什么是栈 栈在我们日常编码中遇到的非常多,很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException,栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化...
  • 栈:后进先出的线性表如何实现增删查1)栈是什么?2)栈的基本操作 线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。在有序排列的数据中,可以灵活的执行增删操作,...
  • 从尾到头打印链表

    2019-02-14 16:45:57
    题目:输入一个链表的头节点,从尾到头反过来打印出每个节点的值。链表节点定义如下: ...这是典型的“后进先出”,我们很容易就能想到栈这种数据结构可以实现这种顺序。每当我们经过一个节点,就把这个节点压入栈...
  • 使用链表进行模拟栈比用数组好用,考虑的要素也少还方便。 链表结构 private class Node{//链表结构 Item item; Node next; } 迭代器 private class Iterator implements java.util.Iterator<Item>{//迭代...
  • * 文件描述:使用堆栈存储模型(后进先出)来挂载链表数据 * 头部插入链表方式相当于堆栈模型的存储模式 * 编辑人:王廷云 * 编辑日期:2017-11-12 * 修改日期:2018-2-1 *********************...
  • 实现数据结构中的栈---后进先出LIFO

    千次阅读 2020-06-18 12:17:21
    书本整齐跨一叠在一起,最后放在最上面的那本最先拿走,生活中有很多后进先出的列子,就不一一说明了,用图来说明应该很好理解。 放在最上面的那本书的位置叫栈顶,栈顶是可变的,比如说你拿走了西游记,那么栈顶...
  • 因为栈限定在表尾进行插入或者删除,所以栈又被称为后进先出的线性表(简称LIFO:Last in, First out.结构)。 用链表实现栈,仅仅限定在头指针和尾指针,可以将头指针作为栈低,尾指针作为栈顶,所以对栈的操作也就...
  • 栈区的使用规则、压栈和出栈、栈区先进后出,后进先出
  • 定义类: public class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; this.next = null; } public int getVal() { return val; } ... this.val
  • Queue是先进先出的集合而Stack是后进先出的集合。这两个集合在日常的工作中也经常会用到。Queue相当我们去银行柜台排队,大家依次鱼贯而行。Stack象我们家中洗碗,最后洗好的碗叠在最上面,而下次拿的时候是最先拿到...
  • 【剑指offer】链表

    2021-06-20 09:48:58
    解法2:官方是利用的栈的存储方式,因为栈的特点就是后进先出。从链表的头节点开始,依次将每个节点压入栈内,全部入栈后,依次弹出栈内的元素并存储到数组中。 源代码 解法1: public int[] reversePrint...
  • 这个说起来也简单就是把1-2-3-4-5这样的链表逆序构建或打印出来5-4-3-2-1。比如用后进先出的栈的特性来做:就是按照链表的顺序把数据压入栈中,再打印栈
  • 看下数据结构中一种重要的数据存储形式,链表,下面两段是来自百度百科: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每...
  • 栈的数据结点被限制为后进先出,这意味着栈的数据新增操作只能在末端进行,不允许在栈的中间某个结点后新增数据。同时,栈的数据删除操作也只能在末端进行,不允许在栈的中间某个结点后删除数据。 因此,可以说栈是...
  • 输入链表的第一个节点,从尾到头反过来打印出每个结点的值。02.问题分析对于这种颠倒顺序的问题,我们应该就会想到栈,后进先出。所以,这一题要么自己使用栈,要么让系
  • 在Linux 内核中使用最多的数据结构就是链表了,其中就包含了许多高级思想。比如面向对象、类似C++模板的实现、堆和栈的实现。1. 链表简介链表是一种常用的组织有序数据的数据结构,...
  • 线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删...栈是特殊的线性表,栈的数据结点必须后进先出后进的意思是,栈的数据新增操作只能在末端进行,不允许在栈的中间某个结点后新增
  • 链表——基本算法

    2022-01-18 23:19:20
    1、反转链表 ...给3个指针,一个cur,用于遍历链表中的每个节点,一个prev,用于保存cur指向的节点的上一个节点地址,还有一个after,用于保存cur指向的节点的下一个节点地址,链表操作遵循连后断,即 ...
  • 栈的操作就是针对栈顶元素,其特点就是后进先出。这里分别采用数组和单链表分别实现了一个顺序栈和链栈,并且共享了一个栈的应用: 单词逆序。
  • 1、栈是一种先进后出的顺序表,和顺序表的区别是:顺序表可以操作任意元素,但是栈只能对栈顶元素进行操作,即后进先出原则。 2、栈的操作就只有入栈和出栈两个。 3、实现入栈和出栈 栈的栈顶用top标识,入栈时...
  • c++基础知识——STL之链表

    千次阅读 多人点赞 2022-05-02 22:40:46
    STLzhi链表,想学习c++ 的朋友可以看过来了,带你学会c++中的链表;

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,075
精华内容 12,830
关键字:

后进先出链表