Java implemented by self-designed data structure (linked list)


  • 0
    J

    Use a double linked list to implement a min stack. Head pointer is to create a new element and add it to list, meanwhile top pointer is to keep the top of the stack (end of the list).

    public class MinStack {
    /** initialize your data structure here. */
    private class StackStruct {
    StackStruct next;
    StackStruct prev;
    int val;
    int min;

        public StackStruct (int val, int min, StackStruct prev) {
            this.val = val;
            this.min = min;
            next = null;
            this.prev = prev;
        }
    }
    
    private final StackStruct root;
    private StackStruct head;
    private StackStruct top;
    private int minValue;
    private int size;
    
    public MinStack() {
        size = 0;
        minValue = Integer.MAX_VALUE;
        
        head = new StackStruct(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
        root = head;
        
        head = head.next;
        top = root;
    }
    
    public void push(int x) {
        size++;
        
        minValue = (x < minValue) ? x : minValue;
        
        head = new StackStruct(x, minValue, top);
        top = head;
        head = head.next;
    }
    
    public void pop() {
        if (--size <= 0) {
            minValue = Integer.MAX_VALUE;
            return;
        }
        
        top = top.prev;
        minValue = top.min;
        top.next = null;
        head = top.next;
    }
    
    public int top() {
        return top.val;
    }
    
    public int getMin() {
        return top.min;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.