栈和队列相关面试题（java版）

1、实现一个栈，实现push和pop操作，并在O(1)的时间复杂度内获取当前栈中的min值。

基本思路：
设计一个类StackWithMin，里面有两个栈结构data和min，data 就是存取原本数据的，而min存取当前data中最小的那个数据，data和min栈中的数据个数要始终保持一致（也就是说min中的最小数据会重复）。

import java.util.Stack;

public class StackWithMin{
     private Stack<Integer> data;
     private Stack<Integer> min;

    public StackWithMin(){
        data = new Stack();
        min = new Stack();
    }

    public boolean isEmpty(){
        return data.isEmpty() && min.isEmpty();
    }

    public void push(int val){
        data.push(val);
        if (min.size() == 0 || val < min.peek()){
            min.push(val);
        }else {
            min.push(min.peek());
        }        
    }

    public int pop(){
        min.pop();
        return data.pop();
    }

    public int getMin(){
        return min.peek();
    }

    public int size(){
        return data.size();
    }
}

2、两个栈实现一个队列

基本思路：
设计一个类 QueueWithTwoStacks，该类中有两个成员变量in,out，类型是java.util.Stack，入队操作的时候将数据保存在in中，出队操作的时候调用out.pop()方法，如果out为空的话就将in中的数据出栈，并依次push到out中。

栈是一种后进先出的结构，队列是一种先进先出的结构，两个栈“负负为正”就刚好实现一个队列，实现起来还是蛮简单的。

import java.util.Stack;

public class QueueWithTwoStacks {
    private Stack<Integer> in;
    private Stack<Integer> out;

    public QueueWithTwoStacks(){
        in = new Stack<Integer>();
        out = new Stack<Integer>();
    }

    public boolean isEmpty(){
        return in.isEmpty() && out.isEmpty();
    }

    public void enqueue(int val){
        in.push(val);
    }

    public int dequeue(){
        if (out.isEmpty()){
            while (!in.isEmpty())
                out.push(in.pop());
        }
        return out.pop();
    }

    public int size(){
        return in.size() + out.size();
    }
    
}

3、两个队列实现一个栈

基本思路：
设计一个类 StackWithTwoQueues，该类中包含两个队列 queue，queue2，类型是 LinkedList<Integer>（单链表可表示队列)，入栈时哪个队列不是空的，就将数据offer到该队列中，出栈要将当前非空队列假如是queue1的前n-1个数据出队，并依次将这些数据offer到另外一个空队列queue2中，最后将queue1的最后一个数据出队并返回即可。

出栈时谨记保留非空队列中的最后一个数据，将前n-1个数据依次保存到另外一个空队列中，当非空队列中最后一个数据弹出后，原来的非空队列变为空队列，原来的空队列变为非空队列，以后对调操作，如此反复，即可实现栈的出栈操作。

 import java.util.LinkedList;

public class StackWithTwoQueues{
    private LinkedList<Integer> queue1;
    private LinkedList<Integer> queue2;

    public StackWithTwoQueues(){
       queue1 = new LinkedList<Integer>();
       queue2 = new LinkedList<Integer>();
    }

    public boolean isEmpty(){
        return queue1.isEmpty() && queue2.isEmpty();
    }

    public void push(int val){
        if (queue2.isEmpty())
            queue1.offer(val);
        else if (queue1.isEmpty())
            queue2.offer(val);
    }

    public int pop(){
        int ret = -1;
      
        if (queue2.isEmpty()){
            while (queue1.size() > 1){
                queue2.offer(queue1.poll());
            }
            ret = queue1.poll();
        }
        else if (queue1.isEmpty()){
            while (queue2.size() > 1){
                queue1.offer(queue2.poll());
            }
            ret = queue2.poll();
        }

        return ret;
    }

    public int size(){
        return queue1.size() + queue2.size();
    }
}

4、给定入栈序列，判断所给出的出栈序列是否合法

    如 入栈： 1，2，3，4，5
       出栈：4，5，3，2，1                  合法
       出栈：3，1，2，4，5                 不合法
       出栈：4，5，3，2                    不合法

基本思路：
首先，要确保入栈序列的长度和出栈序列的长度相等。
其次，将入栈序列的每一个元素入栈，入栈后看栈顶的元素是否和出栈序列的当前位置中的值相等，如果相等，那么就出栈，并将出栈序列的索引位置+1
最后，循环完成之后，返回栈的大小是否为0，即 return stack.size() == 0;

import java.util.Stack;
public static boolean isPopSequenceLegal(int[] in,int[] out){
    if (in == null || out == null || in.length != out.length)
        return false;
    Stack<Integer>  stack = new Stack<Integer>();
    for (int i = 0, j = 0; i < in.length; i ++){
        stack.push(in[i]);
        while (j < out.length && stack.size() > 0 && stack.peek() == out[j]){
          ++j;
          stack.pop();
        }
    }
return stack.size();
}

5、用一个数据实现两个栈

基本思路：
将数组从中间分为左右两部分，左边的部分入栈时++,右边的部分入栈时--即可，当中间碰头后扩容即可，代码实现的时候注意一点：
就是push和pop要传入两个参数，一个参数Tag,代表的是哪个栈，另外一个参数是具体的数值，比较简单，这里就不写代码了！

栈和队列相关面试题（java版）

推荐阅读更多精彩内容