第一天——栈和队列

剑指 Offer 09. 用两个栈实现队列

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

public class CQueue {

    public Stack<int> stackIn;
    public Stack<int> stackOut;

    public CQueue() {
        stackIn = new Stack<int>();
        stackOut = new Stack<int>();
    }
    
    public void AppendTail(int value) {
        stackIn.Push(value);
    }
    
    public int DeleteHead() {
        if(stackOut.Count == 0 && stackIn.Count != 0)
        {
            while(stackIn.Count != 0)
            {
                stackOut.Push(stackIn.Pop());
            }
        }

        if(stackOut.Count == 0)
        {
            return -1;
        }
        else
        {
            int deleteItem = stackOut.Pop();
            return deleteItem;
        }
        return -1;
    }
}

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

一个栈只负责进,一个栈只负责删除

添加元素自然不用说,直接push

主要是删除元素的时候要分两种情况来考虑

不管两个栈的情况,总之先把进栈的元素塞进出栈里

直接接着判断判断出栈是不是还是空

出栈还是空的话很显然进栈没有元素,所以返回-1

不是空就在出栈删除元素,就相当于删除队列头


剑指 Offer 30. 包含min函数的栈

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

public class MinStack {

    public Stack<int> stack;
    public Stack<int> findMin;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<int>(); 
        findMin = new Stack<int>();
    }
    
    public void Push(int x) {
        stack.Push(x);
        if(findMin.Count == 0 || findMin.Peek() >= x)
        {
            findMin.Push(x);
        }
    }
    
    public void Pop() {
        if(stack.Peek() == findMin.Peek())
        {
            findMin.Pop();
        }
        stack.Pop();
    }
    
    public int Top() {
        if(stack.Count > 0)return stack.Peek();
        return -1;
    }
    
    public int Min() {
        if(findMin.Count > 0)return findMin.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(1)

所以直接把转成数组然后排序的方法毙掉了

得想个好的办法来避开使用循环

所以就得在进栈的时候下功夫

我一开始的想法是int了一个常量来存放最小值

但这样比较在出栈的时候就有问题了

你不知道会不会有重复的最小值

所以最合适的方法就是建立一个辅助的栈专门存放最小值

我们分为进栈和出栈两部分来讲:

进栈:

如果最小栈不是空的,或者新进栈的元素比最小栈已经比有的元素还要小

又或者新进栈的元素等于最小栈已经有的元素

那么就把元素放进最小栈

出栈:

出栈的时候与最小栈的元素比较,如果相等最小栈也出栈

这样如果出现了重复值,因为最小栈也会有重复值

出栈的时候就不会有问题了

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注