1. 两栈共享存储空间

定义

使用两个栈来对相同类型的数据来进行存储,就是有个顶部和尾部。

若只是使用一个栈来使用的话,事先确定栈的容量是非常重要的,因为当容量小了,就需要不断扩大容量,或者容量大了,就会浪费一段存储空间,这都是很麻烦的。但是使用两个栈就可以做到最大限度地利用事先开辟的存储空间。

当两个栈需要操作相反的关系的时候就可以考虑这个,就比如总有人赚钱和赔钱,那就一边负责增加元素,另一边负责删除元素。

实现

两栈可以理解为一个长度为 n 的线性表从任意位置切开成两段空间,这样子就会有数组的首尾端都是两个栈的栈底。

左边的栈为空的时候,就是栈顶为 -1(栈顶的元素位置),右边的栈为空的时候就是栈顶元素为 n 的时候。

所以当左边栈满的时候,就是栈顶为 n-1,而右边栈为空就是栈顶为 n,而右边栈满的时候就是栈顶为 0,左边栈为空就是栈顶为 -1。所以当两个碰面的时候,也就是两个栈满的时候,就是两个栈顶的位置相差一的时候,即 leftTop + 1 = rightTop。

理解上面这个就好实现了,栈需要记录左右两边的栈顶的位置,所以栈的结构需要改变,需要有栈初始化两个栈的容量的总量,还必须声明左右两边栈顶的位置。

两个方法实现
  1. push():这个需要加入一个栈号参数来判断需要插入那个栈,同时插入时需要判断栈是否满
  2. pop():也需要加一个栈号参数来判断删除哪边栈的元素,删除时需要判断栈是否为空。

2.代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 两栈共享空间
public class DoubleStack {
int[] arr;
// 左右分别记录两个栈的的下一个元素需要插入的位置
int left;
int right;
int length;

public DoubleStack(int capacity){
arr = new int[capacity];
left = 0;
right = capacity - 1;
length = 0;
}

public DoubleStack(){
this(10);
}

public boolean isEmpty(){
return length == 0;
}

public int length(){
return length;
}

public void push(int e, int stackSide){
if(left == right + 1)
throw new IllegalArgumentException("栈已满,入栈失败");

// 1 代表左边的栈, 2 代表右边的栈
if(stackSide == 1){
arr[left] = e;
left ++;
}
else if (stackSide == 2){
arr[right] = e;
right --;
}
else
throw new IllegalArgumentException("stackSide 错误");
length ++;
}

public int pop(int stackSide){
if(stackSide == 1){
if(left == 0)
throw new IllegalArgumentException("出栈失败,左栈为空");
int e = arr[left];
length --;
left --;
return e;
}
else if(stackSide == 2){
if(right == arr.length - 1)
throw new IllegalArgumentException("出栈失败,右栈为空");
int e = arr[right];
length --;
right ++;
return e;
}
else
throw new IllegalArgumentException("出栈失败,栈不存在");

}

public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("capacith: %d, length: %d\n", arr.length, length()));
res.append("DoubleStack: left tail [");
for(int i = 0; i < left; i++){
res.append(arr[i]);
if(i != left - 1)
res.append(", ");
}
res.append("] top ");

res.append("right top [");
for(int i = right + 1; i < arr.length; i++){
res.append(arr[i]);
if(i != arr.length - 1)
res.append(", ");
}
res.append("] tail");

return res.toString();
}