数据结构与算法:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

考查对栈的理解,入栈,出栈操作,解题思路。

题:

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

解:

解一:

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
package interview.q1;

import java.util.Random;
import java.util.Stack;

/**
* 栈:一种线型数据结构,先进后出,后进先出。可以看做只有一个开口的圆桶容器。
* 问:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
* 思路一:使用两个栈,一个完成数据的出栈入栈操作,另一个辅助栈存储每次操作之后得到的最小值。
*/
public class Demo1 {

Stack stack1 = new Stack();
Stack stack2 = new Stack();

int min = 0;

/**
* 入栈
*/
public void push(int node) {
stack1.push(node);
//只有一个元素时
if (stack1.size() == 1) {
min = (int) stack1.peek();
} else {
//每加入一个元素,都需要将其与最小值比较,判断此次操作后的最小值
if (min > node) {
min = node;
}
}
//栈顶一直维持最小,加入
stack2.push(min);
}

/**
* 出栈
*/
public void pop() {
//如果出栈的元素大于min,那么stack2的栈顶元素与倒数第二个是相同的,所以删掉一个后,最小值仍然是栈顶元素
stack1.pop();
//无论栈顶元素与min是否相等,都需要向下移动一个,要保证辅助栈stack2中值与操作的一致 性
stack2.pop();
min = (int) stack2.peek();
}

/**
* 栈顶
*
* @return
*/
public int top() {
return (int) stack1.peek();
}

/**
* 最小
*
* @return
*/
public int min() {
return min;
}

public static void main(String[] args) {
Demo1 demo1 = new Demo1();
Random random = new Random();
for (int i = 0; i < 10; i++) {
int anInt = random.nextInt(100);
demo1.push(anInt);
}
System.out.println(demo1.min());

for (int i = 0; i < 10; i++) {
demo1.pop();
}
System.out.println(demo1.min());
}
}

解二:

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
96
97
98
99
100
101
102
package interview.q1;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
* 栈:一种线型数据结构,先进后出,后进先出。可以看做只有一个开口的圆桶容器。
* 问:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。
* 思路二:原理同方法一,只是数据操作的栈是自定义栈,通过数组扩容完成
*/
public class Demo2 {

private Integer[] elements = new Integer[10];
private int size = 0;
private int min = 0;

private Stack<Integer> minStack = new Stack<>();

/**
* 入栈
*
* @param node
*/
public void push(int node) {
//确保可以再添加一个元素,如果不够就扩容
ensureCapacity(size + 1);
//添加元数,数组元素个数为size
elements[size++] = node;
if (size == 1) {
min = node;
} else {
if (node < min) {
min = node;
}
}
minStack.push(min);
}

/**
* 数组扩容
*
* @param size
*/
public void ensureCapacity(int size) {
int len = elements.length;
if (size > len) {
int newLen = len * 2;
elements = Arrays.copyOf(elements, newLen);
}
}

/**
* 出栈
*/
public void pop() {
if (size >= 1) {
elements[size - 1] = null;
//此处需要注意,int[]数组元素不能设置为null,即使是(Integer)null,也会报空指针异常
//因此使用 Integer[] 数组
}
size--;
minStack.pop();
min = minStack.peek();
}

/**
* 栈顶
*
* @return
*/
public int top() {
if (size >= 1) {
return elements[size - 1];
}
return Integer.parseInt(null);
}

/**
* 最小
*
* @return
*/
public int min() {
return min;
}

public static void main(String[] args) {
Demo2 demo1 = new Demo2();
Random random = new Random();
for (int i = 0; i < 10; i++) {
int anInt = random.nextInt(100);
demo1.push(anInt);
}
System.out.println(demo1.min());

for (int i = 0; i < 10; i++) {
demo1.pop();
}
System.out.println(demo1.min());
}
}

数据结构与算法:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

http://blog.gxitsky.com/2019/10/31/Programming-01-define-stack-min-element/

作者

光星

发布于

2019-10-31

更新于

2022-06-17

许可协议

评论