栈
什么是栈
栈是一种用于存储数据的简单数据结构（与链表类似）。数据入栈的次序是栈的关键。可以把一桶桶装的薯片看作是一个栈的例子，当薯片做好之后，它们会依次被添加到桶里，每一片都会是当前的最上面一片，而每次我们取的时候也是取的最上面的那一片，规定你不能破坏桶也不能把底部捅穿，所以第一个放入桶的薯片只能最后一个从桶里取出；
image.png
定义：栈（Stack）是一个有序线性表，只能在表的一端（称为栈顶，top）执行插入和删除操作。最后插入的元素将第一个被删除，所以栈也称为后进先出（Last In First Out，LIFO）或先进后出（First In Last Out）线性表；
两个改变栈的操作都有专用名称。一个称为入栈（push），表示在栈中插入一个元素；另一个称为出栈（pop），表示从栈中删除一个元素。
试图对一个空栈执行栈操作称为下溢（underflow）；
试图对一个满栈执行栈操作称为溢出（overflow）。
通常，溢出和下溢均认为是异常；
栈的应用
无处不在的Undo操作（撤销）；
程序调用的系统栈；
括号/符号匹配；
等等等等....
栈抽象数据类型
下面给出栈抽象数据类型中的操作，为了简单起见，假设数据类型为整型；
栈的主要操作
void push(int data)：将data（数据）插入栈；
int pop()：删除并返回最后一个插入栈的元素；
栈的辅助操作
int top()：返回最后一个插入栈的元素，但不删除；
int size()：返回存储在栈中元素的个数；
int isEmpty()：判断栈中是否有元素；
int isStackFull()：判断栈中是否存满元素；
我们结合之前创建的Array类，我们能够很好的创建属于我们自己的动态数组实现的栈结构，对于用户来说，我们只需要完成我们的相关操作，并且知道我能够不断地往里添加元素而不出错就行了，所以我们先来定义一个通用的栈接口：
public interface ZyhStack<E> {
int getSize();
boolean isEmepty();
void push(E e);
E pop();
E top();
}
然后我们往之前的动态数组中添加两个用户友好的方法：
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
然后实现自己的动态数组为底层的栈结构就轻松多了：
public class ZyhArrayStack<E> implements ZyhStack<E> {
ZyhArray<E> array;
public ZyhArrayStack(int capacity) {
array = new ZyhArray<>(capacity);
}
public ZyhArrayStack() {
array = new ZyhArray<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmepty() {
return array.isEmpty();
}
public int getCapacity() {
return array.getCapacity();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E top() {
return array.getLast();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack:");
res.append("[");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(",");
}
}
res.append("]");
return res.toString();
}
}
简单复杂度分析
从代码中可以看出，几乎所有的时间复杂度都为O(1)级别，比较特别的是push()和pop()操作可能涉及到底层数组的扩容或缩容的操作，所以是均摊下来的复杂度；
队列
什么是队列
队列是一种用于存储数据的数据结构（与链表和栈类似），数据到达的次序是队列的关键；在日常生活中队列是指从序列的开始按照顺序等待服务的一队人或物；
image.png
定义：队列是一种只能在一端插入（队尾），在另一端删除（队首）的有序线性表。队列中第一个插入的元素也是第一个被删除的元素，所以队列是一种先进先出（FIFO,First In First Out）或后进后出（LiLO,Last In Last Out）线性表；
与栈类似，两个改变队列的操作各有专用名称；在队列中插入一个元素，称为入队（EnQueue），从队列中删除一个元素，称为出队（DeQueue）；试图对一个空队列执行出队操作称为下溢（underflow），试图对一个满队列执行入队操作称为溢出（overflow）；通常认为溢出和下溢是异常。
队列的一些应用举例
操作系统根据（具有相同优先级的）任务到达的顺序调度任务（例如打印队列）；
模拟现实世界中的队列，如售票柜台前的队伍，或者任何需要先来先服务的场景；
多道程序设计；
异步数据传输（文件输入输出、管道、套接字）；
等等等等...
动态数组简单实现队列结构
我们仍然定义一个Queue接口来说明我们队列中常用的一些方法：
public interface ZyhQueue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
借由我们之前自己实现的动态数组，那么我们的队列就很简单了：
public class ZyhArrayQueue<E> implements ZyhQueue<E> {
private ZyhArray<E> array;
public ZyhArrayQueue(int capacity){
array = new ZyhArray<>(capacity);
}
public ZyhArrayQueue(){
array = new ZyhArray<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
}
简单的复杂度分析
void enquque(E)：O(1)（均摊）
E dequeue()：O(n)
E front()：O(1)
int getSize()：O(1)
boolean isEmpty()：O(1)
实现自己的循环队列
循环队列的实现其实就是维护了一个front和一个tail分别指向头和尾，然后需要特别注意的呢是判定队满和队空的条件：
队空：front == tail，这没啥好说的；
队满：tail + 1 == front，这里其实是有意浪费了一个空间，不然就判定不了到底是队空还是队满了，因为条件都一样...
public class ZyhLoopQueue<E> implements ZyhQueue<E> {
private E[] data;
private int front, tail;
private int size;
public ZyhLoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public ZyhLoopQueue(){
this(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void enqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
res.append("front [");
for(int i = front ; i != tail ; i = (i + 1) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}
}
简单复杂度分析
void enquque(E)：O(1)（均摊）
E dequeue()：O(1)（均摊）
E front()：O(1)
int getSize()：O(1)
boolean isEmpty()：O(1)
简单数组队列和循环队列的简单比较
我们来简单对比一下两个队列的性能吧，这里直接上代码：
// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
private static double testQueue(ZyhQueue<Integer> q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
ZyhArrayQueue<Integer> arrayQueue = new ZyhArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
ZyhLoopQueue<Integer> loopQueue = new ZyhLoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
我这里的测试结果是这样的，大家也就可见一斑啦：
image.png
其实ZyhArrayQueue慢主要是因为出栈时每次都需要把整个结构往前挪一下
网友评论