数据结构 - 栈、队列、堆（java）
作者：Studying_swz
- 2022-10-23 天津
本文字数：8356 字
阅读完需：约 27 分钟
栈
栈（Stack）又名堆栈–先进后出，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。表尾称为栈顶，相应地，表头称为栈底。栈的基本操作除了在栈顶进行插入和删除外，还有栈的初始化，判空以及取栈顶元素等。
import java.util.Stack;public class ReStack { public static void main(String[] args) { //可见stack是继承Vector的，所以是同步的--线程安全的 Stack<Integer>stack = new Stack<>(); stack.push(1); stack.push(13); stack.push(123); stack.push(1234); stack.push(1231); //返回最先匹配的索引，栈顶默认索引为1 System.out.println(stack.search(123)); int peek = stack.peek(); int pop = stack.pop(); stack.isEmpty(); }}//源码部分package java.util;public class Stack<E> extends Vector<E> { /** * Creates an empty Stack. */ public Stack() { }
public E push(E item) { addElement(item);
return item; }
public synchronized E pop() { E obj; int len = size();
obj = peek(); removeElementAt(len - 1);
return obj; }
public synchronized E peek() { int len = size();
if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); }
public boolean empty() { return size() == 0; }
public synchronized int search(Object o) { int i = lastIndexOf(o);
if (i >= 0) { return size() - i; } return -1; }
/** use serialVersionUID from JDK 1.0.2 for interoperability */ private static final long serialVersionUID = 1224463164541339165L;}
复制代码
队列
队列（Queue）是一种先进先出（FIFO，First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。队列常用的方法有：add、remove、element、offer、poll、peek、put、take。
import java.util.Queue;
public class ReStack { public static void main(String[] args) { //可见队列是接 Queue<Integer>queue= new LinkedList<>(); //add和offer一样 queue.add(123); queue.add(512); queue.add(5124); queue.add(5112); queue.offer(5122); System.out.println(queue.poll()); queue.remove(123); //peek和element一样 System.out.println(queue.peek()); System.out.println(queue.element()); }}
//源码部分package java.util;public interface Queue<E> extends Collection<E> { boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek();}//源码部分upackage java.util;import java.util.function.Consumer;
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0;
transient Node<E> first; transient Node<E> last; public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
/** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
/** * Unlinks non-null first node f. */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
/** * Unlinks non-null last node l. */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev;
if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }
if (next == null) { last = prev; } else { next.prev = prev; x.next = null; }
x.item = null; size--; modCount++; return element; }
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
public void addFirst(E e) { linkFirst(e); }
public void addLast(E e) { linkLast(e); }
public boolean contains(Object o) { return indexOf(o) != -1; }
public int size() { return size; }
public boolean add(E e) { linkLast(e); return true; }
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
public void add(int index, E element) { checkPositionIndex(index);
if (index == size) linkLast(element); else linkBefore(element, node(index)); }
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
/** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size; }
private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; }
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index);
if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }
public E element() { return getFirst(); }
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
public E remove() { return removeFirst(); }
public boolean offer(E e) { return add(e); }
public boolean offerFirst(E e) { addFirst(e); return true; }
public boolean offerLast(E e) { addLast(e); return true; }
public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
public void push(E e) { addFirst(e); }
public E pop() { return removeFirst(); }
public boolean removeFirstOccurrence(Object o) { return remove(o); }
public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
...................................................}
复制代码
堆
什么是最大堆和最小堆？最大（小）堆是指在树中，存在一个结点而且该结点有儿子结点，该结点的 data 域值都不小于（大于）其儿子结点的 data 域值，并且它是一个完全二叉树（不是满二叉树）。最大堆的根结点是树中元素最大的；最小堆的根结点是树中元素最小的。
大小为 k 的堆中添加元素的时间复杂度为 O ( log k )，我们将重复该操作 N 次，故总时间复杂度为 O ( N log k )。Java 中的堆是用优先队列 PriorityQueue 实现的。默认创建一个最小堆，可以接受一个 Comparator 比较器，来创建最大堆。由于 Comparator 是一个函数接口，这里我们可以直接传入一个 lambda 表达式就能够自动创建 Comparator 对象。
import java.util.PriorityQueue;public class ReStack { public static void main(String[] args) { Queue<Integer> minheap =new PriorityQueue<Integer>();//默认为最小堆 Queue<Integer> maxheap =new PriorityQueue<Integer>((n1, n2) -> n2-n1);//创建最大堆 minheap.add(12); minheap.add(124); minheap.add(122); minheap.add(128); System.out.println(minheap.peek()); minheap.poll(); System.out.println(minheap.peek()); minheap.size(); }}
//源码package java.util;
import java.util.function.Consumer;
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/** * Priority queue represented as a balanced binary heap: the two * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The * priority queue is ordered by comparator, or by the elements' * natural ordering, if comparator is null: For each node n in the * heap and each descendant d of n, n <= d. The element with the * lowest value is in queue[0], assuming the queue is nonempty. */ transient Object[] queue; // non-private to simplify nested class access
/** * The number of elements in the priority queue. */ private int size = 0;
/** * The comparator, or null if priority queue uses elements' * natural ordering. */ private final Comparator<? super E> comparator;
/** * The number of times this priority queue has been * <i>structurally modified</i>. See AbstractList for gory details. */ transient int modCount = 0; // non-private to simplify nested class access
/** * Creates a {@code PriorityQueue} with the default initial * capacity (11) that orders its elements according to their * {@linkplain Comparable natural ordering}. */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); }
public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }
public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); }
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
@SuppressWarnings("unchecked") public PriorityQueue(Collection<? extends E> c) { if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; this.comparator = (Comparator<? super E>) ss.comparator(); initElementsFromCollection(ss); } else if (c instanceof PriorityQueue<?>) { PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; this.comparator = (Comparator<? super E>) pq.comparator(); initFromPriorityQueue(pq); } else { this.comparator = null; initFromCollection(c); } }
@SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); }
@SuppressWarnings("unchecked") public PriorityQueue(SortedSet<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initElementsFromCollection(c); }
private void initFromPriorityQueue(PriorityQueue<? extends E> c) { if (c.getClass() == PriorityQueue.class) { this.queue = c.toArray(); this.size = c.size(); } else { initFromCollection(c); } }
private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) for (int i = 0; i < len; i++) if (a[i] == null) throw new NullPointerException(); this.queue = a; this.size = a.length; } .....................................}
复制代码
堆的操作：1）创建堆--最大堆/最小堆 2）添加元素-add() ----O(logn)3）删除元素-poll()-----O(logn)---删除堆顶 4）堆的长度----minheap.size();5）堆得遍历---删除元素
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【Studying_swz】的原创文章。
原文链接:【http://xie.infoq.cn/article/916e724ff68e47e19ccb16cf3】。文章转载请联系作者。
Studying_swz
关注
还未添加个人签名 2020-12-23 加入
还未添加个人简介
评论