【数据结构真不难】栈与队列——五一专属|向所有热爱分享的“技术劳动者”致敬

2023-10-25 01:10
文章标签 技术 专属 数据结构 队列 所有 分享 不难 热爱 致敬 劳动者 五一

本文主要是介绍【数据结构真不难】栈与队列——五一专属|向所有热爱分享的“技术劳动者”致敬，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 💂 个人主页: 陶然同学
  • 🤟 版权: 本文由【陶然同学】原创、在CSDN首发、需要转载请联系博主
  • 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
  • 💅 想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

目录

1.概述

2.栈

        2.1定义

        2.2出入栈练习(卡特兰数)

3.顺序栈

        3.1定义

        3.2栈类

        3.3算法：入栈【重点】

        3.4算法：出栈【重点】

4.链栈

        4.1定义

        4.2栈类

        4.3算法：入栈

        4.4算法：出栈

5.栈的应用

        5.1大数加法

        5.2后缀表达式

        5.3汉诺塔Hanoi

6.队列

        6.1定义

7.顺序队列

        7.1顺序队列

        7.2循环顺序队列

        7.3循环顺序队列类

        7.4算法：循环顺序队列入队

        7.5算法：循环顺序队列出队

8.链队列

        8.1定义

        8.2链队列类

        8.4算法：链队列入队

        8.5算法：链队列出队

9.优先级队列

        9.1定义

        9.2优先级队列相关类

        9.3算法：优先级队列入队

10.递归

        10.1定义

        10.2算法：1-n和

        10.3算法：n!

        10.4算法：斐波那契数

11.最后

1.概述

  • 比较重要，且应用广泛的两种线性结构：栈 Stack、队列 Queue。

  • 栈和队列 与 线性表不同之处：栈和队列可被看成是两种操作受限的特殊线性表。

2.栈

        2.1定义

  • 栈是一个特殊的线性表，插入和删除只允许在栈顶Top(线性表的尾端)进行操作。

  • 术语：

    • 栈顶Top：允许进行插入和删除的一端。

    • 栈底Bottom

    • 入栈push：栈的插入操作。

    • 出栈pop：栈的删除操作。

  • 栈特点：后进先出（Last In First Out、LIFO）、先进后出（First In Last Out、FILO）。

        2.2出入栈练习(卡特兰数)

  • 需求：若将ABCD依次入栈，则出栈的序列是？（进出栈可以交替进行）

// 入栈个数 1/2/3/4
Ain Aout Bin Bout Cin Cout Din Dout --> ABCD
Ain Aout Bin Bout Cin Din Dout Cout --> ABDC
Ain Aout Bin Cin Cout Din Dout Bout --> ACDB
Ain Aout Bin Cin Cout Bout Din Dout --> ACBD
Ain Aout Bin Cin Din Dout Cout Bout --> ADCB

Ain Bin Bout Aout Cin Cout Din Dout --> BACD
Ain Bin Bout Aout Cin Din Dout Cout --> BADC
Ain Bin Bout Cin Cout Aout Din Dout --> BCAD
Ain Bin Bout Cin Cout Din Dout Aout --> BCDA
Ain Bin Bout Cin Din Dout Cout Aout --> BDCA

Ain Bin Cin Cout Din Dout Bout Aout --> CDBA
Ain Bin Cin Cout Bout Din Dout Aout --> CBDA
Ain Bin Cin Cout Bout Aout Din Dout --> CBAD

Ain Bin Cin Din Dout Cout Bout Aout --> DCBA

进出栈是最经典的卡特兰数

「算法入门笔记」卡特兰数 - 知乎

3.顺序栈

        3.1定义

  • 顺序栈：使用数组实现的栈。

  • 约定：

    • 空栈：top == 0

    • 满栈：top == stackElem.length

    • 长度：top

    • 栈顶元素：stackElem[top - 1]

        3.2栈类

public class SqStack {private Object[] stackElem;			//栈对象数组private int top;					//长度、下一个存储位置 等
}

        3.3算法：入栈【重点】

  • 算法1：

public void push(Object x){if(top == stackElem.length){throw new RuntimeException("栈满");}else{stackElem[top] = x;top++;}
}

  • 算法2：

public void push(Object x){if(top == stackElem.length){throw new RuntimeException("栈满");}else{stackElem[top++] = x;}
}

        3.4算法：出栈【重点】

 算法1：

public Object pop(){if(top == 0){return null;}else{top--;return statckElem[top];}
}

算法2：

public boolean isEmpty(){return top == 0;
}
public Object pop(){if(isEmpty()){return null;}else{return statckElem[--top];}
}

4.链栈

        4.1定义

  • 使用链式存储的栈，就是链栈。进行插入和删除操作在栈顶进行，也就是链表的尾端。

  • 存储单元2部分组成：数据域 data 和指针域 next。

  • 使用top栈顶指针用于指向栈尾。

        4.2栈类

public class LinkStack {private Node top;			//栈顶指针
}

        4.3算法：入栈

  • 需求：将新结点p，压入到栈顶

public void push(Object x){Node p = new Node(x);p.next = top;top = p;
}

        4.4算法：出栈

需求：弹出栈顶元素，需要返回数据

public Object pop(){if(top == null){return null;}else{Node p = top;top = top.next;return p.data;}}

5.栈的应用

        5.1大数加法

9992992347234947324732498327427342472987427427984724274
+ 
   9990920943824283492834824820984028348204209384029293

  • 思路：9293 + 978

        5.2后缀表达式

中序表达式：日常生活中编写的都是中序表达式。

a + b - c

后缀表达式：把运算符写在后面的表达式，也称为逆波兰记法

中序：a+b                后缀：ab+
中序：a + b - c        后缀：ab+c-
中序：a + b * c        后缀：abc*+

    • 除运算符之外的内容，依次填写

    • 使用一个栈记录运算符

      • 入栈：新入栈的运算符比栈里的运算符优先级要高。如果是(进行入栈操作

      • 出栈：新入栈的运算符没有栈里的运算符优先级高，栈里的运算符需要出栈，新运算符入栈。如果是)出栈直到(

  • 将以下中序表达式转换成后续表达式

中序：8-(3+2*6)/5+2^2            后缀：8326*+5/-22^+
中序：2*9+3-2*(10-3)/14        后缀：29*3+2103-*14/-
中序：A+B*(C*D-E)              后缀：ABCD*E-*+
中序：a+b*c+(d*e+f)*g           后缀：abc*+de*f+g*+
中序：9+(3-1)*3+10/2           后缀：931-3*+102/+

        5.3汉诺塔Hanoi

  • 游戏规则 

共3个柱子，在一根柱子上，从下往上按照大小顺序摞着N片圆盘。把圆盘开始按大小顺序重新摆放在另一根柱子上
规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

  • 算法

package hanoi;public class TestHanoi {private static int count = 0;/**** @param n 需要移动的盘子数* @param x 第一个柱子 起始* @param y 第二个柱子 过渡* @param z 第三个柱子 最后*/public static void hanoi(int n, char x, char y , char z) {if(n == 1) {      //只有一个盘子move(x, 1, z);} else {hanoi(n-1, x, z ,y);     // n上面的盘子，从x柱子，通过z柱子，移动到y柱子move(x, n, z);              //n盘子，从x柱子，移动到z柱子hanoi(n-1, y, x, z);    // n上面的盘子目前在y柱子，从y柱子，通过x柱子，移动到z柱子。}}/**** @param x 第一个柱子* @param n 需要移动的盘子号* @param z 第三个柱子*/private static void move(char x, int n, char z) {count++;System.out.println("第"+count+"次移动"+n+"号盘子，从"+x+"柱子到"+z+"柱子");}public static void main(String[] args) {hanoi(4,'x','y','z');}
}

6.队列

        6.1定义

  • 队列是一个特殊的线性表。

    • 只允许在表尾进行插入操作

    • 只允许在表头进行删除操作

  • 队列操作特点：

    • 先进先出（FIFO，First In First Out）

    • or 后进后出（LILO，Last In Last Out）

  • 术语：

    • 队尾rear：进行插入操作的一端。

    • 队首front：进行删除操作的一端。

    • 入队offer：进行插入操作，称为入队。

    • 出队poll：进行删除操作，称为出队。

队列两种存储结果分类：

* 使用顺序存储的称为顺序队列
* 使用链式存储称为链队列。

7.顺序队列

        7.1顺序队列

  • 顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。

  • 操作总结：

    • front表示队首，进行出队操作时，front进行计数。

    • rear表示队尾，进行入队操作时，rear进行计数。

    • front == rear == 0 空队列。

  • 操作步骤：

    • 入队操作：

  •  出队操作

存在问题：假溢出，数组的最后一个元素已经添加数据，但队列没有满。

 解决方案：使用循环顺序队列解决“假溢出”问题。

        7.2循环顺序队列

  • 循环顺序队列：就是在逻辑上队首和队尾连接在一起。

  • 存在问题：队首front和队尾rear重叠时，无法表示队列是满了，还是空的。

  • 解决方案：

    • 方案1：设计一个计数器（整数变量num，入队+1，出队-1，如果num=0就是空）

    • 方案2：设计一个标识变量（flag=0出队，flag=1入队，重叠后0表示空，1表示满）

    • 方案3：少用一个存储单位

// 队列空
front == rear;
// 队列满
(rear + 1) % maxSize == front;
    

//余数操作
5 % 5 = 0;
2 % 5 = 2;

        7.3循环顺序队列类

循环顺序队列，在逻辑上是一个循环，也就是队首和队尾连接。

循环顺序队列，物理上就是一个数组。

public Class CircleQueue {private Object[] queueElem;		//物理数组private int front;				//队首private int rear;				//队尾
}

        7.4算法：循环顺序队列入队

public void offer(Object x) {if( (rear+1) % queueElem.length == front ) {  // 1.判断，如果已经满了，抛异常throw new RuntimeException('队列满了');} else {queueElme[ rear ] = x;					 // 2.没有满进行入队操作rear = (rear + 1) % queueElem.length;	 // 3.队尾rear累加1，但最后时需要归零}
}

        7.5算法：循环顺序队列出队

public Object poll() {if( front == rear ) {						// 判断 空 返回nullreturn null;} Object data = queueElem[front];				// 如果不为空，获得队首front元素front = (front + 1) % queueElem.length;		// 队首+1，且需要归零  return data;
}

8.链队列

        8.1定义

链队列：使用链式存储的队列，使用不带头结点head的单链表。

  • front结点：队首元素

  • rear结点：队尾元素

        8.2链队列类

public class LinkQueue {private Node front;		//队首（出队/删除）private Node rear;		//队尾（入队/插入）
}

        8.4算法：链队列入队

分析：

非空

 空

public void offer(Object x) {Node p = new Node(x);if(front == null) {		//空front = rear = p;//front = p;//rear = p;} else {				//非空rear.next = p;		//1.尾指针的指针域指向新结点rear = p;			//2.尾指针指向队尾}
}

        8.5算法：链队列出队

分析：空队列、一个元素、很多元素

  • 很多元素

一个元素：需要额外的处理队尾，将其设置成null

  • 空队列：返回null即可

public Object poll() {if(front != null) {		//非空Node p = front;				//记录队首元素front = front.next;			//队首移动到下一个if(p == rear) {					//只有一个元素时，队首和队尾相同rear = null;				//队首已经是null，队尾也应该是null}return p.data;				//返回之前队首元素的数据} else {				//空return null;}
}

9.优先级队列

        9.1定义

  • 优先级队列：就是一种带优先级的队列，也就是内部需要根据关键字的值进行排序的队列。

    • 与普通队列基本操作一致，队首删除。

    • 区别：进行==插入==操作时，不在是队尾，对队伍中找到合适的位置。

  • 优先级队列也可以使用两种存取方式，但常用链式存储。

    • 默认队列

 插入操作：数字小的优先级越高

        9.2优先级队列相关类

 数据对象：数据元素的值、结点的优先级

/*{ elem: a, priority: 1}
*/
public class PriorityData {public Object elem;				//数据元素的值public int priority;			//结点的优先级
}

队列对象

public class PriorityQueue {private Node front;		//队首private Node rear;		//队尾
}

数据之间关系

node.next        //指针域
node.data        //数据域，存放的数据类型是 PriorityData

        9.3算法：优先级队列入队

  • 需求：数字越==小==优先级越高。

  • 分析：

    • 前提：从队首进入，依次进行比较

    • 情况1：队首插入（p如果指向队首front，表示新结点优先级的数字小）

情况2：队尾插入 （q为null 或 p等于队尾rear）

 情况3：剩余的中间

public void offer(PriorityData x) {Node s = new Node(x);				//构建新结点// 如果空if(front == null) {		//空front = rear = s;} else {				//非空// 1) 移动：按照优先级进行移动，优先级大就需要继续移动Node p = front;		//用于记录前驱（之前的）Node q = front;		//用于记录下一个while( q != null && (x.priority >= q.data.priority )) {p = q;			//记录前驱q = p.next;}// 2) 插入if(q==front) {			// 2.1 队首s.next = front;			//新结点s指向队首frontfront = s;				//队首指针，指向队列的开始} else if (q == null) {	// 2.2 队尾rear.next = s;			//队尾指针域next,指向新结点rear = s;				//队尾指针，指向队尾} else {				// 2.3 中间p.next = s;s.next = q;}}
}

10.递归

        10.1定义

  • 程序调用自身的编程技巧称为递归（ recursion），由两部分组成：递推、回归。

    • 递推：方法依次调用，没有返回。

    • 回归：程序准备依次返回。

        10.2算法：1-n和

package recursion;public class TestSum {public static void main(String[] args) {System.out.println(sum(10));}/*** 求1-n的和* @param n* @return*/private static int sum(int n) {if(n == 1) {return 1;}return n + sum(n-1);}
}

        10.3算法：n!

package recursion;public class TestFactorial {public static void main(String[] args) {System.out.println(factorial(4));}private static int factorial(int n) {if(n == 1) {return 1;}return n * factorial(n-1);}
}

        10.4算法：斐波那契数

  • 定义

0、1、1、2、3、5、8、13、21、34 .... n
固定值
f(0) = 0
f(1) = 1
后面的每一项都是前两项的和
f(2) = f(0) + f(1)
f(n) = f(n-1) + f(n-2)

  • 算法

package recursion;public class TestFibonacci {public static void main(String[] args) {// 斐波那契数列for(int i = 0 ; i <= 10 ; i ++) {System.out.print(fibonacci(i) + "、");}}/*** 计算斐波那契数列的第n项* f(0) = 0* f(1) = 1* ...* f(n) = f(n-1) + f(n-2)* @param n* @return*/private static int fibonacci(int n) {if(n == 0) {return 0;}if(n == 1) {return 1;}return fibonacci(n-1) + fibonacci(n-2);}
}

11.最后

        我们的数据结构就结束了 欢迎大家添加博主交流 练习过程中遇到问题也可以提供支持 如果需要学习资料 博主也可以推荐

        最后 如果觉得文章对您有帮助 请给博主点赞、收藏、关注 博主会不断推出更多优质文章

这篇关于【数据结构真不难】栈与队列——五一专属|向所有热爱分享的“技术劳动者”致敬的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/279019。

相关文章

如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
linux进程D状态的解决思路分享

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态（D状态）,这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.
阅读更多...
使用Navicat工具比对两个数据库所有表结构的差异案例详解

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》：本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较：二、开始比较总结概要公司存在多
阅读更多...
MySQL8.2.0安装教程分享

MySQL8.2.0安装教程分享

《MySQL8.2.0安装教程分享》这篇文章详细介绍了如何在Windows系统上安装MySQL数据库软件,包括下载、安装、配置和设置环境变量的步骤... 目录mysql的安装图文1.python访问网址2javascript.点击3.进入Downloads向下滑动4.选择Community Server5.
阅读更多...
CentOS系统Maven安装教程分享

CentOS系统Maven安装教程分享

《CentOS系统Maven安装教程分享》本文介绍了如何在CentOS系统中安装Maven,并提供了一个简单的实际应用案例,安装Maven需要先安装Java和设置环境变量,Maven可以自动管理项目的... 目录准备工作下载并安装Maven常见问题及解决方法实际应用案例总结Maven是一个流行的项目管理工具
阅读更多...
10个Python自动化办公的脚本分享

10个Python自动化办公的脚本分享

《10个Python自动化办公的脚本分享》在日常办公中,我们常常会被繁琐、重复的任务占据大量时间,本文为大家分享了10个实用的Python自动化办公案例及源码,希望对大家有所帮助... 目录1. 批量处理 Excel 文件2. 自动发送邮件3. 批量重命名文件4. 数据清洗5. 生成 PPT6. 自动化测试
阅读更多...
10个Python Excel自动化脚本分享

10个Python Excel自动化脚本分享

《10个PythonExcel自动化脚本分享》在数据处理和分析的过程中,Excel文件是我们日常工作中常见的格式,本文将分享10个实用的Excel自动化脚本,希望可以帮助大家更轻松地掌握这些技能... 目录1. Excel单元格批量填充2. 设置行高与列宽3. 根据条件删除行4. 创建新的Excel工作表5
阅读更多...
解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列？消费者组的工作方式每
阅读更多...
Redis多种内存淘汰策略及配置技巧分享

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略（如noeviction、volatile-lru等）及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制？二、Redis 内存淘汰策略1. pythonnoe
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2