栈和队列

发表于 分类于 ， 本文字数： 1.9k

栈

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接口实现stack
 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接口实现queue
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 实现heap
// minHeap：PriorityQueue默认实现小根堆
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
// maxHeap
// 自定义比较器：当compare函数中第一个参数（这里是较大的元素）需要排在前面时，返回一个负数；反之返回一个正数。
class maxComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer num1, Integer num2) {
        return num1 >= num2 ? -1 : 1;
    }
}

// 初始化PriorityQueue的时候new一个自定义比较器的对象
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());
}

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏