datastructs-alg/Stack.java at master · partheinstein/datastructs-alg · GitHub

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
public class Stack {
    class Item {
        int data;
        Item prev;
        Item nextMin;
    }

    Item head;
    Item min;

    public void push(int data) {
        Item t = new Item();
        t.data = data;
        t.prev = head;

        if (head == null) {
            min = t;
        }

        if (t.data < min.data) {
            t.nextMin = min;
            min = t;
        }

        head = t;
    }

    public Item pop() {
        if (head != null) {
            Item item = head;

            if (min == item) {
                min = item.nextMin;
                item.nextMin = null;
            }

            head = head.prev;
            return item;
        }
        return null;
    }

    public Item getMin() {
        return min;
    }

    public static void main(String[] args) {
        Stack s = new Stack();
        // s.push(1);
        // s.push(2);
        // System.out.println(s.pop().data);
        // System.out.println(s.pop().data);
        // System.out.println(s.pop());
        // s.push(3);
        // System.out.println(s.pop().data);

        s.push(2);
        s.push(3);
        s.push(1);
        s.push(4);

        System.out.println(s.getMin().data); //1
        s.pop(); // 4
        System.out.println(s.getMin().data); //1
        s.pop(); // 1
        System.out.println(s.getMin().data); //2
        s.pop(); // 3
        System.out.println(s.getMin().data); //2
        s.pop(); // 2
        System.out.println(s.getMin()); //null

        s.push(4);
        s.push(3);
        s.push(2);
        s.push(1);

        System.out.println(s.getMin().data); //1
        s.pop();
        System.out.println(s.getMin().data); //2
        s.pop();
        System.out.println(s.getMin().data); //3
        s.pop();
        System.out.println(s.getMin().data); //4
        s.pop();
        System.out.println(s.getMin()); //null


    }
}