栈、队列和优先队列

可以使用数组线性表实现栈，使用链表实现队列。

栈(Stack)

将数组线性表定义为栈类中的数据域，而不是使用继承ArrayList的方法是因为，一般来说加强或扩展类的功能时才使用继承的方式。
AbstractList <— Vector <— Stack
ArrayList和Vector类是一样的。如果不需要同步使用ArrayList类。
Stack方法：

• peak() 返回栈顶元素而不移除它
• pop() 返回并移除栈顶元素
• push(e) 添加元素到栈里
• search(e) 检测指定元素是否在栈中

组合的方式实现栈

GenericStack.java

import java.util.ArrayList;
public class Generictack {
    private ArrayList<E> list = new ArrayList<>();

    public int getSize() {
        return list.size();
    }

    public E peek() {
        return list.get(getSize() - 1);
    }

    public void push(E e) {
        list.add(e);
    }

    public E pop() {
        E e = list.get(getSize() -1);
        list.remove(getSize() -1);
        return e;
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        return "stack: " + list.toString();
    }
}

用栈存储素数

TestGenericStack.java

public class TestGenericStack {
    public static void main(String[] args) {
        GenericStack<Integer> stack = new GenericStack<>();
        final int NUMBER_OF_PRIMES = 50;
        
        int count = 0;
        
        for (int i = 2; count < NUMBER_OF_PRIMES; i++) {
            if (isPrime(i)) {
                stack.push(i);
                count++;
            }
        }
        System.out.println("The first 50 prime numbers in descending order: ");
        for (int i = 1; !stack.isEmpty(); i++){
            if (i % 10 == 0)
                System.out.printf("%3d\n", stack.pop());
            else
                System.out.printf("%3d ", stack.pop());
        }
        System.out.println();
        
    }
    
    private static boolean isPrime(int n) {
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

队列(Queue)

java API中java.util.Queue是一个接口
可以用Queue作为父类引用，LinkedList作为实例
java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();

Queue是LinkedList的父类接口
继承关系：
Collection <— Queue <— Deque <— LinkedList
Queue <— AbstractQueue <— PriorityQueue
Queue的方法：

• offer(e) 插入元素e到队列中
• poll() 获取并移除队头(front)元素，，队为空返回null
• remove() 获取并移除队头(front)元素，队为空抛出异常
• peek() 获取但不移除对头元素，队为空返回null
• element() 获取但不移除对头元素，队为空抛出异常

使用继承和组合的方式实现队列和栈都是可行的，但是组合更好一点，因为可以定义一个全新的栈类和队列类，而不需要继承ArrayList和LinkedList中不必要和不合适的方法。

类仅在它们需要被加强或修改时，才会使用继承！！！！

使用组合的方式实现队列

组合的方式实现Queue

import java.util.LinkedList;
public class GenericQueue<E> {
    private LinkedList<E> list = new LinkedList<>();
    public void enqueue(E e) {
        list.addFirst(e);
    }
    public E dequeu() {
        return list.removeFirst();
    }
    public int getSize() {
        return list.size();
    }
    @Override
    public String toString() {
        return "Queue: " + list.toString();
    }
}

继承关系实现Queue

继承关系实现Queue

public class GenericQueue<E> extends java.util.LinkedList<E> {

    public void enqueue(E e) {
        addLast(e);
    }

    public E dequeue() {
        return removeFirst();
    }

    public int getSize() {
        return size();
    }
}

优先队列(PriorityQueue)

对于使用Comparable和Comparator实现的Heap类见文章堆排序

用堆实现优先队列

普通队列是一种先进先出的数据结构，元素在rear添加，在front删除。在优先队列中，元素被赋予优先级，当访问元素时，具有最高优先级的元素最先删除。
Largest-in, first-Out 高进先出
在java API中继承顺序如下：
Queue <— AbstractQueue <— PriorityQueue

可以使用堆实现优先队列，其中根节点是队列中具有最高优先级的对象。

使用Comparable接口

用Comparable实现泛型PriorityQueue

public class MyPriorityQueue<E extends Comparable<E>> {
    private Heap<E> heap = new Heap<>();

    public void enqueue(E newOject) {
        heap.add(newObject);
    }

    public E dequeue() {
        return heap.remove();
    }
    public int getSize() {
        return heap.getSize();
    }
}

用Comparator实现泛型PriorityQueue

用Comparator实现泛型PriorityQueue

import java.util.Comparator;

public class MyPriorityQueue<E> {
    private Comparator<? super E> comparator;
    private Heap<E> heap;
    
    MyPriorityQueue(Comparator<? super E> comparator) {
        this.comparator = comparator;
        this.heap = new Heap<>(comparator);
    }
    
    public void enqueue(E newObject) {
        heap.add(newObject);
    }
    public E dequeue() {
        return heap.remove();
    }
    public int getSize() {
        return heap.getSize();
    }
}

---