数据结构与算法之美08

数据结构与算法之美08

一、什么是栈?1.后进者先出,先进者后出,这就是典型的“栈”结构。2.从栈的操作特性来看,是一种“操作受限”的线性表,只允许在端插入和删除数据。二、为什么需要栈?1.栈是一种操作受限的数据结构,其操作特性用数组和链表均可实现。2.但,任何数据结构都是对特定应用场景的抽象,数组和链表虽然使用起来更加灵活,但却暴露了几乎所有的操作,难免会引发错误操作的风险。3.所以,当某个数据集合只涉及在某端插入和删除数据,且满足后进者先出,先进者后出的操作特性时,我们应该首选栈这种数据结构。三、如何实现栈?1.栈的APIpublic class Stack<Item> {//压栈public void push(Item item){}//弹栈public Item pop(){}//是否为空pu

数据结构与算法之美07

数据结构与算法之美07

链表(下):如何轻松写出正确的链表代码? 一、理解指针或引用的含义1.含义:将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。2.示例:p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。 二、警惕指针丢失和内存泄漏(单链表)1.插入节点在节点a和节点b之间插入节点x,b是a的下一节点,,p指针指向节点a,则造成指针丢失和内存泄漏的代码:p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。正确的写法是2句代码交换顺序,即:x—>next =

评判代码优劣的标准

评判代码优劣的标准

默认6分代码风格有问题扣1分代码有明显的设计问题,耦合严重扣1分逻辑有明显功能或性能问题扣1-2分没有单元测试扣1分通过各种模式解耦和提高扩展性加1分优化高并发下的性能问题加1分代码本身有一定技术挑战加1分引入或者实现新框架解决通用问题加1分 每个人自行选择过去半年里自己认为写的最好的代码,向我介绍他写的代码好在哪里。 转自 蛋疼的axb 的微博

约瑟夫环问题

约瑟夫环问题

约瑟夫环问题,这是一个很经典算法,处理的关键是:伪链表 问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。

数据结构与算法之美06

数据结构与算法之美06

链表(上):如何实现LRU缓存淘汰算法? 一、什么是链表?1.和数组一样,链表也是一种线性表。2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。 二、为什么使用链表?即链表的特点1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。 三、常用链表:单链表、循环链表和双向链表1.单链表1)每个节点只包含一个