[算法总结] 3 道题搞定 BAT 面试——堆栈和队列
本文首发于我的个人博客:尾尾部落
0. 基础概念
栈:后进先出(LIFO)
队列:先进先出(FIFO)
1. 栈的 java 实现
import java.util.Arrays; public class Stack { private int size = 0; //栈顶位置 private int[] array; public Stack(){ this(10); } public Stack(int init) { if(init <= 0){ init = 10; } array = new int[init]; } /** * 入栈操作 * @param item 入栈的元素 */ public void push(int item){ if(size == array.length){ array = Arrays.copyOf(array, size*2); //扩容操作 } array[size++] = item; } /** * 获取栈顶元素,但栈顶元素不出栈 * @return 栈顶元素 */ public int peek(){ if(size == 0){ //空栈 throw new IndexOutOfBoundsException("栈是空的"); } return array[size-1]; } /** * 出栈,同时获取栈顶元素 * @return */ public int pop(){ int item = peek(); //获取栈顶元素 size--; //直接使元素个数减1,不用清除元素,下次入栈会覆盖旧元素的值 return item; } /** * 判断栈是否已满 * @return */ public boolean isFull(){ return size == array.length; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return size == 0; } public int getSize(){ return size; } }
2. 队列的 java 实现
public class ArrayQueue { private final Object[] queue; //声明一个数组 private int head; private int tail; /** * 初始化队列 * @param capacity 队列长度 */ public ArrayQueue(int capacity){ this.queue = new Object[capacity]; } /** * 入队 * @param o 入队元素 * @return 入队成功与否 */ public boolean put(Object o){ if(head == (tail+1)%queue.length){ //说明队满 return false; } queue[tail] = o; tail = (tail+1)%queue.length; //tail标记后移一位 return true; } /** * 返回队首元素,但不出队 * @return */ public Object peak() { if(head==tail){ //队空 return null; } return queue[head]; } /** * 出队 * @return 出队元素 */ public Object pull(){ if(head==tail){ return null; } Object item = queue[head]; queue[head] = null; return item; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 判断是否为满 * @return */ public boolean isFull(){ return head == (tail+1)%queue.length; } /** * 获取队列中的元素个数 * @return */ public int getsize(){ if(tail>=head){ return tail-head; }else{ return (tail+queue.length)-head; } } }
3. 用两个栈实现队列
剑指offer:用两个栈实现队列
LeetCode:Implement Queue using Stacks
class MyQueue { Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); /** Push element x to the back of queue. */ public void push(int x) { input.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { peek(); return output.pop(); } /** Get the front element. */ public int peek() { if(output.isEmpty()){ while(!input.isEmpty()) output.push(input.pop()); } return output.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return input.isEmpty() && output.isEmpty(); } }
4. 用队列实现栈
LeetCode:Implement Stack using Queues
class MyStack { Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); /** Push element x onto stack. */ public void push(int x) { if(q1.isEmpty()){ q1.add(x); for(int i = 0; i < q2.size(); i++){ q1.add(q2.poll()); } }else{ q2.add(x); for(int i = 0; i < q1.size(); i++){ q2.add(q1.poll()); } } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return q1.isEmpty() ? q2.poll() : q1.poll(); } /** Get the top element. */ public int top() { return q1.isEmpty() ? q2.peek() : q1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return q1.isEmpty() && q2.isEmpty(); } }
5. 包含min函数的栈
剑指offer:包含min函数的栈
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); public void push(int x) { stack.push(x); if(temp.isEmpty() || temp.peek() >= x) temp.push(x); } public void pop() { int x = stack.pop(); int min = temp.peek(); if(x == min) temp.pop(); } public int top() { return stack.peek(); } public int getMin() { return temp.peek(); } }
6. 栈的压入、弹出序列
剑指offer:栈的压入、弹出序列
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA, int [] popA) { if(pushA.length != popA.length || pushA.length == 0 || popA.length == 0) return false; Stack<Integer> stack = new Stack<>(); int index = 0; for(int i = 0; i < pushA.length; i++){ stack.push(pushA[i]); while(!stack.empty() && stack.peek() == popA[index]){ stack.pop(); index++; } } return stack.empty(); } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
深度 | 朴素贝叶斯模型算法研究与实例分析
深度 | 朴素贝叶斯模型算法研究与实例分析 ( 白宁超2018年9月3日15: 56:20) 导读:朴素贝叶斯模型是机器学习常用的模型算法之一,其在文本分类方面简单易行,且取得不错的分类效果。所以很受欢迎,对于朴素贝叶斯的学习,本文首先介绍理论知识即朴素贝叶斯相关概念和公式推导,为了加深理解,采用一个维基百科上面性别分类例子进行形式化描述。然后通过编程实现朴素贝叶斯分类算法,并在屏蔽社区言论、垃圾邮件、个人广告中获取区域倾向等几个方面进行应用,包括创建数据集、数据预处理、词集模型和词袋模型、朴素贝叶斯模型训练和优化等。然后结合复旦大学新闻语料进行朴素贝叶斯的应用。最后,大家熟悉其原理和实现之后,采用机器学习sklearn包进行实现和优化。由于篇幅较长,采用理论理解、案例实现、sklearn优化三个部分进行学习。(本文原创,转载必须注明出处:朴素贝叶斯模型算法研究与实例分析) 复旦新闻语料:朴素贝叶斯中文文本分类 项目概述 本节介绍朴素贝叶斯分类算法模型在中文领域中的应用。我们对新闻语料进行多文本分类操作,本文选择艺术、文学、教育、哲学、历史五个类别的训练文本,然后采用新的测试语料进行分...
- 下一篇
区块链的技术特征 区块链开发公司哪家好
区块链是近几年最具革命性的创新技术,同时也成为各大投资机构疯狂追逐的风口。 目前国内外区块链技术大多处于发展初期,将与往后成熟期的区块链技术千差万别。简单介绍一下当前区块链的主流分支形态,即按照链式处理“去中心化”程度可将区块链技术进一步划分为以下三类: 区块链具有去中心化、时序数据、集体维护、可编程和安全可信等特点。 去中心化:区块链数据的验证、记账、存储、维护和传输等过程均是基于分布式系统结构,采用纯数学方法而不是中心机构来建立分布式节点间的信任关系,从而形成去中心化的可信任的分布式系统; 时序数据:区块链采用带有时间戳的链式区块结构存储数据,从而为数据增加了时间维度,具有极强的可验证性和可追溯性; 集体维护:区块链系统采用特定的经济激励机制来保证分布式系统中所有节点均可参与数据区块的验证过程,并通过共识算法来选择特定的节点将新区块添加到区块链; 可编程:区块链技术可提供灵活的脚本代码系统,支持用户创建高级的智能合约、货币或其它去中心化应用; 安全可信:区块链技术采用非对称密码学原理对数据进行加密,同时借助分布式系统各节点的工作量证明等共识算法形成的强大算力来抵御外部攻击、保证区块...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7设置SWAP分区,小内存服务器的救世主