数据结构:双端栈

待我称王封你为后i 2023-09-28 14:56 96阅读 0赞

## 基本介绍 ##

![在这里插入图片描述][8ec9a4568a3349ffa549d4a398adf235.png]

*  双端栈是线性表的一种，也是栈的一个特殊分类
 *  我们可以用动态数组和栈的思想来实现双端栈
 *  因为它有两边的操作，比较特殊，所以不能借助前面两节实现的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();
        }
    }

![在这里插入图片描述][9525fc9c037f43088facecb443a44c7a.png]

[8ec9a4568a3349ffa549d4a398adf235.png]: https://img-blog.csdnimg.cn/8ec9a4568a3349ffa549d4a398adf235.png
[9525fc9c037f43088facecb443a44c7a.png]: https://img-blog.csdnimg.cn/9525fc9c037f43088facecb443a44c7a.png