栈---四题

一、 使用递归函数和栈操作，逆序一个栈

思路：需要设计两个递归函数
递归函数一：将栈stack的栈底元素返回并移除。
递归函数二：逆序一个栈，并调用递归函数一。

import java.util.Scanner;
import java.util.Stack;


/**
 * @author zhengban
 *
 */

public class MyStack1{

    //递归函数一：将栈stack的栈底元素返回并移除。
    public static int getLast(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.empty()){
            return result;
        }else{
            int last = getLast(stack);
            return last;
        }

    }
    //递归函数二：逆序一个栈，并调用递归函数一。
    public static void reverse(Stack<Integer> stack){
        if(stack.empty()){
            return;
        }
        int i = getLast(stack);
        reverse(stack);
        stack.push(i);
    }


}
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

二、用两个栈来实现一个队列，完成队列的offer和Poll操作。 队列中的元素为int类型。

思路：一个栈作为压入栈stack1，一个作为弹出栈stack2。
需要注意的点：
1、如果stack1要往stack2中压入数据，必须以一次性把数据全部压入；
2、如果stack2不为空，stack1 绝对不能向stack2中压入数据。

import java.util.Stack;
public class MyStack2{
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void offer(int node) {
        stack1.push(node);
    }

    public int poll() {
        if(stack1.empty() && stack2.empty()){
            throw new RuntimeException("Queue is empty");
        }else if(stack2.empty()){
            while(!stack1.empty())
            stack2.push(stack1.pop());
        }
        return stack2.pop();

    }
    public int peek() {
        if(stack1.empty() && stack2.empty()){
            throw new RuntimeException("Queue is empty");
        }else if(stack2.empty()){
            while(!stack1.empty())
            stack2.push(stack1.pop());
        }
        return stack2.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
30

三、输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

….

依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

import java.util.ArrayList;
import java.util.Stack;


public class MyStack3{
    public boolean IsPopOrder(int [] pushA,int [] popA) {

        if(pushA.length == 0 || popA.length == 0)
            return false;

        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.empty() && stack.peek()==popA[index]){
                stack.pop();
                index++;    
            }
        }
            return stack.empty();
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

解法一思路：迭代器

解法一：
import java.util.Iterator;
import java.util.Stack;

public class MyStack{

    Stack<Integer> stack = new Stack<Integer>();

    public void push(int node) {
        stack.push(node);
    }

    public void pop() {
        stack.pop();
    }

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

    public int min() {
        int min  = stack.peek();
        Iterator<Integer> it = stack.iterator();
        while(it.hasNext()){
            int tep = it.next();
            if(tep<min){
                min = tep;
            }   
        }
        return 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

解法二思路：设计两个栈，一个栈保存当前栈中的元素stack，另一个栈用来保存每一步的最小值stackmin。
push（）：
1、假设当前值为node，先将其压入stack，
2、然后判断stackmin是否为空，如果为空，则将node也压入stackmin；如果不为空，则将node与stackmin的栈顶元素比较。
3、如果node<=stackmin.peek（），则将node压入stackmin，node变成当前stackmin的栈顶元素；
如果node>stackmin.peek（）,则将stackmin.peek（）重复压入stackmin一次。
pop（）：弹出stack的数据，弹出stackmin的数据；
min（）：stackmin栈顶元素始终是当前stack中的最小值。

解法二：
import java.util.Stack;

public class MyStack4{
        //使用两个栈。一个用来保存当前栈中的元素，一种保存每一步最小值。
        Stack<Integer> stack= new Stack<Integer>();
        Stack<Integer> stackmin= new Stack<Integer>();

    public void push(int node) {
        stack.push(node);//将当前数据压入stack
        if(stackmin.empty()){
            stackmin.push(node);//若stackmin为空，也将当前数据压入stackmin
        }else if(node<min()){
            stackmin.push(node);//若stackmin不为空，将当前数据与min比较
        }else{
            int newmin = stackmin.peek();
            //如果node>stackmin.peek（）,则将stackmin.peek（）重复压入stackmin一次。
            //也可以不重复压入，如果不重复压入，在出栈时需要加上判断，否则出错。
            stackmin.push(newmin);
        }
    }

    public void pop() {
        if(stack.empty()){
            throw new RuntimeException("empty");
        }
        stackmin.pop();
        stack.pop();
    }

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

    public int min() {
        if(stack.empty()){
            throw new RuntimeException("empty");
        }
        return stackmin.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
30
31
32
33
34
35
36
37
38
39
40
41