Fork me on GitHub

算法之美-用两个X实现一个Y

对于经典面试题:“两个栈实现队列”和“两个队列实现栈”,应该怎么考虑呢?

两个栈实现队列

思路: 利用inStack作为进队的缓存。出队时,因为考虑到“先进先出”,可以利用另一个栈outStack转存当前的缓存。出队时,为了保证再入队依旧满足规律,若outStack为空,先全部倒入outStack;若不为空,则outStack直接出栈。

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
private Stack<Integer> inStack = new Stack<>();
private Stack<Integer> outStack = new Stack<>();
void push(Integer in){
inStack.push(in);
}
Integer pop() throws Exception {
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
if(outStack.isEmpty()){
throw new Exception("no data");
}
return outStack.pop();
}

public static void main(String[] args) throws Exception {
Solution9 test = new Solution9();
test.push(8);
test.push(9);
test.push(99);
System.out.println(test.pop());
test.push(999);
}

两个队列实现栈

思路: 利用一个队存储,另一个队作为缓存。当出栈时,让非空的队列先出队n-1,最后剩下的一个出队则完成了栈的“先入先出”的功能。

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
LinkedList<Integer> queue1=new LinkedList<Integer>();  
LinkedList<Integer> queue2=new LinkedList<Integer>();
public void push(int value)//入栈
{
queue1.addLast(value);
}

public int pop()//出栈 必须是非空的栈才能出栈啊
{
if(sSize()!=0)//栈不为空
{
//移动一个队的n-1个到另一个中
if(!queue1.isEmpty())//q1 空
{
putN_1ToAnthor();
return queue1.removeFirst();
}
else //q2 空
{
putN_1ToAnthor();
return queue2.removeFirst();
}
}
else {
System.out.println("栈已经为空啦,不能出栈");
return -1;
}
}

public int sSize()
{
return queue1.size()+queue2.size();
}

public void putN_1ToAnthor()//从非空中出队n-1个到另一个队列 因为队列总是一空一非空
{
if(!queue1.isEmpty())
{
while(queue1.size()>1)
{
queue2.addLast(queue1.removeFirst());
}
}
else if(!queue2.isEmpty())
{
while(queue2.size()>1)
{
queue1.addLast(queue2.removeFirst());
}
}
}

其他类似题目(更新中。。)

包含 min 函数的栈

题目描述:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

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
    private Stack<Integer> datastack = new Stack<>();
private Stack<Integer> minstack = new Stack<>();


public void push(int node) {
datastack.push(node);
// if(minstack.isEmpty()){
// minstack.push(node);
// }else{
// if(minstack.peek()<node){
// minstack.push(minstack.peek());
// }else{
// minstack.push(node);
// }
// }
//注意minstack栈顶始终存储的当前栈的最小值,且长度和datastack一样
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}
public void pop() {
datastack.pop();
minstack.pop();//注意这里

}

public int top() {
return datastack.peek();
}

public int min() {
return minstack.peek();
}

数据流中的中位数

题目描述:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

两个栈实现:

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
//用两个栈实现的
Stack<Integer> min = new Stack<>();
Stack<Integer> max = new Stack<>();
int number = 0;
public void Insert(Integer num) {

number++;
if(min.size() == 0 && (max.size() == 0 || num <= max.peek())){
min.push(num);
return;
}
if(max.size() == 0 && (min.size() == 0 || num >= min.peek())){
max.push(num);
return;
}
if(num > max.peek()){
while(max.size() != 0 && num>max.peek()){
min.push(max.pop());
}
}
if(num < min.peek()){
while( min.size() != 0&& num<min.peek() ){
max.push(min.pop());
}
}
min.push(num);
}

public Double GetMedian() {
while(min.size()<number/2){
min.push(max.pop());
}
while(min.size()>number/2){
max.push(min.pop());
}
if(number%2==0){
return (min.peek()+max.peek())/2.0;
}
else{
return (double)max.peek();
}
}

两个大根堆实现:

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
    //用堆实现的
/* 大顶堆,存储左半边元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小顶堆,存储右半边元素,并且右半边元素都大于左半边 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 当前数据流读入的元素个数 */
private int N = 0;
public void Insert2(Integer val) {
/* 插入要保证两个堆存于平衡状态 */
if (N % 2 == 0) {
/* N 为偶数的情况下插入到右半边。
* 因为右半边元素都要大于左半边,但是新插入的元素不一定比左半边元素
来的大,
* 因此需要先将元素插入左半边,然后利用左半边为大顶堆的特点,取出堆
顶元素即为最大元素,此时插入右半边 */
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
} N
++;
}
public Double GetMedian2() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
-------------本文结束感谢阅读-------------