赞
踩
栈(Stack):栈是先进后出(FILO, First In Last Out)的数据结构。Java中实现栈有以下两种方式:
由于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()); //判断栈是否为空
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(); //删除栈顶元素
底层是链表
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); } } }
底层是数组实现
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); } }
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提供了两个常用的实现类:
举例:
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的方法进行总结。
增加: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
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。