[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

简介: 本文首发于我的个人博客:尾尾部落0. 基础概念栈:后进先出(LIFO)image队列:先进先出(FIFO)image1.

本文首发于我的个人博客:尾尾部落

0. 基础概念

:后进先出(LIFO)

img_8c1994b4d5a536933821795ecce3f92d.jpe
image

队列:先进先出(FIFO)

img_bd6050744813563db11765fd96379f3b.jpe
image

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();
    }
}
目录
相关文章
|
19天前
|
缓存 监控 算法
内网监控管理软件:PHP 语言队列算法揭秘
在数字化办公环境中,内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用,包括监控数据收集、任务调度和日志记录等场景,通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理,为企业提供高效的安全保障。
23 1
|
2月前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
98 16
|
5月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
5月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
60 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
5月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
5月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
59 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
5月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
192 2
|
5月前
|
算法 数据挖掘
【栈和队列】算法题 ---- 力扣(二)
【栈和队列】算法题 ---- 力扣

热门文章

最新文章