讲栈之前,要先讲一下Deque双端队列
- 既可以添加到队尾,也可以添加到队首
- 既可以从队首获取又可以从队尾获取
public interface Deque<E> extends Queue<E> {
}
我们可以看到Deque其实是扩展至Queue接口的
我们对比一下Deque和Queue的方法
Queue | Deque | |
---|---|---|
添加元素到队尾 | add(E e) / off(E e) | addLast(E e) / offerLast(E e) |
取队首元素并删除 | E remove() / E poll() | E removeFirst() / E pollFirst() |
取队首元素但不删除 | E element() / E peek() | E getFirst() / E peekFirst() |
Deque还有自己的方法
Deque | |
---|---|
添加元素到队首 | addFirst(E e) / offerFirst() |
取队尾元素并删除 | E removeLast() / E pollLast() |
取队尾元素但不删除 | E getLast() / E peekLast() |
Deque的实现类: ArrayDeque , LinkedList
Deque<Object> deque = new LinkedList<>();
deque.offerLast("end");
deque.offerFirst("3");
deque.offerFirst("2");
deque.offerFirst("1");
while (deque.size() > 0) {
System.out.println(deque.pollFirst());
}
运行结果
1
2
3
end
栈(Stack)是一种后进先出的数据结构
先进去的元素永远都在栈顶,所有它最后才会出来
有两个重要的方法
- push(E e):把元素压栈
- pop(E e): 把栈顶的元素“弹出”
用Deque可以实现Stack的功能
- push(E e) : addFirst(E e)
- pop() : removeFirst()
- peek() : peekFirst()
Java使用Deque实现栈的功能,注意只调用push / pop /peek,避免调用Deque的其它方法
不要使用遗留类Stack