java堆栈内存是如何实现的?

TheDisguiser 2020-09-03 21:58:30 java常见问答 7133

堆栈是java永远逃不过的问题之一,java靠着它们存储着各种对象及其他,下面我们来了解下它们要如何实现。

堆的实现

/*
 * 自己实现的ArrayList可以通过在两个data元素集合是实现swap的操作,
 * 而如果调用已经实现的ArrayList则可以使用工具类Collections.swap() ;
 */
/**
 * 堆的在下标设置时使用shiftUp时使用index=0 ;这是跟数组有关,
 * 便于统一操作
 */
import java.util.ArrayList;
import java.util.Collections;
public class MaxHeap < E extends Comparable < E > >
{
    private ArrayList < E > list;
    public MaxHeap()
    {
        list = new ArrayList < E > ();
    }
    private int parent(int i)
    {
        return (i - 1) / 2;
    }
    private int leftChild(int i)
    {
        return i * 2 + 1;
    }
    private int rightChild(int i)
    {
        return i * 2 + 2;
    }
    private void siftUp(int k)
    {
        while (k > 0 && list.get(k)
            .compareTo(list.get(parent(k))) > 0)
        {
            //            swap(parent(k) , k) ;
            Collections.swap(list, k, parent(k));
            k = parent(k);
        }
    }
    public void add(E e)
    {
        list.add(list.size(), e);
        siftUp(list.size() - 1);
    }
    public E getFront()
    {
        return list.get(0);
    }
    private void siftDown(int k)
    {
        while (leftChild(k) < list.size())
        {
            int j;
            j = leftChild(k);
            if (j + 1 < list.size() && list.get(j)
                .compareTo(list.get(j + 1)) < 0)
            {
                j = rightChild(k);
            }
            if (list.get(k)
                .compareTo(list.get(j)) < 0)
            {
                Collections.swap(list, k, j);
            }
            else
            {
                break;
            }
            k = j;
        }
    }
    public E extractMax()
    {
        if (list.size() == 0)
        {
            throw new IllegalArgumentException("Exception");
        }
        E retMax = list.get(0);
        Collections.swap(list, 0, list.size() - 1);
        list.remove(list.size() - 1);
        siftDown(0);
        return retMax;
    }
    public boolean isEmpty()
    {
        return list.size() == 0;
    }
    public int getSize()
    {
        return list.size();
    }
    public static void main(String[] args)
    {
        MaxHeap < Integer > maxHeap = new MaxHeap < > ();
        maxHeap.add(123);
        maxHeap.add(99);
        maxHeap.add(666);
        maxHeap.add(78);
        maxHeap.add(999);
        System.out.println("获取最大元素" + maxHeap.getFront());
        int n = maxHeap.getSize();
        for (int i = 0; i < n - 1; i++)
        {
            System.out.println("删除第" + i + "个元素:" + maxHeap.extractMax());
        }
        System.out.println("获取最大元素" + maxHeap.getFront());
    }
}

栈中基于链表实现

package Algorithm.learn;
/**
 * Created by liujinhong on 2017/3/7.
 */
class Node < E >
{
    Node < E > next = null;
    E data;
    public Node(E data)
    {
        this.data = data;
    }
}
public class ListStack < E >
{
    Node < E > top = null;
    boolean isEmpty()
    {
        return top == null;
    }
    public void push(E item)
    {
        Node < E > node = new Node < E > (item);
        node.next = top;
        top = node;
    }
    public E pop()
    {
        if (this.isEmpty()) return null;
        E data = top.data;
        top = top.next;
        return data;
    }
    public E peek()
    {
        if (this.isEmpty()) return null;
        return top.data;
    }
    public static void main(String[] args)
    {
        ListStack < Integer > stack = new ListStack < > ();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

以上就是本篇文章的所有内容,想知道更多java入门知识的小伙伴们请一定记得关注我们了解详情。

推荐阅读:

java栈存放什么?java堆存放什么?

java堆排序代码,堆排序实现

堆排序优点是什么?堆排序缺点又是什么?