算法初级——返回栈中最小元素

实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返 回栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。
/*
* 实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返 回栈中最小元素的操作。
* 两种实现方式
* mystack1:如果最小栈为空,压入最小栈,再来的元素判断是否小于当前最小,如果小于当前最小栈的栈顶元素,则压入最小栈,
* 每一步都压入数据栈,弹出栈时先判断数据栈是否为空,如果不为空,先弹出数据栈元素,同时记录,并与最小栈元素比较,
* 如果相等,同时弹出最小栈元素。
* mystack2:压栈操作 先判断最小栈是否为空,如果空,压入最小栈,否则判断当前元素和最小栈栈顶元素的大小,
* 如果小于栈顶元素,压入最小栈,否则,栈顶元素重新压入最小栈。
* 弹出操作 判断数据栈是否为空,如果不为空,先弹出最小栈栈顶元素,然后弹出数据栈元素。
*/

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
103
104
105
106
107
108
import java.util.Stack;
import javax.management.RuntimeErrorException;

public class Getmin {
   
    public static class Mystack1 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
       
        public Mystack1() {
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }
        //获取最小
        public int getmin() {
            if(this.stackMin.isEmpty()) {
                throw new RuntimeException("empty");
            }
            return this.stackMin.peek();
        }
        //压栈
        public void push(int newNum) {
            if(this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            }else if(newNum <= this.getmin()) {
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }
        //弹出
        public int pop() {
            if(this.stackData.isEmpty()) {
                throw new RuntimeException("empty");
            }
            int temp = this.stackData.pop();
            if(temp == this.getmin()) {
                this.stackMin.pop();
            }
            return temp;
        }
    }
   
    public static class Mystack2{
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
       
        public Mystack2() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }
        public int getmin() {
            if(this.stackMin.isEmpty()) {
                throw new RuntimeException("empty");
            }
            return this.stackMin.peek();
        }
       
        public void push(int newNum) {
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            }else if(newNum < this.getmin()) {
                this.stackMin.push(newNum);
            } else {
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }
            this.stackData.push(newNum);
        }
       
        public int pop() {
            if(this.stackData.isEmpty()) {
                throw new RuntimeException("empty");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }
       
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Mystack1 stack1 = new Mystack1();
        stack1.push(3);
        System.out.println(stack1.getmin());
        stack1.push(4);
        System.out.println(stack1.getmin());
        stack1.push(1);
        System.out.println(stack1.getmin());
        stack1.push(2);
        System.out.println(stack1.getmin());
        System.out.println(stack1.pop());
        System.out.println(stack1.getmin());

        System.out.println("=============");

        Mystack2 stack2 = new Mystack2();
        stack2.push(3);
        System.out.println(stack2.getmin());
        stack2.push(4);
        System.out.println(stack2.getmin());
        stack2.push(1);
        System.out.println(stack2.getmin());
        stack2.push(2);
        System.out.println(stack2.getmin());
        System.out.println(stack2.pop());
        System.out.println(stack2.getmin());
    }
}
0 条评论
发表一条评论