包含min函数的栈(思路和实现)

KLQ 2020-04-28 14:27:56 java常见问答 6134

下面要给大家带来的是和包含min函数的栈实例相关的内容,具体包括了三种思路和代码实现方式,一起来了解一下吧。

题目:

定义栈的数据结构,请在这个类型中实现一个可以得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

注:

保证测试当中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。

思路1

代码实现:

import java.util.Stack;
public class Solution
{
    Stack < Integer > dataStack = new Stack < Integer > ();
    Stack < Integer > minStack = new Stack < Integer > ();
    public void push(int node)
    {
        dataStack.push(node);
        if (minStack.isEmpty() || node < minStack.peek())
        {
            minStack.push(node);
        }
        else
        {
            minStack.push(minStack.peek());
        }
    }
    public void pop()
    {
        dataStack.pop();
        minStack.pop();
    }
    public int top()
    {
        return dataStack.peek();
    }
    public int min()
    {
        return minStack.peek();
    }
}

思路2:

ArrayList实现

代码实现:

import java.util.ArrayList;
public class Solution
{
    ArrayList < Integer > list = new ArrayList < Integer > ();
    public void push(int node)
    {
        list.add(0, node);
    }
    public void pop()
    {
        list.get(0);
        list.remove(0);
    }
    public int top()
    {
        return list.get(0)
            .intValue();
    }
    public int min()
    {
        int temp = top();
        for (int i = 1; i < list.size(); i++)
        {
            if (temp > list.get(i)
                .intValue())
            {
                temp = list.get(i)
                    .intValue();
            }
        }
        return temp;
    }
}

思路3

代码实现:

import java.util.Stack;
import java.util.Arrays;
public class Solution {
/*借用辅助栈存储min的大小,自定义了栈结构
*/
    private int size;
    private int min = Integer.MAX_VALUE;
    private Stack
<Integer> minStack = new Stack
    <Integer>();
    private Integer[] elements = new Integer[10];
    public void push(int node) {
        ensureCapacity(size+1);
        elements[size++] = node;
        if(node <= min){
            minStack.push(node);
            min = minStack.peek();
        }else{
            minStack.push(min);
        }
    //    System.out.println(min+"");
    }
 
    private void ensureCapacity(int size) {
        // TODO Auto-generated method stub
        int len = elements.length;
        if(size > len){
            int newLen = (len*3)/2+1; //每次扩容方式
            elements = Arrays.copyOf(elements, newLen);
        }
    }
    public void pop() {
        Integer top = top();
        if(top != null){
            elements[size-1] = (Integer) null;
        }
        size--;
        minStack.pop();    
        min = minStack.peek();
    //    System.out.println(min+"");
    }
 
    public int top() {
        if(!empty()){
            if(size-1>=0)
                return elements[size-1];
        }
        return (Integer) null;
    }
    public boolean empty(){
        return size == 0;
    }
 
    public int min() {
        return min;
    }
}

以上的三种思路和代码实现你都了解了吗?可以参考一下实操呢。更多java实例,可以继续关注本站了解哦。