Java面试之用两个栈实现队列

这篇具有很好参考价值的文章主要介绍了Java面试之用两个栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


题目

用两个栈实现一个队列,实现在队列尾部插入节点和在队列头部删除节点的功能。


一、什么是队列和栈?

1.1队列

队列是一种特殊的线性表,它只允许在表的前端(队头)进行删除操作,在表的后端(队尾)进行插入。
故队列又称为先进先出(FIFO—first in first out)线性表。
Java面试之用两个栈实现队列,Java面试,java,面试,开发语言

1.2栈

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。
它按照后进先出(LIFO—last in first out)的原则存储数据,先进入的数据被压入(push)栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出(pop)数据(最后一个数据被第一个读出来)。
栈在计算机领域被广泛应用,比如:操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。
Java面试之用两个栈实现队列,Java面试,java,面试,开发语言

二、具体实现

2.1 思路分析

Java面试之用两个栈实现队列,Java面试,java,面试,开发语言

(a)在stack1中依次插入a、b、c,stack2为空
(b)现在从队列中删除一个元素,按照队列先入先出的规则,最先删除的应该是a。
但是a在栈底不能直接删除,这时候可以借助stack2,将元素逐个弹出(pop)并压入(push)stack2,则元素在stack2中的顺序{从c、b、a}正好和stack1中相反,此时就可以弹出stack2的栈顶a,如图b。
(c)如果想继续删除队列头部,按照最开始的顺序,b比c早进入队列,此时应该删除b。b正好在stack2的栈顶,只需要弹出stack2的栈顶即可。如图c。

这样就可以总结出一个删除的步骤:
1、当stack2不为空时,stack2就是栈顶就是最先进入队列的元素,可以弹出。
2、当stack2为空时,将stack1中的元素逐个弹入stack2中,由于先进入队列的元素被压到stack1栈底,经过弹出和压入操作后位处stack2栈顶,就可以直接弹出。

(d)接下来插入一个元素d,把它压入stack1。
(e)现在考虑删除一个元素,此时stack2不为空,直接弹出c,而c确实比d先进入队列,因此也是正确的。

2.2代码实现

代码如下:文章来源地址https://www.toymoban.com/news/detail-681484.html

import java.util.*;
import java.util.Stack;
public class CQueue{
	Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node){
    	stack1.push(node);
    }
    public int pop(){
    	if(stack2.isEmpty()){
	    	//将第一个栈中内容弹出放入第二个栈中
	    	while(!stack1.isEmpty()){
	    		stack2.push(stack1.pop());
	    	}
    	}
    	if(stack2.isEmpty()){
    		Throw new Exception(queue is empty!);
    	}
    	int head = stack2.pop();
    	return head;
    
    }
	
}

到了这里,关于Java面试之用两个栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作,在另一端进行删除数据操作得特殊线性表,队列是 先进先出 ,入队:进行插入操作得一端称为 队尾(rear) ,出队:进行删除操作的一端称为 队头(front) 。队列Queue是个接口, 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(48)
  • java八股文面试[多线程]——两个线程交替打印1-100之间的数字

    一份代码,两个线程,使用synchronize实现: 重写run()方法,将输出1到100之间整数的代码写到同步方法里。 线程1进入到同步方法,输出一个整数后,阻塞并释放锁。 线程2进入到同步方法,唤醒线程1,输出整数后,阻塞并释放锁。 线程1和线程2重复第3步,直到输出所有的整数

    2024年02月11日
    浏览(45)
  • 两个数组的交集-C语言/Java

    描述         给定两个数组  nums1  和  nums2  ,返回  它们的交集  。输出结果中的每个元素一定是  唯一  的。我们可以  不考虑输出结果的顺序。 (1 = nums1.length, nums2.length = 1000,0 = nums1[i], nums2[i] = 1000) 示例1 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例2 输入:

    2024年02月11日
    浏览(40)
  • 32个Java面试必考点-09(上)消息队列Kafka架构与原理

    本课时主要讲解消息队列与数据库相关的知识,重点讲解三部分知识点: 1.Kafka 的架构与消息交互流程; 2.数据库事务的 4 大特性和分类; 3.MySQL 相关的内容,比如索引、MySQL 调优等。 消息队列与数据库知识点 先来看看相关知识点汇总,如下图。首先为了防止歧义进行说明

    2024年02月20日
    浏览(41)
  • [开发|java] java 比较两个对象的指定属性的值是否相等

    Java中比较两个对象的指定属性的值是否相等,可以使用Apache Commons Lang库中的EqualsBuilder类。EqualsBuilder提供了一种便捷的方法来比较两个对象的属性值是否相等,具体步骤如下: 通过构造器创建一个EqualsBuilder对象。 调用EqualsBuilder对象的append方法,传入需要比较的两个对象以

    2024年02月16日
    浏览(58)
  • Java开发 - 消息队列之RabbitMQ初体验

    目录 前言 RabbitMQ 什么是RabbitMQ RabbitMQ特点 安装启动 RabbitMQ和Kafka的消息收发区别 RabbitMQ使用案例 添加依赖 添加配置 创建RabbitMQ配置类 RabbitMQ消息的发送 RabbitMQ消息的接收 测试 结语 前一篇,我们学习了Kafka的基本使用,这一篇,我们来学习RabbitMQ。他们作为消息队列本身都具

    2024年02月03日
    浏览(44)
  • 【数据结构经典题目】—两个队列实现栈与两个栈实现队列

    ​                                           食用指南:本文在有C基础的情况下食用更佳                                            🔥 这就不得不推荐此专栏了: C语言                                         🍀

    2024年02月13日
    浏览(46)
  • JAVA 两个通用安全模块的设计与开发(论文+源码)_Nueve

    摘  要 本文详细介绍了基于口令的身份认证与文件安全传输两个通用安全模块的设计原理和实现过程,分析了当前口令保存的安全性,提出了运用MD5算法等对口令进行处理,并将处理结果保存在数据库中的方法。同时为了进一步增强认证系统的灵活度,设计了用户注册时的口

    2024年02月04日
    浏览(38)
  • Java 实现两个日期之间相差多少天

    Java 实现两个日期之间相差多少天 运行结果:

    2024年02月15日
    浏览(49)
  • Java 数据结构篇-用链表、数组实现队列(数组实现:循环队列)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 队列的说明         1.1 队列的几种常用操作         2.0 使用链表实现队列说明         2.1 链表实现队列         2.2 链表实现队列 - 入栈操作         2.3 链表实现队

    2024年02月05日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包