java特殊数据结构：栈Stack
目录
含义
代码实现
含义
* 两个特殊的数据结构
* 栈Stack：FILO
* 定义栈
* 对栈的基本操作只有push进栈和pop出栈两种，栈的实现可以有数组实现的顺序栈和链表结构的链式栈
*
* java提供的具体实现类Stack
* public class Stack<E> extends Vector<E>
* E push(E item) 将数据存储到数组中，如果集合已经满了，则添加新数据时增容
* E pop() 弹出栈顶数据
* E peek() 查看栈顶数据，并不会执行弹出操作
* search(Object o) 查找o对象的下标值
*
* 手写实现
* 1、定义接口
* public interface Stack<T> {
//栈是否为空 记得在方法上添加注释
boolean isEmpty();
// data元素入栈
void push(T data);
//返回栈顶元素,未出栈
T peek();
//出栈,返回栈顶元素,同时从栈中移除该元素
T pop();
}
*
* 2、实现类，这里忽略了抽象类
* //顺序栈
public class SeqStack<T> implements Stack<T> {
// 栈顶指针,-1代表空栈
private int top = -1;
// 容量大小默认为10
private static final int capacity = 10;
// 存放元素的数组
private T[] array;
//当前栈中存储的元素个数
private int size;
public SeqStack() {
this(capacity);
}
@SuppressWarnings("unchecked")
public SeqStack(int capacity) {
array = (T[]) new Object[capacity];
}
public int size() {
return size;
}
public boolean isEmpty() {
return this.top == -1;
}
// 添加元素,从栈顶(数组尾部)插入
public void push(T data) {
// 判断容量是否充足
if (array.length == size)
ensureCapacity(size * 2 + 1);// 扩容
// 从栈顶添加元素
array[++top] = data;
size++;
}
private void ensureCapacity(int capacity) {
// 如果需要拓展的容量比现在数组的容量还小,则无需扩容
if (capacity < size)
return;
T[] old = array;
array = (T[]) new Object[capacity];
// for (int i=0; i<size ; i++) //复制元素
// array[i]=old[i];
System.arraycopy(old, 0, array, 0, size);
}
// 获取栈顶元素的值,不删除
public T peek() {
if (isEmpty())
throw new EmptyStackException();
return array[top];
}
// 从栈顶(顺序表尾部)删除
public T pop() {
if (isEmpty())
throw new EmptyStackException();
size--;
return array[top--];
}
}
*
*
* 队列Queue：FIFO
根据实现方式不同分为顺序队列和链式队列。
enqueue(String item) 入队操作
dequeue() 出队操作
循环队列：基于数组的队列实现中，当tail=items.length时需要搬移大量的数据，就会导致
入队操作的性能降低，可以使用循环队列解决
典型算法：约瑟夫环
队列接口 Queue
public interface Queue<E> extends Collection<E> {
boolean add(E e);向队列中添加数据，阈值为64，Double size if small; else grow by 50%
boolean offer(E e);
E remove(); 删除队列头部的数据
E poll();
E element();获取队列中的数据
E peek();
}
Deque 双向队列
### 优先队列
PriorityQueue是AbstractQueue的实现类，优先级队列的元素根据自然排序或者在构造函数时期提供
Comparator来排序，具体根据构造器判断。PriorityQueue不允许null元素
- 队列的头在某种意义上是指定顺序的最后一个元素。队列查找操作poll、remove、peek和element访
问队列头部元素
- 优先级队列是无限制的，但是具有内部capacity，用于控制在队列中存储元素的数组大小
- 该类以及迭代器实现了Collection、Iterator接口的所有可选方法，这个迭代器提供了iterator()方法不
能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历使用Arrays.sort(queue.toArray())
- 注意这个实现不是线程安全的，多线程不应该并发访问PriorityQueue实例，如果有某个线程修改了队列的话
，使用线程安全的类PriorityBlockingQueue
PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素
大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树complete
binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以
通过数组来作为PriorityQueue的底层实现。
阻塞队列就是在队列的基础上添加了阻塞特性。在队列为空时，从队头获取数据会被阻塞，直到队列中有数据才返回；在队列
已满时，插入数据的操作会被阻塞，直到队列中空闲位置后才插入数据，然后返回。基于阻塞队列的生产者-消费者模式可以有
效地协调生产和消费的速度。
#### BlockingQueue接口
方法 抛出异常 返回特殊值 一直阻塞 超时退出
插入 add(e) offer(e) put(e) offer(e, tiime, unit)
移除 remove() poll() take() poll(tiime, unit)
查看 element() peek()
java针对阻塞队列提供了7种常见的实现，分别是
ArrayBlockingQueue由数组结构组成的有界阻塞队列、
LinkedBlockingQueue由链表结构组成的有界阻塞队列，默认长度为Integer.MAX_VALUE，如果指定长度则有上限、
PriorityBlockingQueue支持优先级排序的无界阻塞队列、
DelayQueue使用优先级队列实现的无界阻塞队列、
SynchronousQueue不存储元素的阻塞队列,只起到一个同步器的作用、
LinkedTransferQueue由链表结构组成的无界阻塞队列、
LinkedBlockingDeque由链表结构组成的双向阻塞队列。
代码实现
SeqStack类
package com.zjh1;
import java.util.EmptyStackException;
//顺序栈
public class SeqStack<T> implements Stack<T> {
// 栈顶指针,-1代表空栈
private int top = -1;
// 容量大小默认为10
private static final int capacity = 10;
// 存放元素的数组
private T[] array;
private int size;
public SeqStack() {
this(capacity);
}
@SuppressWarnings("unchecked")
public SeqStack(int capacity) {
array = (T[]) new Object[capacity];
}
public int size() {
return size;
}
public boolean isEmpty() {
return this.top == -1;
}
// 添加元素,从栈顶(数组尾部)插入
public void push(T data) {
// 判断容量是否充足
if (array.length == size)
ensureCapacity(size * 2 + 1);// 扩容
// 从栈顶添加元素
array[++top] = data;
size++;
}
private void ensureCapacity(int capacity) {
// 如果需要拓展的容量比现在数组的容量还小,则无需扩容
if (capacity < size)
return;
T[] old = array;
array = (T[]) new Object[capacity];
// for (int i=0; i<size ; i++) //复制元素
// array[i]=old[i];
System.arraycopy(old, 0, array, 0, size);
}
// 获取栈顶元素的值,不删除
public T peek() {
if (isEmpty())
throw new EmptyStackException();
return array[top];
}
// 从栈顶(顺序表尾部)删除
public T pop() {
if (isEmpty())
throw new EmptyStackException();
size--;
return array[top--];
}
}Stack类
package com.zjh;
public interface Stack<T> {
// 栈是否为空 记得在方法上添加注释
boolean isEmpty();
// data元素入栈
void push(T data);
// 返回栈顶元素,未出栈
T peek();
// 出栈,返回栈顶元素,同时从栈中移除该元素
T pop();
}