【剑指offer-Java版】21包含min函数的栈

一时失言乱红尘 2022-08-21 09:40 7阅读 0赞

包含min操作的栈：在基本栈基础上提供一个Min功能，可以取得当前栈的最小值

重点在于思路，拿空间换取了Min的功能，申请一个等量空间的辅助栈用于存取栈中的最小元素

public class _Q21 extends MyStack<Integer> {
    
        private MyStack<Integer> dataStack = new MyStack<>();
        private MyStack<Integer> minStack = new MyStack<>();
    
        @Override
        public Integer pop() { // 栈空的处理在父类中已经实现
            minStack.pop(); 
            return dataStack.pop();
        }
    
        @Override
        public void push(Integer data) {
            // 插入的第一个元素-直接插入，毕竟此时minStack.head是空的
            if(minStack.head == null) {
                minStack.push(data);
            }
    
            if(data < minStack.head.data){
                minStack.push(data);
            }else {
                minStack.push(minStack.head.data);
            }
    
            dataStack.push(data);
        }
    
        public Integer min(){
            if(minStack.len == 0) return null;
            return minStack.head.data;
        }
    
        }
    
        /* Q21 中的栈 ,使用了一个链表实现 */
        public class MyStack<T> {
    
        public StackNode<T> head;
        public int len;
    
        public void push(T data){
            StackNode<T> node = new StackNode<T>();
            node.data = data;
            node.nextNode = head;
            head = node;
            len++;
        }
    
        public T pop(){
            if(len == 0) return null;
    
            StackNode<T> node = head;
            head = head.nextNode;
            len--;
    
            return node.data;
        }
        }

测试代码：

public class _Q21Test extends TestCase {
        
    
        _Q21 stackWithMin = new _Q21();
    
        // 3 4 2 5  -- 3 3 2 2
        // 3 4 2    -- 3 3 2
        // 3 4 2 3  -- 3 3 2 2
        public void test(){
            stackWithMin.push(3);
            stackWithMin.push(4);
            stackWithMin.push(2);
            stackWithMin.push(5);
            stackWithMin.pop();
            stackWithMin.push(3);
    
            System.out.println(stackWithMin.min());
        }
        }