数据结构——Java实现栈和队列

一、栈 Stack

1.特点

（1）栈是一种线性数据结构

（2）规定只能从栈顶添加元素，从栈顶取出元素

（3）是一种先进后出的数据结构（Last First Out）LIFO

2.具体实现

Java中可以直接调用方法来实现栈

如何自己写代码来实现栈呢？

先定义一个接口，方便后边进行调用

package com.algo.lesson.lesson02.stack;

public interface Stack_I<T> {
    //入栈
    void push(T ele);
    //出栈
    T pop();
    //查看栈顶元素
    T peek();
    //判断是否为空
    boolean isEmpty();
    //后去栈中元素
    int getSize();
}

接下来来实现栈的方法，调用接口，完善方法：

package com.algo.lesson.lesson02.stack;

import com.algo.lesson.lesson01.MyArr;

//以数组作为栈顶的底层数据结构
public class ArrStack<T> implements Stack_I<T> {

    private MyArr<T>data;

    int size;

    public ArrStack() {
        this.data=new MyArr<>(100);
        this.size=0;
    }

    @Override
    public void push(T ele) {
        //在数组尾部添加元素
        this.data.add(ele);
        this.size++;
    }

    @Override
    public T pop() {
        if(isEmpty()){
            return null;
        }
        this.size--;
        return this.data.removeBFromLast();
    }

    @Override
    public T peek() {
        return this.data.getLastValue();
    }

    @Override
    public boolean isEmpty() {
        return this.size==0;
    }

    @Override
    public int getSize() {
        return this.size;
    }
}

以上就是方法的代码，接下来，写个main函数来调用，检查方法是否正确

package com.algo.lesson.lesson02.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class StackTest<T> {
    public void test(Stack_I<T>stack, List<T> list){
        //开始时间
        long startTime=System.nanoTime();

        for(int i=0;i<list.size();i++){
            stack.push(list.get(i));
        }
        System.out.println(stack.getSize());
        while(!stack.isEmpty()){
            T ele=stack.pop();
            System.out.println(ele+"  ");
        }

        //结束时间
        long endTime=System.nanoTime();
        System.out.println("总耗时："+(endTime-startTime)/100000000.0);
    }

    public static void main(String[] args) {
        StackTest<Integer>stackTest=new StackTest<>();
        Stack_I<Integer>stack=new ArrStack<>();
        List<Integer>list=new ArrayList<>();
        Random random=new Random();
        for(int i=0;i<100;i++){
            int val= random.nextInt(1000);
            list.add(val);
        }
        stackTest.test(stack,list);
    }
}

注：其中long startTime=System.nanoTime();方法是获取一个时间（单位毫秒）

在程序运行前和运行后个添加一个，最后将两个时间相减，得到程序运行时间。

3.时间复杂度分析

二、队列

1.特点

（1）队列也是一种线性数据结构

（2）只能从一端添加元素，另一端取出元素

（3）是一种先进先出的数据结构（FIFO——fist in fist out ）

2.具体实现

Java中也可以直接调用队列的方法：

自己的实现：

接口：

package com.algo.lesson.lesson02.queue;

public interface Queue_I<T> {
    void offer(T ele);//入队
    T poll();//出队
    T peek();//查找队首元素
    int getSize();
    boolean isEmpty();


}

方法代码：

package com.algo.lesson.lesson02.queue;

import com.algo.lesson.lesson01.MyArr;

public class ArrQueue<T>implements Queue_I<T> {

    private MyArr<T>data;

/*
    private int size;//队列中元素的个数
*/

    public ArrQueue(){
        this.data=new MyArr<>(50);
    }

    @Override
    public void offer(T ele) {
        this.data.add(ele);
    }

    @Override
    public T poll() {
        if(isEmpty()){
            return null;
        }
        return this.data.removeByIndex(0);
    }

    @Override
    public T peek() {
        if(isEmpty()){
            return null;
        }
        return this.data.getValueByIndex(0);
    }

    @Override
    public int getSize() {
        return this.data.getSize();
    }

    @Override
    public boolean isEmpty() {
        return this.data.isEmpty();
    }
}

3.出现的问题

入队列时间复杂度为O(n)，因为在出队时，元素要前移，会出现假溢出的情况。

所以就出现了循环队列来解决这个问题

循环队列：

front记录队首，tail记录队尾，队尾达到容积时，返回到队头，将空位置补上，可以继续存储数据。

package com.algo.lesson.lesson02.queue;

import java.util.Random;

/*
基于Java中的数组进行二次封装,制作一个可变数组
 */
//泛型:就是类型作为参数
public class LoopArr<T> {
    private T[] data;//保存数据

    private int size;//数组中实际存放元素的个数

    private int front;//队首

    private int tail;//队尾

    int capacity;//容积

    //构造函数
    public LoopArr(int capacity) {
        if (capacity <= 0) {
            this.capacity = 11;
        } else {
            this.capacity = capacity + 1;
        }
        this.size = 0;
        this.front = this.tail = 0;
        this.data = (T[]) (new Object[this.capacity]);
    }

    //获取数组中实际存放元素的个数
    public int getSize() {
        return this.size;
    }

    //获取数组的容积
    public int getCapacity() {
        return this.capacity;
    }

    //判断数组是否为空
    public boolean isEmpty() {
        return this.front == this.tail;
    }

    //向数组中添加元素(尾部)
    public void add(T item) {
        //判断数组是否满
        if ((this.tail + 1) % this.capacity == this.front) {
            //扩容
            resize((this.capacity-1)*2+1);
        }
        //从index位置开始元素需要进行后移
        this.data[this.tail] = item;
        this.tail = (this.tail + 1) % this.capacity;
        //更新this.size
        this.size++;
    }

    private void resize(int newCapacity) {
        System.out.println("resize:" + newCapacity);
        T[] newData = (T[]) (new Object[newCapacity]);
        //将原数组驾到新数组里

        for (int i = 0; i < this.size; i++) {
            newData[i] = this.data[(this.front+i)%this.capacity];
        }
        //改变容器
        this.data = newData;
        this.capacity = newCapacity;
        //将this.front置零
        this.front=0;
        this.tail=this.size;
    }

    //获取指定位置的值
    public T getValueByIndex() {
        if(isEmpty()){
            return null;
        }
        return this.data[this.front];
    }

    //移除队首元素
    public T remove() {
        if (isEmpty()) {
            return null;
        }
        //删除操作的核心
        /*
        1.找到删除的位置
        2.删除位置之后的元素要前移 arr[j-1]=arr[j]
         */
        T delValue = this.data[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        //判断是否缩容
        if (this.size < this.capacity / 4 && this.capacity / 2 > 0) {
            resize((this.capacity-1) / 2 +1);
        }
        return delValue;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < this.size; i++) {
            sb.append(this.data[i]);
            if (i != this.size - 1) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
package com.algo.lesson.lesson02.queue;

public class LoopQueue<T> implements Queue_I<T>{

    private LoopArr<T>data;//容器

    public LoopQueue(){
        this.data=new LoopArr<>(100);
    }




    @Override
    public void offer(T ele) {
        this.data.add(ele);
    }

    @Override
    public T poll() {
        return this.data.remove();
    }

    @Override
    public T peek() {
        return this.data.getValueByIndex();
    }

    @Override
    public int getSize() {
        return this.data.getSize();
    }

    @Override
    public boolean isEmpty() {
        return this.data.isEmpty();
    }
}

4.循环队列的复杂度分析

三、栈和队列的互相实现

既然我们了解了栈和队列，知道了这两种数据结构十分相似，也就可以大胆假设以下，可不可以相互实现，不是用上面所写的以数组为底层，而是相互为底层存储。

1.用栈来实现队列

import java.util.Stack;

class MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        while (!B.isEmpty()) {
            A.push(B.pop());
        }
        A.push(x);
        while (!A.isEmpty()) {
            B.push(A.pop());
        }
    }

    public int pop() {
        return B.pop();
    }

    public int peek() {
        return B.peek();
    }

    public boolean empty() {
        return B.isEmpty();
    }
}

2.用队列实现栈

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.add(x);
        while (!queue1.isEmpty()) {
            queue2.add(queue1.remove());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.remove();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

这就是这两种数据结构相互实现的代码

在LeetCode中也有相对应的题目：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（栈实现队列）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（队列实现栈）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/335328.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python 并发编程

Python 并发编程

文章目录 Python 并发编程1. 基本概念1.1 CPU 密集型计算1.2 IO 密集型计算1.3 多线程&#xff0c;多进程&#xff0c;多协程的对比1.4 怎么根据任务选择对应的技术&#xff1f; 2. 全局解释器锁 GIL2.1 Python 速度慢的两大原因2.2 GIL 是什么?2.3 为什么有 GIL ?2.4 怎样规…
阅读更多...
蓝桥杯备战 每日一题 （2）

蓝桥杯备战 每日一题 （2）

今天的题目是回忆迷宫 这个题目我们来熟悉一下 弗洛伊德算法 的代码模板 弗洛伊德算法用来处理最短路径问题 弗洛伊德算法&#xff08;Floyd’s algorithm&#xff09;用于解决图中所有节点对之间的最短路径问题。算法的基本思路是通过逐步迭代更新节点对之间的最短路径长度&a…
阅读更多...
力扣日记1.19-【二叉树篇】538. 把二叉搜索树转换为累加树

力扣日记1.19-【二叉树篇】538. 把二叉搜索树转换为累加树

力扣日记&#xff1a;【二叉树篇】538. 把二叉搜索树转换为累加树 日期&#xff1a;2023.1.19 参考&#xff1a;代码随想录、力扣 ps&#xff1a;因为准备组会汇报又搁置了好久&#xff08;其实就是懒逃避T^T)&#xff0c;但这是最后一道二叉树啦啊啊啊&#xff01;&#xff01…
阅读更多...
串口通信自用

串口通信自用

定义 串口&#xff08;Serial Port&#xff09;是一种用于数据通信的接口标准&#xff0c;它通过物理线路将数据以逐位的方式传输。串口通信可以在计算机和外部设备之间进行数据交换&#xff0c;常用于连接调制解调器、打印机、传感器、嵌入式系统等设备。常用的通信协议协议有…
阅读更多...
day02：列表、表格、表单

day02：列表、表格、表单

01-列表 作用&#xff1a;布局内容排列整齐的区域。 列表分类&#xff1a;无序列表、有序列表、定义列表。 无序列表 作用&#xff1a;布局排列整齐的不需要规定顺序的区域。 标签&#xff1a;ul 嵌套 li&#xff0c;ul 是无序列表&#xff0c;li 是列表条目。 <ul>…
阅读更多...
【信号与系统】【北京航空航天大学】实验四、幅频、相频响应和傅里叶变换

【信号与系统】【北京航空航天大学】实验四、幅频、相频响应和傅里叶变换

一、实验目的 1、 掌握利用MATLAB计算系统幅频、相频响应的方法&#xff1b; 2、 掌握使用MATLAB进行傅里叶变换的方法&#xff1b; 3、 掌握使用MATLAB验证傅里叶变换的性质的方法。 二、实验内容 1、 MATLAB代码&#xff1a; >> clear all; >> a [1 3 2]; …
阅读更多...
rabbitmq的介绍、使用、案例

rabbitmq的介绍、使用、案例

1.介绍 rabbitmq简单来说就是个消息中间件&#xff0c;可以让不同的应用程序之间进行异步的通信&#xff0c;通过消息传递来实现解耦和分布式处理。 消息队列&#xff1a;允许将消息发到队列&#xff0c;然后进行取出、处理等操作&#xff0c;使得生产者和消费者之间能够解耦&…
阅读更多...
C++初阶--自我实现vector

C++初阶--自我实现vector

实现模板 #include<assert.h> #include<string.h> #include<iostream> #include<list> using namespace std; namespace fnc {template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//构造函数vector(){…
阅读更多...
五、模 板

五、模 板

1 泛型编程 以往我们想实现一个通用的交换函数&#xff0c;可能是通过下面的方式来实现的&#xff1a; void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left ri…
阅读更多...
递归、搜索与回溯算法（专题一：递归）

递归、搜索与回溯算法（专题一：递归）

往期文章&#xff08;希望小伙伴们在看这篇文章之前&#xff0c;看一下往期文章&#xff09; &#xff08;1&#xff09;递归、搜索与回溯算法&#xff08;专题零&#xff1a;解释回溯算法中涉及到的名词&#xff09;【回溯算法入门必看】-CSDN博客 接下来我会用几道题&#…
阅读更多...
【深度学习每日小知识】Artificial Intelligence 人工智能

【深度学习每日小知识】Artificial Intelligence 人工智能

人工智能 (AI) 是一个快速发展的领域&#xff0c;有潜力改变我们的生活和工作方式。人工智能已经为从自动驾驶汽车到个性化医疗等各个行业做出了重大贡献。然而&#xff0c;与任何新技术一样&#xff0c;人工智能也存在许多问题和担忧。在这里&#xff0c;我们将探讨有关人工智…
阅读更多...
【Qt开发】初识Qt

【Qt开发】初识Qt

文章目录 1. Qt的背景1.1 Qt是什么1.2 Qt的发展史1.3 Qt支持的平台 2. Qt开发环境的搭建2.1 Qt SDK下载2.2 Qt SDK的安装 3. 一个简单的Qt模板程序的创建4. Qt模板程序的代码讲解4.1 main.cpp4.2 widget.h4.3 widget.cpp4.4 widget.ui4.5 test_1_18.pro4.6 一些中间文件 5. Qt在…
阅读更多...
算法训练 day24 | 77. 组合

算法训练 day24 | 77. 组合

77. 组合 题目链接:组合 视频讲解:带你学透回溯算法-组合问题 回溯其实和递归是密不可分的&#xff0c;解决回溯问题标准解法也是根据三部曲来进行的。 1、递归函数的返回值和参数 对于本题&#xff0c;我们需要用一个数组保存单个满足条件的组合&#xff0c;还需要另一个结果数…
阅读更多...
分布式搜索引擎ElasticSearch——深入elasticSearch

分布式搜索引擎ElasticSearch——深入elasticSearch

分布式搜索引擎ElasticSearch——深入elasticSearch 文章目录 分布式搜索引擎ElasticSearch——深入elasticSearch数据聚合聚合的分类DSL实现Bucket聚合DSL实现Metric聚合RestAPI实现聚合 自动补全DSL实现自动补全查询修改酒店索引库数据结构RestAPI实现自动补全查询实现酒店搜…
阅读更多...
elasticsearch6.6.0设置访问密码

elasticsearch6.6.0设置访问密码

elasticsearch6.6.0设置访问密码 第一步 x-pack-core-6.6.0.jar第二步 elasticsearch.yml第三步 设置密码 第一步 x-pack-core-6.6.0.jar 首先破解 x-pack-core-6.6.0.jar 破解的方式大家可以参考 https://codeantenna.com/a/YDks83ZHjd 中<5.破解x-pack> 这部分 , 也可…
阅读更多...
Labview局部变量、全局变量、引用、属性节点、调用节点用法理解及精讲

Labview局部变量、全局变量、引用、属性节点、调用节点用法理解及精讲

写本章前想起题主初学Labview时面对一个位移台程序&#xff0c;傻傻搞不清局部变量和属性节点值有什么区别&#xff0c;概念很模糊。所以更新这篇文章让大家更具象和深刻的去理解这几个概念&#xff0c;看完记得点赞加关注喔~ 本文程序源代码附在后面&#xff0c;大家可以自行下…
阅读更多...
原型设计 Axure RP 9

原型设计 Axure RP 9

Axure RP 9是一款专业的原型设计和协作工具&#xff0c;让用户快速创建高保真度的交互原型&#xff0c;模拟真实的用户界面和交互体验。该软件界面布局合理&#xff0c;易于使用&#xff0c;提供丰富的交互功能和效果&#xff0c;如动态面板、变量、条件逻辑、动画等。同时支持…
阅读更多...
C#，字符串匹配（模式搜索）有限自动机（Finite Automata）算法的源代码

C#，字符串匹配（模式搜索）有限自动机（Finite Automata）算法的源代码

一、有限状态自动机 图中两个圆圈&#xff0c;也叫节点&#xff0c;用于表示状态&#xff0c;从图中可以看成&#xff0c;它有两个状态&#xff0c;分别叫0和1。从每个节点出发&#xff0c;都会有若干条边。当处于某个状态时&#xff0c;如果输入的字符跟该节点出发的某条边的内…
阅读更多...
如何在Java中加载两个类全限定名相同的类？

如何在Java中加载两个类全限定名相同的类？

我们知道在Java中类全限定名由两部分组成&#xff0c;包名和类名&#xff0c;当然网上也有说法是由三部分组成&#xff0c;包名、子包名以及类名&#xff0c;这里我把包相关的统称为包名。 比如说在某个Java项目中com.knight包下有一个类A&#xff0c;那么这个类A的类全限定名…
阅读更多...
解决一个mysql的更新属性长度问题

解决一个mysql的更新属性长度问题

需求背景&#xff1a; 线上有一个 platform属性&#xff0c;原有长度为 varchar(10)&#xff0c;但是突然需要填入一个11位长度的值&#xff1b;而偏偏这个属性在线上100张表中有50张都存在&#xff0c;并且名字各式各样&#xff0c;庆幸都包含 platform&#xff1b;例如 platf…
阅读更多...
最新文章

Copyright @ 2022~2023