Java面试--队列和栈

不念不忘少年蓝@ 2021-09-27 07:52 330阅读 0赞

> **面试题：队列和栈区别 (百度面试题)  
> 面试题：使用两个栈实现队列(百度面试题)  
> 面试题：两个栈实现最小值栈(百度面试题)  
> 面试题：链表倒数第k个数(360面试题)**

**一、区别：**  
1、栈的插入和删除操作只允许在表的尾端进行（在栈中成为“栈顶”），满足“FIFO：First In Last Out”；  
队列只允许在表尾插入数据元素，在表头删除数据元素,满足“First In First Out”  
2、遍历数据速度不同。栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影响数据结构，速度要快的多  
**二、使用两个栈实现队列：**  
**我的这篇博客写了：[剑指Offer（五）用两个栈实现队列（Java版 )][Offer_Java_]  
三、两个栈实现最小值栈：**

public class MinStack {
        private Stack<Integer> stackData; //数据栈
        private Stack<Integer> stackMin;  //保存当前最小数的栈（称最小栈
        //构造函数
        public MinStack(){
            stackData=new Stack<>();
            stackMin=new Stack<>();
        }
        //压人函数
        public void push(Integer num){
            //压入时判断最小栈是否为空或者要压入的数是否比最小栈栈顶数还小时则压入数据站的同时压入最小栈
            if(stackMin.isEmpty()||getMin()>num){
                stackMin.push(num);
            }
            stackData.push(num);
        }
        //弹出函数
        public Integer pop(){
            Integer num=stackData.pop();
            if(stackMin.peek() == num){
                stackMin.pop();
            }
            return num;
        }
        //获取栈中最小数
        public Integer getMin(){
            return stackMin.peek();
        }
    }

**四、链表倒数第k个数：  
我的这篇博客写了：[剑指Offer（十四）链表中倒数第k个结点（Java版 )][Offer_k_Java_]**

--------------------

**Java面试的完整博客目录如下：[Java笔试面试目录][Java]**

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916] 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。  
> ![这里写图片描述][70]**

[Offer_Java_]: https://blog.csdn.net/weixin_41835916/article/details/80627020
[Offer_k_Java_]: https://blog.csdn.net/weixin_41835916/article/details/80675560
[Java]: https://blog.csdn.net/weixin_41835916/article/details/81413498
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916
[70]: /images/20210923/d0e1b1b935e74a8aa9f5efd8c1c7e74b.png