Java剑指offer

第一天

1.使用双栈实现队列操作
题目要求:用两个栈实现一个双向队列，包含队列的插入(appendTail)以及删除(deleteHead),若队列中没有元素就返回-1.

思路分析:维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作

成员变量

• 维护两个栈 stack1 和 stack2，其中 stack1 支持插入操作，stack2 支持删除操作
  构造方法

• 初始化 stack1 和 stack2 为空
  插入元素

• stack1 直接插入元素
  删除元素

• 如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里
• 如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回

复杂度分析

时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)O(1)。插入不多说，对于删除操作，虽然看起来是 O(n)O(n) 的时间复杂度，但是只是进行第一个栈进入第二个栈的操作，之后直接弹出，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)O(1)。

空间复杂度：O(n)O(n)。需要使用两个栈存储已有的元素

代码实现：

package com.sordfingeroffer;

import java.util.Deque;
import java.util.LinkedList;

public class CQueue {
    //使用Deque做堆栈而不是stack，因为stack的方法是同步的
    //Deque接口做堆栈实现的方法:push()、pop()、peek()(返回的是开头的元素)
    Deque <Integer> stack1;
    Deque <Integer> stack2;


    public CQueue()
    {
        //LinkedList实现了Deque和list的接口
        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
            return stack2.pop();
    }

    public static void main(String[] args) {
        CQueue q=new CQueue();
        q.appendTail(10);

        q.appendTail(20);
        q.appendTail(30);

        int param1=q.deleteHead();
        int param2=q.deleteHead();
        int param3=q.deleteHead();

        System.out.println(param1);
        System.out.println(param2);
        System.out.println(param3);

    }
}

2.包含Min的栈
题目要求：定义一个栈结构(pop、push、top基本操作)并且添加一个min函数，能够返回栈中最小的元素

普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)，所以我们需要建立一个辅助栈来降低复杂度

• stack1:存储所有的元素，包括pop()、push()基本操作以及top()操作，保持题目正常逻辑

• stack2:只是与min相关，里面的内容不必要遵循栈的基本操作，min()返回的是栈顶元素

函数设计:

• push():stack1正常push，stack2的栈顶要与Push的值进行比较，把小的那个push进入stack2中(以便到时候pop出来的时候可以得到最小的值)

• pop():stack1正常pop,若stack1中pop的值和stack2中的栈顶的值相同就pop，这就意味着将stack1中最小的元素pop出去了，所以stack2要进行同步pop

• min():只需要返回stack2中的栈顶元素即可

代码实现:

package com.sordfingeroffer;

import java.util.Stack;

public class MiniStack {
    //stack类是vector的子类，标准的后进先出的栈
    //方法有:boolean empty()、Object peek( )、Object pop( )、Object push(Object element)、int search(Object element)-->查找对象在指定位置的值
    Stack <Integer> stack1,stack2;
    /** initialize your data structure here. */
    public MiniStack() {
        stack1=new Stack<Integer>();
        stack2=new Stack<Integer>();
    }

    public void push(int x)
    {
        stack1.push(x);
        if(stack2.isEmpty() || stack2.peek()>=x)
        {
            stack2.push(x);
        }
    }

    public void pop()
    {
        if(stack1.pop().equals(stack2.peek()))
        {
            stack2.pop();
        }
    }

    public int top() {
        return stack1.peek();
    }

    public int min() {
        return stack2.peek();
    }

    public static void main(String[] args) {
        MiniStack minStack = new MiniStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.min());
    }

}