416,剑指 Offer-用两个栈实现队列

2021年11月25日 阅读数:2
这篇文章主要向大家介绍416,剑指 Offer-用两个栈实现队列,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

416,剑指 Offer-用两个栈实现队列_队列

Everyone's the hero in their own story.数组

每一个人都是本身故事里的英雄。app

问题描述ide

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

 

示例 1:3d

输入:blog

["CQueue","appendTail","deleteHead","deleteHead"]队列

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

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

示例 2:二叉树

输入:

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

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

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

 

问题分析

作这题以前咱们首先要明白一点就是,栈是先进后出的,队列是先进先出的。咱们能够使用两个栈stackPop和stackPush,往队列中添加元素的时候直接把要添加的值压入到stackPush栈中。往队列中删除元素的时候若是stackPop中有元素咱们就直接删除,若是没有元素,咱们须要把stackPush中的元素所有出栈放到stackPop中,而后再删除stackPop中的元素。这样作的目的咱们就能够保证stackPop中的元素永远都是比stackPush中的元素更老。

 1class CQueue {
2    public Stack<Integer> stackPush;
3    public Stack<Integer> stackPop;
4
5    public CQueue() {
6        stackPush = new Stack<>();
7        stackPop = new Stack<>();
8    }
9
10    public void appendTail(int value) {
11        stackPush.push(value);
12    }
13
14    public int deleteHead() {
15        if (stackPop.isEmpty())
16            while (!stackPush.isEmpty())
17                stackPop.push(stackPush.pop());
18        return stackPop.isEmpty() ? -1 : stackPop.pop();
19    }
20}

 

总结

用栈实现队列也是比较常见的一道题,相似的还有用队列实现栈。

 

 

416,剑指 Offer-用两个栈实现队列_队列_02

414,剑指 Offer-重建二叉树

410,剑指 Offer-从尾到头打印链表

408,剑指 Offer-替换空格

404,剑指 Offer-数组中重复的数字

 

 

416,剑指 Offer-用两个栈实现队列_队列_03

长按上图,识别图中二维码以后便可关注。

 

若是喜欢这篇文章就点个"赞"吧