目录
题目描述
解题思路
步骤一
步骤二
步骤三
小结
实现代码
注意事项
总结
首页 Java Java基础 如何用两个栈实现一个队列?

如何用两个栈实现一个队列?

Oct 26, 2020 pm 05:54 PM
java 队列

Java基础教程栏目介绍如何用两个栈实现一个队列。

如何用两个栈实现一个队列?

队列和栈是计算机中两个非常重要的数据结构,经过前面的学习(《队列》、《栈》)我们知道了它们各自的特点,队列是先进先出(FIFO)的,而栈是先进后出(FILO)的,那如何用栈来实现队列呢?这可是一道经典的面试题,所以本文我们就来实现一下。

在正式开始之前,我们先来回顾一下栈和队列的常用方法。

栈(Stack)的常用方法包含以下这些:

  • push():入栈方法,向栈顶添加元素;
  • pop():出栈方法,将栈顶的元素移除并返回元素;
  • peek():查询栈顶元素,并不会移除元素。

image.png

队列(Queue)的常用方法包含以下这些:

  • offer():入队方法,向队尾添加元素;
  • poll():出队方法,从队头移除并返回元素;
  • peek():查询队头元素,并不会移除元素。

image.png有了这些前置知识,接下来我们来看今天的题目。

题目描述

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能,若队列中没有元素,deleteHead 操作返回 -1。

示例 1:

输入:

["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

输出:[null,null,3,-1]

示例 2:

输入:

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[],[]]

输出:[null,-1,null,null,5,2]

提示:

1 <= values <= 10000

最多会对 appendTail、deleteHead 进行 10000 次调用

leetcode:leetcode-cn.com/problems/yo…

解题思路

这道题目的意思其实很好理解,就是要将先进后出的栈改为先进先出的队列,其实问题中也给出了一些提示,“用两个栈来实现一个队列”。这道题实现的核心思想就是「负负得正」,我们先用一个栈来存入元素(这时最先进入的元素在栈底),然后再将第一个栈中的元素移动到新栈中,此时最先进入的元素就在栈顶了,然后在用第二个栈出栈时,整个执行的顺序就变成了先进先出。

接下来,我们用图解的方式来实现一下整个流程。

步骤一

先将元素入栈到第一个栈中,如下图所示:image.png

步骤二

将第一个栈中的元素都移动到第二个栈中,如下图所示:image.png

步骤三

所有元素从第二个栈中出栈,如下图所示:image.png

小结

从上述图片可以看出,元素添加顺序是 1、2、3,最终经过两个栈之后的出栈顺序也是 1、2、3,这样我们就通过两个栈实现了队列(先进先出)。image.png

实现代码

接下来我们就用代码来实现一下以上思路:

class CQueue {
    Stack inputStack; // 入栈的容器(添加时操作)
    Stack outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码

我们在 LeetCode 中提交以上测试代码,执行结果如下:image.png

注意事项

在整个实现过程中有两个小细节需要特别注意一下:

  1. 第 1 个栈只负责入栈(暂存数据),第 2 个栈只负责出栈(最终的队列执行顺序);
  2. 每次栈 2 出栈时都要把所有的元素都出完之后,才能从栈 1 中追加(添加)新数据,当栈 2 的数据没有全部出栈完成时,不能将栈 1 的元素入栈到栈 2,这样会导致元素的执行顺序混乱。

总结

本文我们通过两个先进后出的栈,通过“负负得正”的思路实现了队列先进先出的特性,但需要特别注意的是当第 2 个栈也就是出栈容器,在非空(栈)时不能将第 1 个栈中的元素添加到第 2 个栈中,以免造成程序执行顺序混乱。

相关免费学习推荐:java基础教程

以上是如何用两个栈实现一个队列?的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根指南。下面我们分别通过例子和代码实现来讨论平方根在Java中的工作原理。

Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义,如何在 Java 中检查完美数?,示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里,我们通过示例讨论 Java 中的函数,并通过示例讨论两个不同的生成器。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义,如何在Java中检查史密斯号?带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中,我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回? 突破或从Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles