队列和栈笔试题

1.用两个栈实现队列

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

有以下的实现方法；

方法一：创建两个栈：stack1和stack2；push时将数据添加到stack1中，pop时先判断stack2是否为空，为空则将stack1中的数据放到stack2中，弹出stack2中的数据；

2.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。 此栈包含的方法有： push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素 min():获取栈中最小元素 有以下方法： 方法一：创建两个栈，一个用于正常的push和pop，另一个用于记录当前值时的最小值；   3.栈的压入、弹出序列 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。 (a).0<=pushV.length == popV.length <=1000 (b).-1000<=pushV[i]<=1000 (c).popV 的所有数字均在 pushV里面出现过 (d).pushV 的所有数字均不相同 解题方法如下： 方法一：模拟解题出栈和入栈过程，先将pushA中的值压入栈中，当发现栈中的值和popA的值一致时，进行出栈操作，否则将pushA中的值压入栈中；   4.翻转单词序列 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

有以下几种方法；

方法一：将字符串按照空格进行分割成数组，然后将数组从后往前进行拼接即可；

方法二：先将字符串进行反转，之后按照空格分隔再反转一次即可； 

 5.滑动窗口的最大值 给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。   例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。   窗口大于数组长度或窗口长度为0的时候，返回空。

 有以下几种方法：

方法一：暴力查询，对每个窗口一次找出最大的值；

方法二：双向队列的方式，对于窗口中，我们只是需要查询出当前窗口中的最大值，因此，我们只需要记住单调递增的数值，遍历到当前值，我们 需要把比当前值小的数据都删除掉，然后查看头节点是否超出窗口范围，如果没有超出窗口范围，直接移除头节点，当前的头节点即是最大值；

import java.util.*;
public class Solution {
    public ArrayList maxInWindows(int [] num, int size) {
        ArrayList result = new ArrayList();
        if(num == null || num.length < size || size <=0){
            return result;
        }
        LinkedList queue = new LinkedList<>();
        for(int i = 0; i < num.length; i++){
            while(!queue.isEmpty() && num[queue.getLast()] <= num[i]){
                //当队列的末尾值比当前值要小，需要将末尾值给移除
                queue.removeLast();
            }
            queue.addLast(i);
            if(queue.getFirst() <= i - size){
                //将队首超出窗口的数据给移除
                queue.removeFirst();
            }
            if(i >= size - 1){
                result.add(num[queue.getFirst()]);
            }
        }
        return result;
    }
}