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

大话数据结构七：两栈共享存储空间（双向栈）2014-12-301. 为什么要使用双向栈？

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

2. 双向栈有什么特点？

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

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; // 栈1private static final Integer STACK_2 = 2; // 栈2public 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） { // 操作的是栈1arr[++top1] = data; // 栈1前进一位return true;} else if （stackNum == STACK_2） { // 操作的是栈2arr[--top2] = data; // 栈2后退一位return true;} else {System.out.println（"请输入正确的栈编号: 1 或 2"）;return false;}}// 弹栈@SuppressWarnings（"unchecked"）public T pop（int stackNum） {if （stackNum == STACK_1） { // 操作的是栈1if （top1 == -1） {System.out.println（"栈1已经是空栈..."）;return null;}return （T） arr[top1--]; // 栈1后退一位} else if （stackNum == STACK_2） { // 操作的是栈2if （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