java打印对象内存地址 分布式事务 事务消息 分布式事务 几种解决方案 分布式事务-Seata 分布式事务-Seata 分布式事务-LCN-TCC 分布式事务-LCN 分布式事务-消息队列-定时任务-本地事件表 Zuul网关实战02 Zuul网关实战01 灰度发布落地实战2 灰度发布落地实战1 Gsnova on Heroku build Systemd Debian system initialization manage multi id_rsa ubuntu 64bits cannot run 32bits app REHL power auditing Debug Assembly for ARMv8 on QEMU ARM体系结构--寄存器 Run Debian iso on QEMU ARMv8 QEMU ARM64 guide cross compiler install buildroot install QEMU install python入门--数据结构 python入门--内置数据类型 python入门--类 异常 python入门--条件表达式 方法 python入门--数字 字符串 数组 RTC驱动分析 块设备驱动 TCP UDP socket 触摸屏驱动 USB驱动 LED按键中断 LCD 驱动 驱动信号 根文件系统 实验 内核实验 字符设备驱动程序 绪论 uboot 实验 LCD 实验 系统时钟和UART 中断控制器 Nand Flash控制器 MMU 实验 储存管理器实验 GPIO实验 点亮LED 编译加载驱动 制作烧写内核 dnw替代方法 MINI2440 TQ2440安装配套Linux 使用NFS 制作烧写跟文件系统 grub引导Windows 烧写裸版程序-linux Ubuntu 网络没有 eth0 Linux自动挂载 烧写裸板程序 电路基础 Mac词典 Vim插件 Assembly 综合研究 Assembly 指令总结 Assembly 直接定址表 Assembly 使用BIOS进行键盘输入和磁盘读写 Assembly 外中断 Assembly 端口 Assembly int指令 Assembly 内中断 Assembly 标志寄存器 Assembly 转移指令的原理 Assembly Call和ret指令 Assembly 数据处理两个基本问题 Assembly 灵活定位内存地址 Assembly 包含多个段的程序 Assembly [bx] loop Assembly 第一个程序 Assembly 寄存器 (内存访问) Assembly 寄存器 AWS VPN with EC2 hidden file in picture(linux) Assembly 基础 idea shortcuts 常用快捷键 idea plugin folder install ruby and jekyll

Stack Queue

2020年10月31日

栈和队列

栈和队列的实际实现

双向链表

数组实现

应用一:怎么用数组实现不超过固定大小的栈

ring buffer

pushi, popi, size, limit

用 size 约束了 pushi 和 popi 追赶问题

应用二:实现一个特殊的栈,在基本功能的基础上,再实现返回栈中最小元素的功能

pop push getMin操作的时间复杂度都是O(1)

设计的栈类型可以使用现成的栈结构

  1. data栈,min栈,同时往里面放,空间换时间,占用空间大,弹出不用做判断
  2. data栈,min栈,只有新data < min 时才往里放,时间换空间,占用空间更小,但是弹出做判断

应用三:如何用栈结构实现队列结构

两个栈 stackPush 和 stackPop

stackPush 写入 1 2 3 4 5

挨个执行pop操作,导入到 stackPop,5 4 3 2 1

用户返回时,直接返回 stackPop.pop()

要保证2个原则:

  1. stackPop为空的时候才能导入,用户输入 1 2 3 4 5之后,弹出5,又写个6,此时6不应该进stackPop
  2. 如果决定导数据到statckPop,一定要一次性的从stackPush导到stackPop导完,别导一半

应用四:如何用栈结构实现队列结构

两个队列data 和 helper

data 写入 1 2 3 4 5

将 1 2 3 4 导入到 helper,留着 5 不导入,给用户弹出返回

下一回,helper变成 data,data变成helper,继续这么干

应用五:图,的宽度遍历使用的队列,深度遍历使用的栈

问,用栈实现图的宽度遍历,用队列实现图的深度遍历,怎么做

用2个栈,拼出一个队列搞宽度

用2个队列,拼出一个栈搞深度

递归的底层实现,依赖系统的栈

递归的时间复杂度

T(N) = a*T(N/b) + O(N ^ d)

哈希表一律按值传递包括String

非基础类型的Key按引用传递,即使Key对象有20G大小,也只会存一个内存地址