Java 栈和队列的相互转换详解

目录
  • 用栈实现队列—力扣232题
  • 用队列实现栈—力扣225题 
    • 1. 双队列实现栈
    • 2.一个队列实现栈

栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除。因此,栈和队列可以相互转换。

用栈实现队列—力扣232题

题目要求:仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作

使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助 

上图可以看到,新元素进栈时,要确保该栈为空。进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中。这样操作之后,栈中元素存放的顺序就和队列的一样啦

代码实现:


//双栈模拟队列
public class MyQueue{
    //实际存储元素的栈
    private Stack<Integer> s1 = new Stack<>();
    //辅助栈
    private Stack<Integer> s2 = new Stack<>();

    public MyQueue() {

    }

    //将元素 x 推到队列的末尾
    public void push(int x) {
        if (s1.empty()){//栈为空,直接放入x
            s1.push(x);
        }else {
            //此时不为空
            //先把s1所有元素弹出放入s2
            while (!s1.empty()){
                s2.push(s1.pop());//s2放入的值就是s2弹出的值
                //以下两句和上一句相同
//                int val = s1.pop();
//                s2.push(val);
            }
            //将新元素直接放入s1,此时新元素就处在s1的栈顶
            s1.push(x);
            //再次将s2的所有值依次弹出放入s1
            while (!s2.empty()){
                s1.push(s2.pop());
            }
        }

    }

    //从队列的开头移除并返回元素
    public int pop() {
       return s1.pop();
    }

    //返回队列开头的元素
    public int peek() {
        return s1.peek();
    }

    //判断队列是否为空
    public boolean empty() {
        return s1.empty();
    }
}

用队列实现栈—力扣225题 

题目要求:仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作

1. 双队列实现栈

使用双队列实现栈, q1是存储元素的队列,保证q2添加元素之后永远为空队列(新元素直接入q2),保证新元素处在队首。这样的话,新元素入队之后,另外一个队列的元素依次出队然后入队,这样就实现了一个栈。

代码实现:

public class MyStack {
    //q1是存储元素的队列
    private Queue<Integer> q1 = new LinkedList<>();
    //q2是辅助队列
    //添加元素后保证q2永远为空
    private Queue<Integer> q2 = new LinkedList<>();
    public MyStack () {

    }

    //将元素 x 压入栈顶
    public void push(int x) {
        //新入队元素直接入q2,成为q2队首
        q2.offer(x);
        //将q1中的所有元素依次出队,入q2
        while (!q1.isEmpty()){
            q2.offer(q1.poll());
        }

        //q1为空,q2为存储元素的队列,互换引用指向
        //互换之后,q1任然是存储元素的队列,q2为空
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    // 移除并返回栈顶元素
    public int pop() {
        return q1.poll();
    }

    //返回栈顶元素
    public int top() {
        return q1.peek();
    }

    //判断栈是否为空
    public boolean empty() {
        return q1.isEmpty();
    }
}
 

2.一个队列实现栈

先将元素入队,再将之前的元素依次出队再入队即可!也就是说,保证新元素在队首

代码实现:

public class MyStack {
    private Queue<Integer> queue = new LinkedList<>();
    public MyStack() {
    }

    public void push(int x) {
        //记录之前元素的个数
        int size = queue.size();
        //将新元素入队
        queue.offer(x);
        //将之前的元素依次出队再入队,新元素就在队首位置
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }

    }

    public int pop() {
        return queue.poll();
    }

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

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

这几个例题实践目的是更加熟悉的掌握和了解栈和队列,实际应用中是不推荐的哦。

到此这篇关于Java 栈和队列的相互转换详解的文章就介绍到这了,更多相关Java 栈和队列 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • java 数据结构中栈和队列的实例详解

    java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl

  • java 数据结构之栈与队列

    java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • Java数据结构学习之栈和队列

    一.栈 1.1 概述 Java为什么要有集合类: 临时存储数据. 链表的本质: 对象间通过持有和引用关系互相关联起来. 线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列 1.1.1 线性表的概念 (1)线性表:n个数据元素的有序序列. ①首先,线性表中元素的个数是有限的. ②其次,线性表中元素是有序的. (2)那这个"序"指的是什么呢? ①除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • 如何使用两个栈实现队列Java

    这篇文章主要介绍了如何使用两个栈实现队列Java,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目 用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 题解 描述 栈的特性是先进后出,队列的特点是先进先出,当数字依次入栈1后,依次出栈1并且压入栈2后,然后再出栈的顺序与进入栈1的顺序是一致的. 因此,进入队列通过压入栈1实现,弹出队列通过弹出栈2的栈顶元素实现,在弹出元素时需要保证当前栈弹出元素的顺序和队列弹

  • Java深入了解数据结构之栈与队列的详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现 ①入栈 ②出栈 ③获取栈顶元素 ④判断栈是否为空 4,实现mystack 二,队列 1,概念 2,队列的实现 ①入队 ②出队 ③获取队首元素 3,实现myqueue 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的

  • Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • Java特性队列和栈的堵塞原理解析

    做消息通信,消息会不断从网络流中取得,而后台也有线程不断消费.本来我一直是使用一些线程安全标识或方法来控制,后来在网上找到一些java新特性,里面包含了可以用到的堆栈使用,而且是堵塞的,这样至少可以保证一些安全性. 对于堆: BlockingQueue 不接受 null 元素.试图 add.put 或 offer 一个 null 元素时,某些实现会抛出 NullPointerException.null 被用作指示 poll 操作失败的警戒值. BlockingQueue 可以是限定容量的.它在

  • Java 栈和队列的相互转换详解

    目录 用栈实现队列-力扣232题 用队列实现栈-力扣225题  1. 双队列实现栈 2.一个队列实现栈 栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除.因此,栈和队列可以相互转换. 用栈实现队列-力扣232题 题目要求:仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作 使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助  上图可以看到,新元素进栈时,要确保该栈为空.进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中.

  • java 中 阻塞队列BlockingQueue详解及实例

    java 中 阻塞队列BlockingQueue详解及实例 BlockingQueue很好的解决了多线程中数据的传输,首先BlockingQueue是一个接口,它大致有四个实现类,这是一个很特殊的队列,如果BlockQueue是空的,从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒.同样,如果BlockingQueue是满的,任何试图往里存东西的操作也会被阻断进入等待状态,直到BlockingQueue里有空间才会被唤醒继续操作.

  • Java Date与String的相互转换详解

    Java Date与String的相互转换详解 前言: 我们在注册网站的时候,往往需要填写个人信息,如姓名,年龄,出生日期等,在页面上的出生日期的值传递到后台的时候是一个字符串,而我们存入数据库的时候确需要一个日期类型,反过来,在页面上显示的时候,需要从数据库获取出生日期,此时该类型为日期类型,然后需要将该日期类型转为字符串显示在页面上,Java的API中为我们提供了日期与字符串相互转运的类DateForamt.DateForamt是一个抽象类,所以平时使用的是它的子类SimpleDateFor

  • Java基本数据类型之间的相互转换详解

    目录 1.自动类型转换 1.定义 2.数据类型按精度大小排序 3.使用细节 2.强制类型转换 1.定义 2.使用细节 3.基本数据类型与String类型的转换 1.基本数据类型转String类型 2.String类型转基本数据类型 今天主要学习的是Java基本数据类型之间的转换以及String类型与基本数据类型之间的转换 1.自动类型转换 1.定义 Java程序在进行赋值或运算时,自动将精度小的转换成精度大的. 2.数据类型按精度大小排序 char —> int —> long —> f

  • Java与Unix时间戳的相互转换详解

    Java将Unix时间戳转换成指定格式日期,供大家参考,具体内容如下 当从服务器获取数据的时候,有时候获取的数据中的时间在很多的情况下是时间戳类似于这样1473048265,当然,我们不可能将这些数据以时间戳的形式展示给用户,通常情况,是要对这个时间戳进行一系列的处理加工,使其变成我们想要并习惯浏览的那种格式,那么怎么处理这些时间戳格式的数据呢?每个语言和框架都有自己的方法和方式. 下面将以java的方法来实现,废话少说直接撸码-- 方法实现 /** * Java将Unix时间戳转换成指定格式日

  • java list,set,map,数组间的相互转换详解

    java list,set,map,数组间的相互转换详解 1.list转set Set set = new HashSet( new ArrayList()); 2.set转list List list = new ArrayList( new HashSet());  3.数组转为list List stooges = Arrays.asList( "Larry" , "Moe" , "Curly" ); 此时stooges中有有三个元素.注意

  • Java 异常的栈轨迹(Stack Trace)详解及实例代码

    Java 异常的栈轨迹(Stack Trace)详解 捕获到异常时,往往需要进行一些处理.比较简单直接的方式就是打印异常栈轨迹Stack Trace.说起栈轨迹,可能很多人和我一样,第一反应就是printStackTrace()方法.其实除了这个方法,还有一些别的内容也是和栈轨迹有关的. 1.printStackTrace() 首先需要明确,这个方法并不是来自于Exception类.Exception类本身除了定义了几个构造器之外,所有的方法都是从其父类继承过来的.而和异常相关的方法都是从jav

  • Java并发编程之阻塞队列深入详解

    目录 1. 什么是阻塞队列 2. 阻塞队列的代码使用 3. 生产者消费者模型 (1)应用一:解耦合 (2)应用二:削峰填谷 (3)相关代码 4.阻塞队列和生产者消费者模型功能的实现 1. 什么是阻塞队列 阻塞队列是一种特殊的队列,和数据结构中普通的队列一样,也遵守先进先出的原则同时,阻塞队列是一种能保证线程安全的数据结构,并且具有以下两种特性:当队列满的时候,继续向队列中插入元素就会让队列阻塞,直到有其他线程从队列中取走元素:当队列为空的时候,继续出队列也会让队列阻塞,直到有其他线程往队列中插入

随机推荐