标签：stackHead offer int day01 元素 最小值 复杂度 Stack

用两个栈实现队列

题目要求

思路

栈的特性是先进后出，而队列的特性是先进先出，用栈实现队列的话就需要一个辅助栈来逆置原来的栈序列。

代码

class CQueue {

    Stack<Integer> stackTail,stackHead;
    public CQueue() {
        stackTail = new Stack<Integer>();
        stackHead = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stackTail.push(value);
    }
    
    public int deleteHead() {
        int result=-1;
        if(stackHead.empty()){
            while(!stackTail.empty()){
                stackHead.push(stackTail.pop());
            }
        }
        if(!stackHead.empty()){
            result=(int)stackHead.pop();
        }
        return result;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

复杂度分析

空间复杂度

O(n),原始栈和辅助栈所用的空间大小。

时间复杂度

平均O(n),最好可达O(1),最坏可达O(n)。

反思不足

思路

在出队操作中，最开始是将栈中的所有元素入辅助栈，弹出栈顶元素后，再一次把所有元素压入原来的栈，每次出队操作都这样做。

当时这么想的目的是为了维持顺序不变。

后来发现没必要这样做，将辅助栈的元素全部都出队后再加入后入队的新元素同样可以达到该目的。

java se

对Stack类的有关api不熟悉

包含min函数的栈

题目要求

思路

相对于传统栈主要在于增加了min函数。

由于栈只能栈顶删除元素或增加元素，所以根据栈顶可以唯一确定当前的最小值，因为无法对栈顶之外的元素进行操作，于是可以通过建立起一个与栈顶变化相对应的最小值序列。那为什么选择栈这一数据结构来实现这个序列呢，因为这个序列的变化在原始栈入栈时在末尾追加元素，在原始栈出栈时，在末尾删除元素。

代码

class MinStack {

    Stack <Integer> stack,minStack;
    int min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new<Integer> Stack();
        minStack=new<Integer>Stack();
    }
    
    public void push(int x) {
        if(stack.empty()){
            min=x;
        }else if(x<=min){
            min=x;
        }
        stack.push(x);
        minStack.push(min);
    }
    
    public void pop() {
        
        if(!stack.empty()){
            stack.pop();
            minStack.pop();
            min=min();
        }
            
    }
    
    public int top() {
        if(!stack.empty())
            return stack.peek();

        return -1;
    }
    
    public int min() {
        if(!minStack.empty()){
            return minStack.peek();
        }
        return -1;

    }
}

/**
 * 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();
 */

复杂度分析

空间复杂度

最坏O(n),连续入栈n个元素

时间复杂度

均为O(1)

反思不足

思路

最开始想的是在插入元素时实时的更新最小值就可以了，于是采用了一个整型变量来记录最小值。

此时没有考虑到出栈对最小值的影响。

后面又想到用一个变量来记录上一个最小值，如果出栈元素刚好是最小值，那么就将最小值更新为上一个最小值。

此时没有考虑到可能有重复的最小值元素。而且如果一直出栈的话，上一个最小值如何更新？

看了题解才知道可以构建一个随着出栈、入栈而变化的最小值序列。

标签：stackHead,offer,int,day01,元素,最小值,复杂度,Stack
From： https://www.cnblogs.com/zhouj-learn/p/16759796.html