0111栈与队列Day1-创新互联

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

class CQueue {

    public CQueue() {

    }
    
    public void appendTail(int value) {

    }
    
    public int deleteHead() {

    }
}

栈实现队列的出队操作效率低下：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。

列表倒序操作可使用双栈实现：设有含三个元素的栈 A = [1,2,3] 和空栈 B = [] 。若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1] ，即栈 B 元素为栈 A 元素倒序。

利用栈 B 删除队首元素：倒序后，B 执行出栈则相当于删除了 A 的栈底元素，即对应队首元素。

函数设计：
加入队尾 appendTail() ： 将数字 val 加入栈 A 即可。
删除队首deleteHead() ： 有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1 。
否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

代码如下：

class CQueue {
    LinkedListA, B;
    public CQueue() {
        A = new LinkedList();
        B = new LinkedList();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   -->返回 -3.
minStack.pop();
minStack.top();      -->返回 0.
minStack.min();   -->返回 -2.

class MinStack {

    public MinStack() {

    }
    
    public void push(int x) {

    }
    
    public void pop() {

    }
    
    public int top() {

    }
    
    public int min() {

    }
}

普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)O(N) 。

本题难点： 将 min() 函数复杂度降为 O(1)O(1) 。可借助辅助栈实现：

数据栈 A ： 栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 B ： 栈 B 中存储栈 A 中所有 非严格降序 元素的子序列，则栈 A 中的最小元素始终对应栈 B 的栈顶元素。此时， min() 函数只需返回栈 B 的栈顶元素即可。

函数设计：
push(x) 函数： 重点为保持栈 B 的元素是 非严格降序 的；

执行「元素 x 压入栈 A」 ；
若「栈 B 为空」或「x ≤ 栈 B 的栈顶元素」，则执行「元素 x 压入栈 B」 ；
pop() 函数： 重点为保持栈 A , B 的 元素一致性 ；

执行「栈 A 元素出栈」，将出栈元素记为 y ；
若 「y 等于栈 B 的栈顶元素」，则执行「栈 B 元素出栈」；
top() 函数： 直接返回栈 A 的栈顶元素，即返回 A.peek() ；

min() 函数： 直接返回栈 B 的栈顶元素，即返回 B.peek() ；

采用 “非严格” 降序原因：

在栈 A具有 重复 最小值元素时，非严格降序可防止栈 B提前弹出最小值元素，示例如下：

代码如下：

注：Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals()代替 ==，以比较对象的值。 

class MinStack {
    StackA, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧