04、算法与数据结构 - 实战：栈和队列

数组实现栈

/**
 * 数组实现栈
 */
public class Stack01 {
   
     

    private int[] arr;

    private int size; // 栈容量

    private int index = -1;

    public Stack01(int size) {
   
     
        this.size = size;
        arr = new int[size];
    }

    public int pop() {
   
     
        if (index == -1) throw new RuntimeException("stack is empty");
        return arr[index--];
    }

    public void push(int num) {
   
     
        if (index == size - 1) throw new RuntimeException("stack is full");
        arr[++index] = num;
    }

    public boolean empty() {
   
     
        return index == -1;
    }

    public int peek() {
   
     
        if (index == -1) throw new RuntimeException("stack is empty");
        return arr[index];
    }
}

数组实现队列

一般的实现方式是定义两个指针，然后push和pull时的时候判断两个指针有没有追赶上，但是这种实现方式很麻烦而且容易出错。
更好的方式时用一个size遍历记录队列当前大小，如果size没满（size < limit），则两个指针必然没有追赶上，可以push。pull也是，只要判断size不等于0,

/**
 * 数组实现队列
 */
public class Queue01 {
   
     

    private int[] arr;

    private int size;

    private int limit;

    private int pullIndex;

    private int pushIndex;

    public Queue01(int limit) {
   
     
        this.limit = limit;
        this.size = 0;
        this.pullIndex = 0;
        this.pushIndex = 0;
        arr = new int[limit];
    }

    public int pull() {
   
     
        //size等于0，代表队列已空
        if (size == 0) throw new RuntimeException("queue is empry");
        size--;
        int element = arr[pullIndex++];
        //如果pullIndex等于limit，从新返回到0
        if (pullIndex == limit) pullIndex = 0;
        return element;
    }

    public void push(int num) {
   
     
        //size等于limit，代表队列已满
        if (size == limit) throw new RuntimeException("queue is full");
        size++;
        arr[pushIndex++] =  num;
        //如果pushIndex等于limit，从新返回到0
        if (pushIndex == limit) pushIndex = 0;
    }

    public int size() {
   
     
        return size;
    }

}

用栈实现队列

面试官常见的问法：请使用栈实现宽度优先遍历

此时要想到，宽度优先遍历是用队列实现的，是没法用栈直接实现的，这时候应该要先用栈实现队列，再用这个队列去进行宽度优先遍历

定义一个push栈和pull栈
push时直接push到push栈
pull时检查pull栈是否为空，是则从push栈倒到pull栈，但是要把push一次倒空

/**
 * 用栈实现队列
 */
public class Queue02 {
   
     

    private Stack01 stack1;

    private Stack01 stack2;
    
    private int size;
    
    private int limit;

    public Queue02(int capacity) {
   
     
        stack1 = new Stack01(capacity);
        stack2 = new Stack01(capacity);
        this.size = 0;
        this.limit = capacity;
    }

    public int pull() {
   
     
        if (size == 0) throw new RuntimeException("queue is empry");
        //从队列获取元素时，发现stack2为空，则把stack1中的所有元素倒入stack2中
        if (stack2.empty()) {
   
     
            while (!stack1.empty()) {
   
     
                stack2.push(stack1.pop());
            }
        }
        size--;
        return stack2.pop();
    }
    
    public void push(int num) {
   
     
        if (size == limit) throw new RuntimeException("queue is full");
        stack1.push(num);
        size++;
    }

}

用两个栈来实现，一个用于压入元素，一个用于取出元素，当取出元素时，发现获取元素的栈为空，则一口气把压入元素的栈中的元素全部倒入获取元素的栈中，这样就可以保证元素的先入先出顺序。

用队列实现栈

面试官常见的问法：请使用队列实现深度优先遍历

同理，先用队列实现栈，再用这个栈去实现深度优先遍历

实现方式就是两个队列互相倒
例如定义了queue1和queue2
push了1、2、3、4、5
要弹出一个数返回时，先把queue1中的1，2，3，4挪到queue2去
然后去除5
queue1和queue2交换
然会5

/**
 * 用队列实现栈
 */
/**
 * 用队列实现栈
 */
public class Stack02 {
   
     

    private Queue01 q1;

    private Queue01 q2;

    public Stack02(int size) {
   
     
        q1 = new Queue01(size);
        q2 = new Queue01(size);
    }

    public int pop() {
   
     
        //把q1中的元素放入q2，直到q1剩下一个元素
        while (q1.size() > 1) {
   
     
            q2.push(q1.pull());
        }
        int num = q1.pull();

        //q1和q2的引用互相交换
        Queue01 temp = q1;
        q1 = q2;
        q2 = temp;

        return num;
    }
    
    public void push(int num) {
   
     
        q1.push(num);
    }

}

最小栈

/**
 * 最小栈，min方法返回栈中的最小值
 */
public class Stack03 {
   
     

    private Stack01 dataStack;

    private Stack01 minStack;

    public Stack03(int size) {
   
     
        dataStack = new Stack01(size);
        minStack = new Stack01(size);
    }

    public void push(int num) {
   
     
        dataStack.push(num);
        //每次数据栈压入一个数，最小栈也压入一个数，该数为栈顶与当前压入数中较小的一个，保证栈顶总是最小值
        if (!minStack.empty() && minStack.peek() > num) minStack.push(num);
        else minStack.push(minStack.peek());
    }
    
    public int pop() {
   
     
        //同步把最小栈的栈顶数弹出
        minStack.pop();
        return dataStack.pop();
    }
    
    public int min() {
   
     
        //最小栈的栈顶就是栈中的最小值
        return minStack.peek();
    }

}