南通市住房城乡建设局网站,英雄联盟世界排名,建站公司主要做那些业务,昌平网站开发公司数据结构的三要素包括#xff1a;逻辑结构、存储结构、数据的运算。逻辑结构描述的是数据之间的逻辑关系#xff0c;分为线性结构#xff08;线性表#xff08;数组、链表#xff09;、栈、队列#xff09;和非线性结构#xff08;图、树、集合#xff09;。物理结构也…数据结构的三要素包括逻辑结构、存储结构、数据的运算。逻辑结构描述的是数据之间的逻辑关系分为线性结构线性表数组、链表、栈、队列和非线性结构图、树、集合。物理结构也称为存储结构顺序存储、链式存储、索引存储、散列存储。
常见的数据结构分为线性数据结构和非线性数据结构包括数组、链表、栈、队列、树、图、散列表等。 在Java中数组这种数据结构有专门的实现不可变数组int [] array{})、可变数组ArrayList同样的链表这种数据结构也有专门的实现类LinkedList这些实现类都是java封装好的类开箱即用。但是java有没有专门针对于栈、队列这两种数据结构的封装类呢
结果是肯定的。下面我们来介绍在java这门语言中对栈、队列这两种数据结构的封装类。
一、栈Stack、ArrayDeque、LinkedList
首先来看一下JAVA集合体系图 Stack类正如类名那样该类是java对栈这种数据结构的封装我们可以很容易滴使用该类中的方法实现栈的所有功能。下面是该类的五个方法
方法名返回类型说明emptyboolean判断是否为空peekE只返回栈顶端的元素不弹出该元素空栈会抛出异常popE弹出栈顶的元素pushE将元素压入栈并返回searchint返回最靠近顶端的目标元素到顶端的距离调用 lastIndexOf
不过由于Stack类是继承至Vector,Vector 类在方法上添加了 synchronized 以达到线程安全的目的不过 JVM 级别的 synchronized 特别消耗资源已不被 Java 官方推荐使用。因此用Stack类作为栈来使用已经不合时宜。 ArrayDeque类实现了Deque接口而Deque接口又继承至Queue接口Queue是一个单向队列在头部进行remove()、poll()出队操作在尾部进行add()、offer()入队操作使用peek()、element()方法检索队列头。下面的表格给出了Queue接口的方法 boolean add(E e) 将指定的元素插入到此队列中如果可以立即执行此操作而不会违反容量限制 true在成功后返回 IllegalStateException如果当前没有可用空间则抛出IllegalStateException。 E element() 检索但不删除这个队列的头。 boolean offer(E e) 如果在不违反容量限制的情况下立即执行则将指定的元素插入到此队列中。 E peek() 检索但不删除此队列的头如果此队列为空则返回 null 。 E poll() 检索并删除此队列的头如果此队列为空则返回 null 。 E remove() 检索并删除此队列的头。 Deque接口定义了双端队列dequedouble-ended queue双端队列是一种具有队列和栈的性质的数据结构它允许两端都可以进行入和出队操作的队列即元素可以从队头出队和入队也可以从队尾出队和入队。因此。Deque即可当成队列使用也可当成栈使用。下面是Deque中定义的方法 boolean add(E e) 将指定的元素插入此双端队列表示的队列中换句话说在此双端队列的尾部如果它是立即可行且不会违反容量限制返回 true在成功时和抛出 IllegalStateException如果当前没有空间可用的。 void addFirst(E e) 插入此双端队列的前面如果它是立即可行且不会违反容量限制抛出一个指定的元素 IllegalStateException如果当前没有空间可用。 void addLast(E e) 在插入如果它是立即可行且不会违反容量限制抛出此双端队列的末尾指定元素 IllegalStateException如果当前没有空间可用。 boolean contains(Object o) 如果此deque包含指定的元素则返回 true 。 IteratorE descendingIterator() 以相反的顺序返回此deque中的元素的迭代器。 E element() 检索但不删除由此deque表示的队列的头部换句话说该deque的第一个元素。 E getFirst() 检索但不删除这个deque的第一个元素。 E getLast() 检索但不删除这个deque的最后一个元素。 IteratorE iterator() 以正确的顺序返回此deque中的元素的迭代器。 boolean offer(E e) 将指定的元素插入由此deque表示的队列换句话说在该deque的尾部如果可以立即执行而不违反容量限制 true在成功时 false如果当前没有可用空间则返回false。 boolean offerFirst(E e) 在此deque的前面插入指定的元素除非它会违反容量限制。 boolean offerLast(E e) 在此deque的末尾插入指定的元素除非它会违反容量限制。 E peek() 检索但不删除由此deque表示的队列的头部换句话说此deque的第一个元素如果此deque为空则返回 null 。 E peekFirst() 检索但不删除此deque的第一个元素或返回 null如果这个deque是空的。 E peekLast() 检索但不删除此deque的最后一个元素如果此deque为空则返回 null 。 E poll() 检索并删除由此deque换句话说此deque的第一个元素表示的队列的 null如果此deque为空则返回 null 。 E pollFirst() 检索并删除此deque的第一个元素如果此deque为空则返回 null 。 E pollLast() 检索并删除此deque的最后一个元素如果此deque为空则返回 null 。 E pop() 从这个deque表示的堆栈中弹出一个元素。 void push(E e) 将元素推送到由此deque表示的堆栈换句话说在此deque的头部如果可以立即执行此操作而不违反容量限制则抛出 IllegalStateException如果当前没有可用空间。 E remove() 检索并删除由此deque表示的队列的头换句话说该deque的第一个元素。 boolean remove(Object o) 从此deque中删除指定元素的第一个出现。 E removeFirst() 检索并删除此deque的第一个元素。 boolean removeFirstOccurrence(Object o) 从此deque中删除指定元素的第一个出现。 E removeLast() 检索并删除此deque的最后一个元素。 boolean removeLastOccurrence(Object o) 从此deque中删除指定元素的最后一次出现。 int size() 返回此deque中的元素数。
ArrayDeque类实现了Deque接口 ,类内方法基本与Deque一致。不过ArrayDeque类的底层是一个环形数组具体来说在逻辑结构上是一个环形但是实际存储结构上是一个一维数组。 下面是该类的常用方法 boolean add(E e) 在此deque的末尾插入指定的元素。 void addFirst(E e) 在此deque前面插入指定的元素。 void addLast(E e) 在此deque的末尾插入指定的元素。 void clear() 从这个deque中删除所有的元素。 ArrayDequeE clone() 返回此deque的副本。 boolean contains(Object o) 如果此deque包含指定的元素则返回 true 。 IteratorE descendingIterator() 以相反的顺序返回此deque中的元素的迭代器。 E element() 检索但不删除由这个deque表示的队列的头。 E getFirst() 检索但不删除这个deque的第一个元素。 E getLast() 检索但不删除这个deque的最后一个元素。 boolean isEmpty() 如果此deque不包含元素则返回 true 。 IteratorE iterator() 返回此deque中的元素的迭代器。 boolean offer(E e) 在此deque的末尾插入指定的元素。 boolean offerFirst(E e) 在此deque前面插入指定的元素。 boolean offerLast(E e) 在此deque的末尾插入指定的元素。 E peek() 检索但不删除由此deque表示的队列的头部如果此deque为空则返回 null 。 E peekFirst() 检索但不删除此deque的第一个元素如果此deque为空则返回 null 。 E peekLast() 检索但不删除此deque的最后一个元素或返回 null如果此deque为空。 E poll() 检索并删除由此deque换句话说该deque的第一个元素表示的队列的 null如果此deque为空则返回 null 。 E pollFirst() 检索并删除此deque的第一个元素如果此deque为空则返回 null 。 E pollLast() 检索并删除此deque的最后一个元素如果此deque为空则返回 null 。 E pop() 从这个deque表示的堆栈中弹出一个元素。 void push(E e) 将元素推送到由此deque表示的堆栈上。 E remove() 检索并删除由此deque表示的队列的头部。 boolean remove(Object o) 从此deque中删除指定元素的单个实例。 E removeFirst() 检索并删除此deque的第一个元素。 boolean removeFirstOccurrence(Object o) 删除此deque中指定元素的第一个出现从头到尾遍历deque时。 E removeLast() 检索并删除此deque的最后一个元素。 boolean removeLastOccurrence(Object o) 删除此deque中指定元素的最后一次从头到尾遍历deque时。 int size() 返回此deque中的元素数。 SpliteratorE spliterator() 创建一个late-binding和失败快速 Spliterator在这个deque的元素。 Object[] toArray() 以适当的顺序返回一个包含此deque中所有元素的数组从第一个到最后一个元素。 T T[] toArray(T[] a) 以正确的顺序返回一个包含此deque中所有元素的数组从第一个到最后一个元素; 返回的数组的运行时类型是指定数组的运行时类型。 LinkedList的底层维护了一个双向链表它同时实现了List接口和Deque对口因此它既可以看作一个顺序容器又可以看作一个队列(Queue)同时又可以看作一个栈(stack)换句话说它同时具备双向链表和双端队列特点。从继承图上来看该类实现了Deque接口因此可以使用接口中的方法。 boolean add(E e) 将指定的元素追加到此列表的末尾。 void add(int index, E element) 在此列表中的指定位置插入指定的元素。 boolean addAll(Collection? extends E c) 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。 boolean addAll(int index, Collection? extends E c) 将指定集合中的所有元素插入到此列表中从指定的位置开始。 void addFirst(E e) 在该列表开头插入指定的元素。 void addLast(E e) 将指定的元素追加到此列表的末尾。 void clear() 从列表中删除所有元素。 Object clone() 返回此 LinkedList的浅版本。 boolean contains(Object o) 如果此列表包含指定的元素则返回 true 。 IteratorE descendingIterator() 以相反的顺序返回此deque中的元素的迭代器。 E element() 检索但不删除此列表的头第一个元素。 E get(int index) 返回此列表中指定位置的元素。 E getFirst() 返回此列表中的第一个元素。 E getLast() 返回此列表中的最后一个元素。 int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引如果此列表不包含元素则返回-1。 int lastIndexOf(Object o) 返回此列表中指定元素的最后一次出现的索引如果此列表不包含元素则返回-1。 ListIteratorE listIterator(int index) 从列表中的指定位置开始返回此列表中元素的列表迭代器按适当的顺序。 boolean offer(E e) 将指定的元素添加为此列表的尾部最后一个元素。 boolean offerFirst(E e) 在此列表的前面插入指定的元素。 boolean offerLast(E e) 在该列表的末尾插入指定的元素。 E peek() 检索但不删除此列表的头第一个元素。 E peekFirst() 检索但不删除此列表的第一个元素如果此列表为空则返回 null 。 E peekLast() 检索但不删除此列表的最后一个元素如果此列表为空则返回 null 。 E poll() 检索并删除此列表的头第一个元素。 E pollFirst() 检索并删除此列表的第一个元素如果此列表为空则返回 null 。 E pollLast() 检索并删除此列表的最后一个元素如果此列表为空则返回 null 。 E pop() 从此列表表示的堆栈中弹出一个元素。 void push(E e) 将元素推送到由此列表表示的堆栈上。 E remove() 检索并删除此列表的头第一个元素。 E remove(int index) 删除该列表中指定位置的元素。 boolean remove(Object o) 从列表中删除指定元素的第一个出现如果存在。 E removeFirst() 从此列表中删除并返回第一个元素。 boolean removeFirstOccurrence(Object o) 删除此列表中指定元素的第一个出现从头到尾遍历列表时。 E removeLast() 从此列表中删除并返回最后一个元素。 boolean removeLastOccurrence(Object o) 删除此列表中指定元素的最后一次出现从头到尾遍历列表时。 E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。 int size() 返回此列表中的元素数。 SpliteratorE spliterator() 在此列表中的元素上创建late-binding和故障快速 Spliterator 。 Object[] toArray() 以正确的顺序从第一个到最后一个元素返回一个包含此列表中所有元素的数组。 T T[] toArray(T[] a) 以正确的顺序返回一个包含此列表中所有元素的数组从第一个到最后一个元素; 返回的数组的运行时类型是指定数组的运行时类型。
由于LinkedList与ArrayDeque都是实现了Deque接口因此这两个类中定义的方法几乎完全相同因此这两个类的用法也几乎没有什么差异虽然对于使用者而言用这两个类都可以轻而易举的实现栈、队列的功能。
