Java栈和基础队列的实现详解
作者:Word码鸭 发布时间:2023-07-02 05:36:59
栈和队列:都是线性表,都是基于List基础上的实现
线性表:数组,链表,字符串,栈,队列
元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素
栈(stack)
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
栈支持的三个核心操作:
入栈push
出栈pop
返回栈顶元素peek
栈的常见实际应用:
无处不在的撤销操作undo,一般任意的编辑器都使用 ctrl + z 操作,其实本质就是每次操作一次 ctrl + z 就是一次栈的pop
浏览器的前进后退,浏览器维护了一个栈结构A->B->C,此时页面停留在C,想要回到页面B,点击后退键头就相当于将C出栈,此时的栈顶就是B
在开发程序中的“调用栈”操作系统栈底层就是栈的实现
栈的实现
栈是一种线性表,所以实现它即可使用数组,也可以使用链表
基于数组实现的栈—顺序栈(栈顶实际就是数组尾部,在数组尾部添加和删除)
基于链表实现的栈—链式栈(链表的头插和尾插)
在数组尾部进行删除和插入的时间复杂度为O(1),所以用数组实现栈是我们的首选
实现代码:
//基于数组实现的栈
public class MyStack<E> {
private int size;//数组长度
//实际存储数据的动态数组
private List<E> data = new ArrayList<>();
//入栈,默认尾插
public void push(E val){
data.add(val);
size ++;
}
//弹出栈顶元素,返回栈顶的值
public E pop(){
if(isEmpty()){
//栈为空
throw new NoSuchElementException("stack is empty!cannot pop!");
}
//删元素
E val = data.remove(size-1);
size--;
return val;
//上面三句等同于return data.remove(size-1);
}
//返回栈顶元素,但不出栈
public E peek(){
if(isEmpty()){
throw new NoSuchElementException("stack is empty!cannot peek");
}
return data.get(size-1);
}
// 判断当前栈是否为空
public boolean isEmpty() {
return size == 0;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data.get(i));
if (i != size - 1) {
// 此时还没到栈顶,还没到数组末尾
sb.append(", ");
}
}
sb.append("] top");
return sb.toString();
}
}
//--------------------------
//测试类·
public class StackTest {
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(3);
myStack.push(5);
System.out.println(myStack);
System.out.println(myStack.pop());//删除栈顶
System.out.println(myStack.peek());//输出栈顶,此时栈顶为3
System.out.println(myStack.isEmpty());
}
}
//输出结果:
[1, 3, 5] top
5
3
false
队列
只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列遵循先进先出FIFO(First In First Out)的原则 :进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头
其实队列的定义很简单,就相当于我们现实生活的排队购物,先排队的人先结账,也就先离开
队列的子类比栈要复杂一些,它有:
基础队列—FIFO
基于优先级的队列—按照优先级大小出队
循环队列—基于数组实现的
双端队列
无论是哪种队列,都必须支持三个核心操作:
入队—offer
出队—poll
返回队首元素—peek
基础队列的实现
基于数组实现的队列—顺序队列
基于链表实现的队列—链式队列
由于队列是从队尾插入,队首出队,而在数组头部删除的时间复杂度为O(n),此时我们用链表会更好一些。而且无论实现哪种队列都需要覆写三个基本操作,因此我们将队列设计为接口
实现代码:
public interface Queue<E> {
// 入队
void offer(E val);
// 出队
E poll();
// 返回队首元素
E peek();
// 判断队列是否为空
boolean isEmpty();
}
//基于链表实现的基础队列
public class MyQueue<E> implements Queue<E> {
// 链表的每个节点
// ------------------------------
//内部类
private class Node {
E val;
Node next;
public Node(E val) {
this.val = val;
}
}
// ------------------------------
// 当前队列中的元素个数
private int size;
// 队首
private Node head;
// 队尾
private Node tail;
@Override
public void offer(E val) {
Node node = new Node(val);
if (head == null) {
// 此时链表为空
head = tail = node;
}else {
tail.next = node;
tail = node;
}
size ++;
}
@Override
public E poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!cannot poll!");
}
E val = head.val;
Node node = head;
head = head.next;
// 将原来头节点脱钩
node.next = null;
size --;
return val;
}
@Override
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty!cannot peek!");
}
return head.val;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("front [");
// 链表的遍历
for (Node x = head;x != null;x = x.next) {
sb.append(x.val);
if (x.next != null) {
// 还没走到链表尾部
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}
//测试类
public class QueueTest {
public static void main(String[] args) {
Queue<Integer> queue = new MyQueue<>();
queue.offer(1);
queue.offer(3);
queue.offer(5);
System.out.println(queue);
}
}
作为初学者,我们不能小瞧任何简单的数据结构与算法,基础的数据结构往往作为高阶数据结构的一部分来应用,万丈高楼平地起,平时要多加练习,我们一起加油!
来源:https://blog.csdn.net/m0_58672924/article/details/122647558
猜你喜欢
- 估计学过Unix开发但是没有细致学习Java的同学们会疑惑了,操作系统里面是没有所谓的守护线程的概念,只有守护进程一说,但是Java语言机制
- 一、消息队列概述消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架
- 右击有main方法的类===> Run as===> Run Configurations ===>双击java
- 1. 什么是对象池对象池,顾名思义就是一定数量的已经创建好的对象(Object)的集合。当需要创建对象时,先在池子中获取,如果池子中没有符合
- 本文实例讲述了java中Object类用法。分享给大家供大家参考。具体如下:1、Object类是所有java类的基类如果在类的声明中未使用e
- 代码背景一个班级,有两类学生,A类:不学习,玩,但是玩的东西不一样,有的是做游戏,有的是看电视B类:放哨的学生,专门看老师的动向,如果老师进
- 本文实例汇总了Java的System.getProperty()方法获取信息的用法。分享给大家供大家参考。具体如下:System.out.p
- @ApiImplicitParam作用在方法上,表示单独的请求参数参数name:参数名。value:参数的具体意义,作用。required:
- 话不多说,下面来直接看示例代码具体代码:DayOfWeek4Birthday.javapackage com.gua;import java
- 最近在做上传文件的服务,简单看了网上的教程。结合实践共享出代码。由于网上的大多数没有服务端的代码,这可不行呀,没服务端怎么调试呢。Ok,先上
- IDEA SpringBoot项目配置热更新的步骤1.在pom.xml中添加依赖:<dependency><groupId
- 本文实例为大家分享了Java实现猜数字游戏的具体代码,供大家参考,具体内容如下完成猜数字游戏需要实现以下几点:获得一个随机数作为“答案数”;
- 你是否受够了每次修改静态文件都要重启服务器?有时候在一些公司前后端的职责没有那么的明确,往往后台人员也要去写一些页面,像jsp页面,或者其他
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 文件分割与合并是一个常见需求,比如:上传大文件时,可以先分割成小块,传到服务器后,再进行合并。很多高大上的分布式文件系统(比如:google
- 一、Monkey 是什么?Monkey 就是SDK中附带的一个工具。二、Monkey 测试的目的?:该工具用于进行压力测试。 然后开发人员结
- 说到多渠道,这里不得不提一下友盟统计,友盟统计是大家日常开发中常用的渠道统计工具,而我们的打包方法就是基于友盟统计实施的。按照友盟官方文档说
- 一.背景本文主要介绍Java 8中时间的操作方法java.util.Date是用于表示一个日期和时间的对象(注意与java.sql.Date
- 一、项目概述之前有不少粉丝私信我说,能不能用Android原生的语言开发一款在手机上运行的游戏呢?说实话,使用java语言直接开发游戏这个需
- 本文实例为大家分享了java实现鲜花销售系统的具体代码,供大家参考,具体内容如下一、练习目标1.体会数组的作用2.找到分层开发的感觉3.收获