栈和队列技术文章

简介: 栈和队列技术文章

栈和队列


**线性表:**连续的,每个元素都有唯一的前驱和后继

数组和链表

数组

地址是连续的

随机访问公式:数组起始地址 + 下标 * 数组单个存储单元的大小

链表

形象地说,链表就是用一串链子将结点串联起来。


结点:包含数据域和指针域。

数据域:数据

指针域:下一个结点的地址


单链表: 除了尾结点, 每一个结点都有一个后继结点


循环链表: 尾结点的下一个结点指向头结点


双线链表: 有后继结点还有前驱结点


双向循环链表: 尾结点的下一个指向头, 头结点之前指向尾结点

常用的是双链表

取中间值和判断链表是否有环的常用方法:快慢指针

反转链表:头插法

泛型

泛型: 参数化类型 ()

事先不指定数据类型,等到使用的时候再确定

泛型的好处

a. 提高了程序的安全性

b. 将运行期遇到的问题转移到了编译期

c. 省去了类型强转的麻烦

泛型的使用

泛型类
// 把泛型定义到类上, 就是泛型类

泛型类: 把泛型定义在类上
格式:class 类名 <泛型类型1,…>
注意:参数化类型必须是引用类型
    
// 注意2: 如果某一个代码中我们使用的时候应该传入泛型, 但是我们没有传, 那么它默认是Object类型
     User user = new User("zs", 18);
        Object age2 = user.getAge();

// 注意3: 注意一些泛型定义的习惯问题
        // 给泛型定义的时候: 习惯上
        // T: type
        // E: element
        // K: key
        // V: value

// 注意4: 不要给一个类定义超过两个泛型(不是语法不允许),  习惯上显得怪异

// 注意5: 在泛型类上定义的泛型, 作用域, 仅仅局限于类名和类体内

泛型的通配

泛型通配符:

① 泛型通配符<?>
任意类型,如果没有明确,那么就是Object以及任意的Java类了
② ? extends E
向下限定,E及其子类
③ ? super E
向上限定,E及其父类

     ArrayList<?> list = new ArrayList<Character>();
        // 报错的原因: 因为从编译角度, 仅能推断出?代指一个不确定的类型
        //        从java语法角度, 一个不确定的类型, 没有存储其它类型(String存储Integer肯定无法运行)
        // 为了避免运行时出现问题, 直接不让添加
        // list.add("zs");// 报错:
        // list.add(new Object());// 报错

ArrayList<? extends F> list = new ArrayList<S2>();
        // 报错的原因: 因为从编译角度, 仅能推断出? extends F代指一个不确定的f或者f的子类型
        //        从java语法角度, 一个不确定的类型, 没有存储其它类型
        // 为了避免运行时出现问题, 直接不让添加
        //list.add("zs");//报错
        //list.add(new Object());//报错
        //list.add(new F());//报错
        //list.add(new S1());//报错

        ArrayList<? super F> list = new ArrayList<F>();
        // list.add("zs");//报错
        // list.add(new Object());//报错
        list.add(new F());
        list.add(new S1());
        list.add(new S2());

class F {}
class S1 extends F{}
class S2 extends F{}

泛型擦除

java中的泛型并不是真正的泛型, java中的泛型只存在于代码编译之前, 代码编译的时候, 这些泛型的写法统统会被擦除, 变成Object以及类型强转.

FILO

链表实现栈时运用头插法

栈的应用

应用场景:

  1. 函数调用栈
  2. 反序字符串
    实现reNumber(str)方法,反转字符串
  3. 括号匹配问题
    实现judgeBracket(str)方法来判断括号匹配
  4. 编译器利用栈实现表达式求值
  5. 浏览器的前进后退功能
  6. 利用栈实现 DFS: depth-first-search 深度优先遍历
  7. 波兰表达式

队列

FIFO

用链表实现队列时,头节点作为队列头实现出队列,尾节点作为队列尾实现入队列

普通队列的应用场景是很有限的,一般在工程中用到的是阻塞队列。

阻塞队列:常用于生产者-消费者模型中。

队列大小固定:

当队列满的时候,入队列就阻塞。

当队列空的时候,出队列就阻塞。

队列应用场景:

缓存

相关文章
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
37 1
|
28天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
54 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
50 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
215 9
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
52 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
48 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
65 10