【剑指offer第一天】栈与队列

朴灿烈づ我的快乐病毒、 2022-09-03 05:12 17阅读 0赞

### 第一题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]  
用两个栈实现队列，其中栈A负责入队操作，每次将元素加入到栈顶。栈B负责出队操作，将栈A中的数字反向存入，先入栈的数字存到栈顶然后出队操作。

class MinStack { 
        Stack<Integer> A,B;
        /** initialize your data structure here. */
        public MinStack() { 
            A = new Stack<>();
            B = new Stack<>();
        }
        
        public void push(int x) { 
            //push方法返回
            A.push(x);
            if(B.isEmpty()||B.peek()>=x){ 
                B.push(x);
            }
        }
    
        public void pop() { 
            if(A.pop().equals(B.peek())){ 
                B.pop();
            }
        }
        
        public int top() { 
            return A.peek();
        }
        
        public int min() { 
            return B.peek();
        }
    }
    
    /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); */

另：现不推荐使用Stack类，[Stack 是 JDK 1.0 的产物。它继承自 Vector][Stack _ JDK 1.0 _ Vector]，

> Java 提供了 Deuqe。Deque 是继承自 Queue，而 Stack 是继承自 Vector。Java 中的  
> Deuqe，即“double ended queue”的缩写，是 Java 中的双端队列集合类型。Deque 具备普通队列 FIFO  
> 的功能，同时它也具备了 Stack 的 LIFO 功能，并且保留了 push 和 pop 函数。

附官方题解：

class CQueue { 
        Deque<Integer> stack1;
        Deque<Integer> stack2;
        
        public CQueue() { 
            stack1 = new LinkedList<Integer>();
            stack2 = new LinkedList<Integer>();
        }
        
        public void appendTail(int value) { 
            stack1.push(value);
        }
        
        public int deleteHead() { 
            // 如果第二个栈为空
            if (stack2.isEmpty()) { 
                while (!stack1.isEmpty()) { 
                    stack2.push(stack1.pop());
                }
            } 
            if (stack2.isEmpty()) { 
                return -1;
            } else { 
                int deleteItem = stack2.pop();
                return deleteItem;
            }
        }
    }

### 第二题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]  
对栈A来说需要完成常规的push,pop,top操作，使用辅助栈B记录最小值，在插入数据时需要比较B的栈顶元素和插入元素数值大小以及B是否为空（为空则直接插入）。

> Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替 == 来比较值是否相等。使用==则比较的是引用地址

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/65b8af492b1b47ff8af2bb936990238c.png
[Stack _ JDK 1.0 _ Vector]: https://blog.csdn.net/fall_hat/article/details/106470006
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/33a972de6ee04359b0ed9cdf425efb9e.png