数据结构:双端栈

• 双端栈是线性表的一种，也是栈的一个特殊分类
• 我们可以用动态数组和栈的思想来实现双端栈
• 因为它有两边的操作，比较特殊，所以不能借助前面两节实现的ArrayList或ArrayStack来实现，这里需要从头实现双端栈。
• 因为入栈，出栈这些操作都有两个方向的选择，所以我们可以把这个栈分成两个区，左栈和右栈，id=0,表示这是左栈，id=1表示是右栈，通过传入的参数来决定是对左栈进行操作还是对右栈进行操作

import java.util.Arrays;

/** * @author zengyihong * @create 2022--07--13 16:09 */
public class ArrayDoubleEndStack<E> { 
    //存元素
    private E[] data;
    //左栈的栈顶 ltop=-1说明是空栈 ltop+1表示左栈元素的个数
    private int ltop;
    //右栈的栈顶 rtop=data.length表示右栈是空栈 data.length-rtop表示右栈元素个数
    private int rtop;
    private static int DEFAULT_SIZE = 10;

    public ArrayDoubleEndStack() { 
        data = (E[]) new Object[DEFAULT_SIZE];
        ltop = -1;
        rtop = data.length;
    }

    /** * 入栈 * * @param element 元素 * @param stackId 表示左栈或右栈 */
    public void push(E element, int stackId) { 
        //双端栈满了，需要扩容
        if (ltop + 1 == rtop) { 
            resize(data.length * 2);
        }
        switch (stackId) { 
            case 0:
                //往左栈 入栈元素
                data[++ltop] = element;
                break;
            case 1:
                data[--rtop] = element;
                break;
        }
    }

    /** * 出栈 * * @param stackId * @return */
    public E pop(int stackId) { 
        if (isEmpty(stackId)) { 
            throw new NullPointerException("stack is null");
        }
        E rs = null;
        switch (stackId) { 
            case 0:
                rs = data[ltop];
                data[ltop--] = null;


            case 1:
                rs = data[rtop];
                data[rtop++] = null;


        }
        //如果元素个数<=len/4 && len>DEFAULT,进行缩容
        if (size(0) + size(1) <= data.length / 4 && data.length > DEFAULT_SIZE) { 
            resize(data.length / 2);
        }

        return rs;
    }

    /** * 获取有效元素个数 * * @return */
    public int size(int stackId) { 
        switch (stackId) { 
            case 0:
                return ltop + 1;
            case 1:
                return data.length - rtop;
        }
        return -1;
    }

    /** * 判断某一端的栈是否为空 * * @param stackId * @return */
    private boolean isEmpty(int stackId) { 
        switch (stackId) { 
            case 0:
                return ltop == -1;
            case 1:
                return rtop == data.length;
        }
        return false;
    }

    /** * 扩容 * @param newLen */
    private void resize(int newLen) { 
        E[]newData=(E[]) new Object[newLen];
        //先处理左端栈
        for (int i = 0; i <=ltop; i++) { 
            newData[i]=data[i];
        }
        //再处理右端栈

        int index=rtop;
        for (int i = newLen-size(1); i < newData.length ; i++) { 
            newData[i]=data[index++];
        }
        rtop=newLen-size(1);
        data=newData;
    }

    /** * 查看当前栈顶元素 * @param stackId * @return */
    public E peek(int stackId){ 
        if (isEmpty(stackId)){ 
            throw new NullPointerException("stack is null");
        }
        switch (stackId){ 
            case 0:
                return data[ltop];
            case 1:
                return data[rtop];
        }
        return null;
    }

    public void clear(int stackId){ 
        switch (stackId){ 
            case 0:
                ltop=-1;
                break;
            case 1:
                rtop=data.length;
                break;
        }
    }

    @Override
    public String toString() { 
        StringBuilder builder = new StringBuilder(String.format("ArrayDoubleEndStack:%d/%d\n", size(0)+size(1),data.length));
        if (isEmpty(0)){ 
            builder.append("leftStack[]\n");
        }else{ 
            builder.append("leftStack:[");
            for (int i = 0; i <= ltop; i++) { 
                builder.append(data[i]);
                if (i==ltop){ 
                    builder.append("]");
                    builder.append("\n");
                }else { 
                    builder.append(",");
                }
            }
        }
        if (isEmpty(1)){ 
            builder.append("rightStack[]");
        }else{ 
            builder.append("rightStack:[");
            for (int i = data.length-1; i >=rtop; i--) { 
                builder.append(data[i]);
                if (i==rtop){ 
                    builder.append("]");
                    builder.append("\n");
                }else { 
                    builder.append(",");
                }
            }

        }
        return builder.toString();
    }
}