栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

面试题9:用两个栈实现队列【Java实现】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

面试题9:用两个栈实现队列【Java实现】

题目

用两个栈实现一个队列。分别实现appendTail函数【队列尾部插入节点】和deleteHead【队列头部删除节点】功能

思路
  • 我们首先要注意栈和队列的特点:栈顶元素是最晚加入的元素,而对于队列来说,尾元素是最晚加入的元素;栈底元素对应队列首元素。
  • 基于以上特点,我们不难发现,当stack1依次出栈到stack2后,此时stack2栈顶元素对应队列首元素,因此deleteHead的实现直接通过stack2出栈即可。
  • 而appendTail的实现直接通过stack1入栈即可,因为此时栈顶元素对应的就是队列的尾元素。
代码实现
	public static void appendTail(Stack stack1,char val) {
		//将val插入到队尾
		stack1.push(val);
	}

	public static void deleteHead(Stack stack1, Stack stack2) {
		if(stack2.isEmpty()) {
			//说明此时stack1的栈底才是队首
			while(!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}
			//删除队首元素
			stack2.pop();
		}else {
			//说明此时队首在stack2栈顶
			stack2.pop();
		}
	}

题目来源于《剑指Offer:名企面试官精讲经典编程题》

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937016.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号