栈的递归实现（不破坏栈的结构）

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
public interface IStack {
//1 入栈
boolean
push(Object obj);
//	2 出栈
Object pop();
//	3 判断栈是否为空
boolean isEmpty();
//	4 判断栈是否已满
boolean isFull();
//	5 返回栈顶元素
Object peek();
//	6 返回元素在栈中的位置
int getIndex(Object obj);
//	7 返回栈的实际长度
int size();
//	8 返回栈的容量
int getStackSize();
//	9
打印栈
void
display();
//
10 返回栈中指定位置的元素
Object getObjectByIndex(int index);
}

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
89
90
91
92
93
94
95
public class MyStack implements IStack {
private static final int MAX_SIZE = 5;
private static Object[] data = new Object[MAX_SIZE];
private static int top = -1;//[0,4]，表示当前存放的位置
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.pop();
myStack.pop();
System.out.println("size:"+myStack.size());
myStack.display();
myStack.push(5);
myStack.push(6);
myStack.display();
System.out.println("size:"+myStack.size());
System.out.println("指定下标的元素为:"+myStack.getIndex(2));
System.out.println("指定下标的元素为:"+myStack.getIndex(6));
myStack.display();
}
@Override
public boolean push(Object obj) {
if (isFull()) return false;
data[++top] = obj;
return true;
}
@Override
public Object pop() {
if (isEmpty()) return null;
Object res = data[top--];
return res;
}
@Override
public boolean isEmpty() {
return top == -1;
}
@Override
public boolean isFull() {
return top >= MAX_SIZE - 1;
}
@Override
public Object peek() {
if (isEmpty()) return null;
return data[top];
}
@Override
public int getIndex(Object obj) {
if(size()==0) return -1;
Object o = pop();
if(o!=obj) {
int idx =
getIndex(obj);
push(o);
return idx;
}else{
push(o);
return size()-1;
}
}
@Override
public int size() {
return top+1;
}
@Override
public int getStackSize() {
return MAX_SIZE;
}
@Override
public void display() {
System.out.print("当前栈内元素为：");
dfs();
System.out.println();
}
public void dfs(){
if(size()==0) return ;
Object o =pop();
dfs();
push(o);
System.out.print(o+" ");
}
@Override
public Object getObjectByIndex(int index) {
Object res = pop();
if(res ==null) return null;
if(size()!=index){
Object element = getObjectByIndex(index);
push(element);
return element;
}
else return res;
}
}