栈
Java中有Stack类,但现在已经过时了,不推荐使用。一个更好的方法是使用Deque接口实现栈(Deque意为双端队列,double ended queue)。具体来说又有ArrayDeuqe和LinkedList两种具体类来实现,两者的区别体现在底层分别使用数组和链表来实现。
常用的重要函数包括:
push(); // 向stack栈顶压入一个元素
pop(); // 从stack中弹出栈顶元素
peek(); // 查看stack中栈顶元素,不弹出
1 2 3 4 5 6 7 8 9 10 11
| Deque<Integer> stack = new LinkedList<>();
stack.push(1); stack.push(2); stack.push(3);
while(!stack.isEmpty()) { System.out.println(stack.pop()); }
|
队列
使用Queue接口实现,具体的实现类有LinkedList。
常用的重要函数包括:
向队列尾部添加元素:
offer(); // 如果因为长度不够等原因插入失败,返回false
add(); // 如果插入失败会抛出异常:IllegalStateException;
查看头部元素 ,不改变队列:
peek(); // 如果队列中没有元素,返回null;
element(); // 如果队列中没有元素,则抛出异常:NoSuchElementException;
取出队首元素(返回队首元素,队列中不再包含此元素):
poll(); // 会在没元素时返回null;
remove(); // 会在没元素时抛出异常:NoSuchElementException;
1 2 3 4 5 6 7 8 9 10
| Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); while (!queue.isEmpty()) { System.out.println(queue.poll()); }
|
小根堆
PriorityQueue类实现了优先队列,默认是一个小根堆的形式,如果要定义大根堆,需要在初始化的时候加入一个自定义的比较器。
1 2 3 4 5 6 7 8 9 10 11 12 13
|
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.offer(5); minHeap.offer(3); minHeap.offer(4); minHeap.offer(1); minHeap.offer(2);
while(!minHeap.isEmpty()) { System.out.println(minHeap.poll()); }
|
大根堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
class maxComparator implements Comparator<Integer> { @Override public int compare(Integer num1, Integer num2) { return num1 >= num2 ? -1 : 1; } }
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new maxComparator()); maxHeap.offer(5); maxHeap.offer(3); maxHeap.offer(4); maxHeap.offer(1); maxHeap.offer(2);
while(!maxHeap.isEmpty()) { System.out.println(maxHeap.poll()); }
|
请我一杯咖啡吧!
微信打赏