堆栈是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入门知识的小伙伴们请一定记得关注我们了解详情。
推荐阅读：