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

Java基础面试题 2年前 (2022) 程序员胖胖胖虎阿

279 0 0

前言

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

高频题汇总:

JAVA-高频面试题汇总:动态规划
 JAVA-高频面试题汇总:字符串
 JAVA-高频面试题汇总:二叉树(上)
JAVA-高频面试题汇总:二叉树(下)
JAVA-高频面试题汇总:回溯
 JAVA-高频面试题汇总:数组（上）
JAVA-高频面试题汇总:数组（下）

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

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

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.用队列实现栈

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

思路

方法一：一个队列实现栈

入队时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();
    }
}

方法二：两个队列

入栈时先进入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函数的栈

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

思路

维护一个辅助栈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.栈的压入、弹出序列

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

思路

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();
    }
}