栈和队列(Java实现)
栈
栈(Stack):栈是先进后出(FILO, First In Last Out)的数据结构。Java中实现栈有以下两种方式:
- stack类
- LinkedList实现(继承了Deque接口)
(1) Stack实现
由于Stack底层是使用Vector的,而Vector支持线程同步,所以整体性能相对较低,如果没有多线程的场景,不建议使用Stack。
stack类图为:
举例:
//栈的实现一,内置类
//底层实现: Vector class Stack<E> extends Vector<E>
//由于Vector支持线程同步,所以效率比较低
Stack<Integer> stack = new Stack<>();
stack.push(1); //插入元素
stack.pop(); //弹出栈顶元素
stack.peek(); //查看栈顶元素
int n = stack.size(); //栈的大小
System.out.println(stack.isEmpty()); //判断栈是否为空
(2)LinkedList实现
LinkedList实现了List,Deque(实现了Queue接口)的接口,底层是双向链表实现的,所以不仅可以表示栈,也可以表示队列。
举例:
//栈的实现二:LinkedList
/*LinkedList底层实现了Deque双端队列的接口,双端队列,完全可以实现栈的功能
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>,
*/
Deque<Integer> stack2 = new LinkedList<>();
stack2.push(1); //插入元素
stack2.push(2); //插入元素
// stack2.offer(3); //offer和push都可以插入元素,但是push是队尾插入,offer是队首
System.out.println(stack2);
int m = stack2.peek(); //取栈顶元素,peek是2
System.out.println(m); //结果为2
m = stack2.getFirst(); //取栈顶第一个元素
System.out.println(m); //结果为2
stack2.pop(); //删除栈顶元素
队列
(1)使用LinkedList实现队列
底层是链表
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 添加元素到队列尾部
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 获取队列头部元素并删除
int head = queue.poll();
System.out.println("Head of the queue: " + head);
// 获取队列头部元素但不删除
int peek = queue.peek();
System.out.println("Peek of the queue: " + peek);
// 遍历队列中的元素
System.out.println("Elements in the queue: ");
for (Integer element : queue) {
System.out.println(element);
}
}
}
(2)使用ArrayDeque实现队列
底层是数组实现
public static void main(String[] args) {
//使用ArrayQueue实现队列
Queue<Integer> queue = new ArrayDeque<>();
// 添加元素到队列尾部
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 获取队列头部元素并删除
int head = queue.poll();
System.out.println("Head of the queue: " + head);
// 获取队列头部元素但不删除
int peek = queue.peek();
System.out.println("Peek of the queue: " + peek);
// 遍历队列中的元素
System.out.println("Elements in the queue: ");
for (Integer element : queue) {
System.out.println(element);
}
}
(3)双端队列
Deque(双端队列)是一种具有队列和栈的特性的数据结构,它允许在队列的头部和尾部进行元素的插入和删除操作。在Java中,Deque接口提供了对双端队列的定义,它是Queue接口的一个子接口。
使用Deque可以进行以下操作:
- 在队列头部插入元素:可以使用
addFirst()
或者offerFirst()
方法在队列的头部插入一个元素。 - 在队列尾部插入元素:可以使用
addLast()
或者offerLast()
方法在队列的尾部插入一个元素。 - 从队列头部删除元素:可以使用
removeFirst()
或者pollFirst()
方法从队列的头部删除一个元素。 - 从队列尾部删除元素:可以使用
removeLast()
或者pollLast()
方法从队列的尾部删除一个元素。 - 获取队列头部的元素:可以使用
getFirst()
或者peekFirst()
方法获取队列头部的元素,但不会将其从队列中删除。 - 获取队列尾部的元素:可以使用
getLast()
或者peekLast()
方法获取队列尾部的元素,但不会将其从队列中删除。 - 判断队列是否为空:可以使用
isEmpty()
方法判断队列是否为空。 - 获取队列的大小:可以使用
size()
方法获取队列中元素的个数。 offer()
方法:用于在队列尾部插入元素,如果插入成功则返回true,否则返回false。它类似于add()
方法,但不同之处在于当队列已满时,add()
方法会抛出异常,而offer()
方法会返回false。push()
方法:用于在队列头部插入元素,即将元素压入栈顶。它等效于addFirst()
方法。与offer()
方法类似,如果插入成功则返回true,否则抛出异常。
Deque接口有多个实现类可供使用,Java提供了两个常用的实现类:
- LinkedList:基于链表实现的双端队列,支持快速插入和删除操作,但在随机访问和迭代性能上相对较慢。
- ArrayDeque:基于数组实现的双端队列,支持快速随机访问和插入删除操作,内存占用较小。但在大量元素的插入删除操作中,可能需要重新调整内部数组的容量,导致时间复杂度稍高。
举例:
public class DequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
// 在队列头部插入元素
deque.addFirst(1);
deque.offerFirst(2);
// 在队列尾部插入元素
deque.addLast(3);
deque.offerLast(4);
// 从队列头部删除元素
int first = deque.removeFirst();
System.out.println("Removed from first: " + first);
// 从队列尾部删除元素
int last = deque.removeLast();
System.out.println("Removed from last: " + last);
// 获取队列头部的元素
int peekFirst = deque.peekFirst();
System.out.println("Peek from first: " + peekFirst);
// 获取队列尾部的元素
int peekLast = deque.peekLast();
System.out.println("Peek from last: " + peekLast);
// 遍历队列中的元素
System.out.println("Elements in the deque:");
for (Integer element : deque) {
System.out.println(element);
}
// 判断队列是否为空
boolean isEmpty = deque.isEmpty();
System.out.println("Is deque empty? " + isEmpty);
// 获取队列的大小
int size = deque.size();
System.out.println("Size of the deque: " + size);
}
}
LinkedList
LinkedList在栈和队列中均有应用,Linkedlist也有很多方法,下面对LinkedList的方法进行总结。
增加:add/offer/push/addFrist/offerFrist/offerLast等等
删除:remove/pop/poll/pollFirst/pollLast等等
如何进行区分?
这些方法分别来自于集合Collections,队列Queue,栈Stack,双端队列Deque,每对方法都有一定的含义,不建议笼统归为添加/删除。
LinkedList类图为:
类LinkedList
实现了以上Deque,Queue,List,Collection的所有的方法。
-
add
和remove
是一对,源自Collection
;- 添加到队尾,从队头删除;
-
offer
和poll
是一对,源自Queue
;- 队列(先进先出 => 尾进头出),所以添加到队尾,从队头删除;
-
push
和pop
是一对,源自Deque
,其本质是栈(Stack
类由于某些历史原因,官方已不建议使用,使用Deque
代替);- 栈(先进后出 => 头进头出),所以添加到队头,从队头删除;
-
offerFirst/offerLast
和pollFirst/pollLast
是一对,源自Deque
,其本质是双端队列。- 双端队列(两端都可以进也都可以出),根据字面意思,
offerFirst
添加到队头,offerLast
添加到队尾,pollFirst
从队头删除,pollLast
从队尾删除。
- 双端队列(两端都可以进也都可以出),根据字面意思,
在使用的时候,建议根据用途来使用不同的方法,比如你想把LinkedList
当做集合list
,那么应该用add/remove
,如果想用作队列,则使用offer/poll
,如果用作栈,则使用push/pop
,如果用作双端队列,则使用offerFirst/offerLast/pollFirst/pollLast
fferLast添加到队尾,
pollFirst从队头删除,
pollLast`从队尾删除。**
在使用的时候,建议根据用途来使用不同的方法,比如你想把LinkedList
当做集合list
,那么应该用add/remove
,如果想用作队列,则使用offer/poll
,如果用作栈,则使用push/pop
,如果用作双端队列,则使用offerFirst/offerLast/pollFirst/pollLast