大话数据结构七：两栈共享存储空间（双向栈）

1. 为什么要使用双向栈？

通过上一篇博客 - 特殊的线性表（栈），不难知道栈的顺序存储（数组实现）性能相对较好，因为它不存在插入和删除时移动元素的问题，但是它有一点缺陷：要事先确定数组存储容量的大小，万一不够，就需要扩充数组容量。这时双向栈就派上用场了，它可以最大限度的利用事先开辟的存储空间。

2. 双向栈有什么特点？

数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度M-1处。这样，两个栈如果增加元素，就会从两端点向中间延伸（如下图）。

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

3. Java实现双向栈

// 双向栈的数组实现
public class ShareStack<T> {
    private Object[] arr; // 数组实现栈的操作
    private int top1; // 栈1: 栈顶指针
    private int top2; // 栈2: 栈顶指针
    private static Integer DEFAULT_SIZE = 16; // 数组默认长度
    private static final Integer STACK_1 = 1; // 栈1
    private static final Integer STACK_2 = 2; // 栈2  

    public ShareStack() {
        init();
    }  

    public ShareStack(int size) {
        DEFAULT_SIZE = size;
        init();
    }  

    // 初始化栈
    public void init() {
        arr = new Object[DEFAULT_SIZE];
        this.top1 = -1;
        this.top2 = DEFAULT_SIZE;
    }  

    // 压栈
    public boolean push(int stackNum, T data) {
        if (top1 + 1 == top2) { // 栈已满
            System.out.println("栈已满,不能再push元素了..");
            return false;
        }
        if (stackNum == STACK_1) { // 操作的是栈1
            arr[++top1] = data; // 栈1前进一位
            return true;
        } else if (stackNum == STACK_2) { // 操作的是栈2
            arr[--top2] = data; // 栈2后退一位
            return true;
        } else {
            System.out.println("请输入正确的栈编号: 1 或 2");
            return false;
        }
    }  

    // 弹栈
    @SuppressWarnings("unchecked")
    public T pop(int stackNum) {
        if (stackNum == STACK_1) { // 操作的是栈1
            if (top1 == -1) {
                System.out.println("栈1已经是空栈...");
                return null;
            }
            return (T) arr[top1--]; // 栈1后退一位
        } else if (stackNum == STACK_2) { // 操作的是栈2
            if (top2 == DEFAULT_SIZE) {
                System.out.println("栈2已经是空栈...");
                return null;
            }
            return (T) arr[top2++]; // 栈2前进一位
        } else {
            System.out.println("请输入正确的栈编号: 1 或 2");
            return null;
        }
    }  

    // 获取栈顶元素
    @SuppressWarnings("unchecked")
    public T getTop(int stackNum) {
        if (stackNum == STACK_1) {
            if (this.top1 != -1) {
                return (T) arr[top1];
            }
        } else if (stackNum == STACK_2) {
            if (stackNum != DEFAULT_SIZE) {
                return (T) arr[top2];
            }
        } else {
            System.out.println("请输入正确的栈编号: 1 或 2");
        }
        return null;
    }  

    // 获取数组长度
    public int size() {
        return DEFAULT_SIZE + top1 + 1 - top2;
    }  

    // 判断是否为空栈
    public boolean isEmpty() {
        return this.top1 == -1 && this.top2 == DEFAULT_SIZE;
    }  

    // 置为空栈
    public boolean clear() {
        this.top1 = -1;
        this.top2 = DEFAULT_SIZE;
        return true;
    }  

    // 测试方法
    public static void main(String[] args) throws Exception {
        ShareStack<Integer> stack = new ShareStack<Integer>();
        stack.push(1, 1);
        stack.push(2, 2);
        stack.pop(1);
        stack.pop(2);
    }
}

4. 什么时候使用双向栈？

1.） 两个栈的空间需求有相反关系时，也就是当一个栈增长时另一个栈在缩短的情况。

2.） 两个栈需要具有相同的数据类型，如果数据类型不同，将会使问题复杂化。

作者：csdn博客 zdp072

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， 顺序栈
， 栈
， return
， stack
， top
， public
， 双向
， 两个return
， 数据结构栈
， 两个栈
， 单调栈
， 栈结构
栈数据结构
，以便于您获取更多的相关知识。