文章目录
一、栈
1.1 什么是栈
1.2 栈的应用
1.2.1 无处不在的撤销(undo)操作
1.2.1 计算机程序调用的系统栈
1.3 栈的实现
1.4 栈的时间复杂度
二、队列
2.1 队列认识
2.2 数组队列的实现（顺序存储）
2.2.1 接口实现
2.2.2 接口类实现
2.2.3 执行结果
2.2.4 数组队列复杂度分析
2.2.4 数组队列的问题
2.3 队列的实现（循环队列）
2.3.1 循环队列
2.3.1 循环队列编码实现
2.3.2 循环队列时间复杂度
2.3 顺序存储和循环队列性能对比
一、栈
1.1 什么是栈
栈是一种线性架构
相比数组，栈对应的操作是数组的子集
栈只能从一端添加元素，也只能从一端取出元素，最先放入堆栈中的内容最后被拿出来，最后放入堆栈中的内容最先被拿出来， 被称为 先进后出 、后进先出。
这里说的一端指的就是 栈顶，删除与添加均在栈顶进行操作
如下图所示：
在上图中我们可以看到栈是一种后进先出的数据结构，也就是 Last In First Out（LIFO） ，我们经常看到有 LIFO 找个单词的时候，就是说这是一种后进先出的数据结构，在计算机的世界里，栈拥有着不可思议的作用，接下来我们就来聊一聊，栈的应用。
1.2 栈的应用
1.2.1 无处不在的撤销(undo)操作
栈在我们计算机的世界里，都有哪些操作呢？不管我们是用开发工具，还是文本编辑，我们都会用一个很常用的操作 (undo操作) ，也就是我们常用的 撤销，当我们打字打快了，打错了，我们只需要按住ctrl + z，就可以将我们输入的文字撤销掉，那么栈是如何在撤销中工作的，比如我们想打我爱我的祖国，这几个字，但是我们打完 我爱我的，准备打祖国的时候，不小心打成了 一起，于是我们就可以进行 撤销操作，将我们的 一起，进行出栈操作，然后在将 祖国添加到我们的栈里面，这样就完成了一次栈在撤销中的工作。
如下图所示：
1.2.1 计算机程序调用的系统栈
比如我有下面一段代码：
public static void A(){ System.out.println("A start"); B(); System.out.println("A end"); } public static void B(){ System.out.println("B start"); C(); System.out.println("B end"); } public static void C(){ System.out.println("C end"); }
首先我们会先进入 方法 A()，打印输出语句 A start，将方法 A()，作为第一个栈，进行入栈操作，放入我们的系统栈中，然后进入方法 B()，打印输出语句 B start，将方法 B()，作为第二个栈进行入栈操作，再进入方法 C()，打印我们的 C end，到这里入栈操作已经完成了，我们就会从我们的栈里面去取我们刚才入栈的方法，因为 B() 方法是最后一个入栈的，遵循栈 先进后出 的原则，首先我们取出 B() 方法，进行 出栈操作，打印输出语句 B end，最好我们取出A() 方法，进行 出栈操作，打印输出语句 A end，以上整个就是我们程序调用系统栈的操作，我们来看下打印结果：
A start
B start
C end
B end
A end
1.3 栈的实现
首先我们需要以下几个栈元素：
int getSize(); // 获取栈的元素多少
boolean isEmpty(); //查看栈是否为空
void push(E e); //添加栈元素
E pop(); //出栈
E peek(); //查看栈顶元素是多少
具体方法实现：
自定义数组类：
public class Array<E> { private E[] data; private int size; // 构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array(){ this(10); } // 获取数组的容量 public int getCapacity(){ return data.length; } // 获取数组中的元素个数 public int getSize(){ return size; } // 返回数组是否为空 public boolean isEmpty(){ return size == 0; } // 在index索引的位置插入一个新元素e public void add(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); if(size == data.length) resize(2 * data.length); for(int i = size - 1; i >= index ; i --) data[i + 1] = data[i]; data[index] = e; size ++; } // 向所有元素后添加一个新元素 public void addLast(E e){ add(size, e); } // 在所有元素前添加一个新元素 public void addFirst(E e){ add(0, e); } // 获取index索引位置的元素 public E get(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } public E getLast(){ return get(size - 1); } public E getFirst(){ return get(0); } // 修改index索引位置的元素为e public void set(int index, E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; } // 查找数组中是否有元素e public boolean contains(E e){ for(int i = 0 ; i < size ; i ++){ if(data[i].equals(e)) return true; } return false; } // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){ for(int i = 0 ; i < size ; i ++){ if(data[i].equals(e)) return i; } return -1; } // 从数组中删除index位置的元素, 返回删除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // loitering objects != memory leak if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; } // 从数组中删除第一个元素, 返回删除的元素 public E removeFirst(){ return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public E removeLast(){ return remove(size - 1); } // 从数组中删除元素e public void removeElement(E e){ int index = find(e); if(index != -1) remove(index); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length)); res.append('['); for(int i = 0 ; i < size ; i ++){ res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i < size ; i ++) newData[i] = data[i]; data = newData; } }
