JAVA-高频面试题汇总:堆和栈

心已赠人 2022-10-27 12:10 218阅读 0赞

## 前言 ##

为了让小伙伴们更好地刷题,我将所有leetcode常考题按照知识点进行了归纳。

## 高频题汇总: ##

[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]  
[JAVA-高频面试题汇总:数组（上）][JAVA- 5]  
[JAVA-高频面试题汇总:数组（下）][JAVA- 6]

#### JAVA-高频面试题汇总:堆和栈 ####

接下来还会进行其他模块的总结,有一起在准备暑期实习的JAVA后端的伙伴可以一起交流!  
小编微信: Apollo\_\_\_quan

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

## 目录 ##

1.  用两个栈实现队列（剑指）
2.  用队列实现栈
3.  包含min函数的栈（剑指）
4.  栈的压入、弹出序列（剑指）

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

##### 1.[用两个栈实现队列（剑指）][Link 1] #####

![image-20210204113042329][]

**思路**

新元素入栈前先把栈1中元素移到栈2，新元素入栈后把栈2中元素移回栈一

**时间复杂度：O(n)**。插入O(n),其他O(1)

**空间复杂度：O(n)**。需要使用两个栈存储已有的元素。

class CQueue { 
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;
        public CQueue() { 
        stack1 = new Stack<>();
        stack2 = new Stack<>();
        }
        
        public void appendTail(int value) { 
        while(!stack1.isEmpty()){   
         stack2.push(stack1.pop());
        }
        stack1.push(value);
        while(!stack2.isEmpty()){ 
            stack1.push(stack2.pop());
        }
        }
        
        public int deleteHead() { 
         if(stack1.isEmpty()){ 
            return -1;
         } 
         else{ 
         return stack1.pop();
        }
        }
    }

##### 2.[用队列实现栈][Link 2] #####

![image-20210204113514736][]

**思路**

方法一：[一个队列实现栈][Link 3]

入队时q1.add(q1.remove())，保证最新入队的在队列头部

class MyStack { 
    
        /** Initialize your data structure here. */
        public MyStack() { 
    
        }
        private LinkedList<Integer> q1 = new LinkedList<>();
    
        public void push(int x) { 
        	q1.add(x);
            for(int i=0; i < q1.size() - 1; i++){  //把之前的元素都重新入队，这样新元素就是队头
                q1.add(q1.remove()); 
            }
        }
        
        public int pop() { 
             int b = q1.remove();
             return b;
        }
        
        public int top() { 
            return q1.peek();
        }
        
        public boolean empty() { 
            return q1.isEmpty();
        }
    }

方法二：[两个队列][Link 2]

入栈时先进入queue2，再把queue1中所有元素入队queue2，再交换queue1和queue2，保证新元素在queue1队头

class MyStack { 
        Queue<Integer> queue1;
        Queue<Integer> queue2;
    
        /** Initialize your data structure here. */
        public MyStack() { 
            queue1 = new LinkedList<Integer>();
            queue2 = new LinkedList<Integer>();
        }
        
        /** Push element x onto stack. */
        public void push(int x) { 
            queue2.offer(x);
            while (!queue1.isEmpty()) { 
                queue2.offer(queue1.poll());
            }
            Queue<Integer> temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }
        
        /** Removes the element on top of the stack and returns that element. */
        public int pop() { 
            return queue1.poll();
        }
        
        /** Get the top element. */
        public int top() { 
            return queue1.peek();
        }
        
        /** Returns whether the stack is empty. */
        public boolean empty() { 
            return queue1.isEmpty();
        }
    }

##### 3.[包含min函数的栈][min] #####

![image-20210204120354655][]

**思路**

维护一个辅助栈B，最小值才入栈

时间复杂度 O(1))： push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别。  
空间复杂度 O(N)： 当共有 N个待入栈元素时，辅助栈 BB 最差情况下存储 N个元素，使用 O(N) 额外空间。

class MinStack { 
        Stack<Integer> A, B;
        public MinStack() { 
            A = new Stack<>(); //栈A正常进出
            B = new Stack<>(); //栈B记录最小值
        }
        public void push(int x) { 
            A.add(x);
            if(B.empty() || B.peek() >= x)
                B.add(x);
        }
        public void pop() { 
            if(A.pop().equals(B.peek()))
                B.pop();
        }
        public int top() { 
            return A.peek();
        }
        public int min() { 
            return B.peek();
        }
    }

##### 4.[栈的压入、弹出序列][Link 4] #####

![image-20210204124851058][]

**思路**

1.构造辅助栈stack，若压入和弹出正确，结束后栈必为空

2.根据pushed\[\]不断入栈，当stack栈顶等于popped\[i\],stack栈顶出栈代表弹出

class Solution { 
        public boolean validateStackSequences(int[] pushed, int[] popped) { 
            Stack<Integer> stack = new Stack<>();
            int i = 0;
            for(int num : pushed) { 
                stack.push(num); // num 入栈
                while(!stack.isEmpty() && stack.peek() == popped[i]) {  // 循环判断与出栈，!stack.isEmpty() 防止空栈报错
                    stack.pop();
                    i++;
                }
            }
            return stack.isEmpty();
        }
    }

## 总结 ##

堆栈题型整理完毕，其余类型  
[JAVA-高频面试题汇总:动态规划][JAVA-]  
[JAVA-高频面试题汇总:字符串][JAVA- 1]  
[JAVA-高频面试题汇总:二叉树(上)][JAVA- 2]  
[JAVA-高频面试题汇总:二叉树(下)][JAVA- 3]  
[JAVA-高频面试题汇总:回溯][JAVA- 4]

[JAVA-]: https://blog.csdn.net/weixin_44273302/article/details/112000020
[JAVA- 1]: https://blog.csdn.net/weixin_44273302/article/details/112436689
[JAVA- 2]: https://blog.csdn.net/weixin_44273302/article/details/112142969
[JAVA- 3]: https://blog.csdn.net/weixin_44273302/article/details/112200568
[JAVA- 4]: https://blog.csdn.net/weixin_44273302/article/details/113423696
[JAVA- 5]: https://blog.csdn.net/weixin_44273302/article/details/113575810
[JAVA- 6]: https://blog.csdn.net/weixin_44273302/article/details/113583602
[Link 1]: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-3/
[image-20210204113042329]: /images/20221024/f0e5cc0a24c24493a1620ee94d900ead.png
[Link 2]: https://leetcode-cn.com/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/
[image-20210204113514736]: /images/20221024/d1f060408497433f9de4133cacf64fc7.png
[Link 3]: https://leetcode-cn.com/problems/implement-stack-using-queues/solution/ni-xin-bu-xin-yi-miao-jiu-rang-ni-zheng-vhk70/
[min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[image-20210204120354655]: /images/20221024/c03b9dc2459f4721aa3bc3b700906cb8.png
[Link 4]: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[image-20210204124851058]: /images/20221024/bd463e271b7648ddbf46d102c231d001.png