一、共享栈的原理

如果栈使用顺序存储的方式来实现，那么一开始就需要分配合适的大小，如果插入的数据超过栈的大小，就溢出了，无法继续插入，需要通过编程的手段，进行扩容，迁移等，想象一下，如果拥有两个相同类型的栈，如果只是各用各的空间，很可能一个栈满了，另外一个栈还空着，这样使得空间无法充分利用，这也是引入共享的原因，意味着当栈1满了以后，若栈2还有空位置，那么就可以往栈2插入，反之也可以。在实际场景当中，一般两个栈，一个增，一个减，刚好符合压栈和出栈，两个栈刚好可以互补。

二、共享栈的特性

实现共享栈，其实也不难，只是需要稍微做一下处理，将一个栈分割为两个，分别为栈A和栈B，栈A的topA初始为-1，栈B的topB初始为stack.maxSize，当往stackA插入数据，topA逐渐增加，往栈B插入数据，topB逐渐变小，那么如何判断这个共享栈满了？topA + 1 = topB表示该共享栈已满。

共享栈.png

三、共享栈的实现-java

public class ShareStack {

    Object[] stackArray;
    int top1;
    int top2;
    int stackMaxSize;
    public ShareStack(int stackMaxSize){
        /**
         *  初始化一个数组，并且初始化两个栈的栈顶
         */
        this.stackMaxSize = stackMaxSize;
        stackArray = new Object[stackMaxSize];
        top1 = -1; //stackA的栈顶脚标
        top2 = stackMaxSize; //stackB的栈顶脚标
    }

    /**
     * 栈常用方法如下：
     * 1、InitShareStack 初始化一个栈
     * 2、ClearStack 清空一个栈
     * 3、StackEmtry 判断一个栈是否为空
     * 4、GetTop 若栈存在，并且非空，返回栈顶元素
     * 5、push 若栈存在，往栈顶插入一个新的元素
     * 6、pop 若栈存在，并且非空，弹出栈顶元素
     */
    public Boolean ClearStack(int flag){
        if (flag == 1){
            //清空即将值修改为null
            for (int index = 0;index <= top1;index++){
                stackArray[index] = null;
            }
            return true;
        }else if (flag ==2){
            for (int index = stackMaxSize-1;index >= top2;index--){
                stackArray[index] = null;
            }
        }
        return false;
    }

    public Boolean StackEmtry(int flag){
        if (flag == 1){
            return top1 == -1 ? true :false;
        }else if (flag ==2){
            return top2 == stackMaxSize ? true :false;
        }else{
            return false;
        }
    }

    public Object GetTop(int flag){
        // flag = 1 表示对stackA进行操作，flag = 2表示对stackB进行操作
        if (flag == 1 && top1 > -1){
            return stackArray[top1];
        }else if (flag == 2 && top2 < stackMaxSize){
            return stackArray[top2];
        }else{
            return false;
        }
    }

    public Boolean push(int flag,Object elem){
        // flag = 1 表示对stackA进行操作，flag = 2表示对stackB进行操作
        if (top1 + 1 == top2){
            //表示栈满
            return false;
        }
        if (flag == 1){
            stackArray[++top1] = elem;
            return true;
        }else if (flag == 2){
            stackArray[--top2] = elem;
            return true;
        }
        return false;
    }

    public Object pop(int flag){
        // flag = 1 表示对stackA进行操作，flag = 2表示对stackB进行操作
        if (flag == 1 && top1 > -1){
            stackArray[top1] = null;
            return stackArray[top1--];
        }else if (flag == 2 && top2 < stackMaxSize){
            stackArray[top2] = null;
            return stackArray[top2++];
        }else{
            return false;
        }
    }

    public String toString(){
        StringBuffer stringBuffer = new StringBuffer();
        for (int index = 0;index < stackMaxSize;index++){
            if (index + 1 == stackMaxSize){
                stringBuffer.append(stackArray[index]);
            }else{
                stringBuffer.append(stackArray[index]);
                stringBuffer.append(",");
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
    }
}