（超详细）动手编写 — 栈、队列 ( Java实现 )
前言
栈
概念
什么是栈？
**栈 **：是一种特殊的线性表，只能在一端进行操作
入栈：往栈中添加元素的操作，一般叫做push
出栈：从栈中移除元素的操作，一般叫做pop，出栈（弹出栈顶元素）
注意：这里说的"栈"与内存中的"栈空间"是两个不同的概念
栈的结构
相比于数组和链表而言，栈同样是存储相同类型数据的线性数据结构，只不过栈的受限性比较大，比如说：栈只有一端是开放的（栈顶），所有的数据操作都是在这一端进行的，基于这个特性，有了所谓的"后进先出(Last In First Out, LIFO)"的特点，其他 3 面是封闭的，所以栈除了栈顶元素，栈中的其他元素都是未知的，栈同时也做不到随机访问。
图示栈结构：
后进先出：
栈的设计
看到前面的栈结构图，是不是很熟悉，事实上，栈除了三面封闭的特性，其他的是和之前写过的线性数据结构一致的，所以栈的内部实现可以直接利用以前学过的数据结构实现，动态数组DynamicArray，链表LinkedList都是可以的，没有读过前面的编写动态数组DynamicArray，链表LinkedList的文章的可以先去看看，动手编写—动态数组（Java实现) 以及 动手编写-链表（Java实现)
但是我们编写的Stack栈类，并不是直接去继承这些类，因为这样子会暴露动态数组DynamicArray，链表LinkedList的一些原有方法，例如随机访问，随机插入，删除等等，这样都会使得栈失去特性。采用组合模式的方式能够解决这一点，画一下类图关系：
栈的接口设计
1、属性：
private List<E> list;—— 利用基于List接口的线性表实现类设计栈
2、接口方法：
int size();—— 查看当前栈元素的数量boolean isEmpty();—— 判断栈是否为空public void push(E element);—— 入栈，添加元素public E pop();—— 出栈，删除尾部元素public E top();—— 添获取栈顶元素void clear();—— 清除栈元素
完成设计后，是具体的方法编码实现，因为是利用动态数组DynamicArray，链表LinkedList实现的栈，调用的都是封装好的方法，这里就不细讲了
编码实现
public class Stack<E> extends DynamicArray<E>{
//利用动态数组实现栈
private List<E> list = new DynamicArray<>();
//利用链表实现栈
//private List<E> list = new DynamicArray<>();
/**
* 查看栈元素数量
* @return
*/
public int size() {
return list.size();
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 入栈，添加元素
* @param element
*/
public void push(E element){
list.add(element);
}
/**
* 出栈，删除尾部元素
*/
public E pop(){
return list.remove(list.size() - 1);
}
/**
* 获取栈顶元素
* @return
*/
public E top(){
return list.get(list.size() - 1);
}
/**
* 清空栈元素
*/
public void clear() {
list.clear();
}
}
小结
栈的应用
1、双栈实现浏览器的前进和后退
2、软件的撤销（Undo）、恢复（Redo）功能
队列
概念
什么是队列？
队列：与前面栈不同的一点是，栈只能在栈顶一端操作元素，而队列能在首尾两端进行操作，队列同样是一种特殊的线性表
入队：只能从队尾（rear）添加元素，一般叫做enQueue
出队：只能从队头（front）移除元素，一般叫做deQueue
队列的结构
相比于数组、链表及栈而言，队列同样是存储相同类型数据的线性数据结构，只不过队列的受限性比栈小一点，但比数组、链表大，比如说：队列只能在队尾一端添加数据，队头移除元素，基于这个特性，有了所谓的"先进先出的原则，First In First Out，FIFO"的特点，其他 2 面在结构设计上是封闭的，所以队列除了队头元素，队列中的其他元素都是未知的，当然队尾元素也是可见的，但是我们一般只在队尾进行元素添加操作，所以也不会开放这个方法，队列同时也做不到随机访问。
图示队列结构：
队列的设计
队列和数组、链表、以及栈都是线性表结构，所以我们没有必要去做一些重复的操作，利用之前写好的动态数组DynamicArray，链表LinkedList都是可以实现的，同样利用栈也是可以实现队列的，但是这里我们是用双向链表Both_LinkedList实现。
在前面动手编写-链表（Java实现)一文讲到，双向链表的头结点与尾结点有first与last指针指向，这对于队列在队头、队尾操作元素是十分方便的，当然是用动态数组或者单向链表也是可以的，只是数组在队头删除元素会使得后面的元素结点往前移动，而单向链表在队尾添加元素时，指针head需要遍历到尾部结点，这两者都会造成复杂度的增加，所以选择双向链表更好
同样的，但是我们编写的Queue队列并不直接接去继承这些类，依旧采用组合的方式实现，画一下类图关系
队列的接口设计
1、属性：
private List<E> list;—— 利用基于List接口的线性表实现类设计队列
2、接口方法：
int size();—— 查看当前队列元素的数量boolean isEmpty();—— 判断队列是否为空public void enQueue(E element);—— 入队，添加元素public E deQueue();—— 出队，删除头部元素public E front();—— 添获取队头元素void clear();—— 清除队列元素
完成设计后，是具体的方法编码实现，因为是利用双向链表Both_LinkedList实现的队列，调用的都是封装好的方法，这里不细讲
编码实现
双向链表实现队列：
public class Queue<E> {
//利用双向链表封装好的方法实现队列
private List<E> list = new Both_LinkedList<>();
/**
* 获取队列元素数量
* @return
*/
public int size() {
return list.size();
}
/**
* 判断当前队列是否为空
* @return
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 入队，从队尾添加元素
* @param element
*/
public void enQueue(E element) {
list.add(element);
}
/**
* 出队，从队头移除元素
* @return
*/
public E deQueue() {
return list.remove(0);
}
/**
* 获取队头元素
* @return
*/
public E front() {
return list.get(0);
}
/**
* 清空队列元素
*/
public void clear() {
list.clear();
}
}
双栈实现队列：
public class QueueByStack<E> {
//定义两个栈，inStack用于队尾入队，outStack用于队头出队
private Stack<E> inStack,outStack;
//使用构造函数初始化
public QueueByStack() {
this.inStack = new Stack<>();
this.outStack = new Stack<>();
}
/**
* 获取队列元素数量
* @return
*/
public int size() {
return inStack.size() + outStack.size();
}
/**
* 判断当前队列是否为空
* @return
*/
public boolean isEmpty() {
return inStack.isEmpty() && outStack.isEmpty();
}
/**
* 入队，从队尾添加元素
* @param element
*/
public void enQueue(E element) {
inStack.push(element);
}
/**
* 出队，从队头添加元素
* @return
*/
public E deQueue() {
checkOutStack();
return outStack.pop();
}
/**
* 获取队头元素
* @return
*/
public E front() {
checkOutStack();
return outStack.top();
}
/**
* 清空栈元素
*/
public void clear() {
inStack.clear();
outStack.clear();
}
/**
* 检查outStack是否为空，如果不为空，等着出队
* 如果为空，且inStack不为空，将inStack中的
* 元素出栈，入栈到outStack，然后准备出队
*/
private void checkOutStack() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
双端队列
概念
双端队列：是能在头尾两端添加、删除的队列
结构图示：
设计
双端队列Deque与队列Queue在实现关系上没有区别，同样是基于双向链表Both_LinkedList，使用组合模式实现的
双向队列的接口设计
1、属性：
private List<E> list;—— 利用基于List接口的线性表实现类设计队列
2、接口方法：
int size();—— 查看当前队列元素的数量boolean isEmpty();—— 判断队列是否为空public void enQueueRear(E element);—— 入队，从队尾入队public E deQueueRear();—— 出队，从队尾出队public void enQueueFront(E element);—— 入队，从队头入队public E enQueueFront();—— 出队，从队头出队public E front();—— 添获取队头元素public E rear();—— 添获取队尾元素void clear();—— 清除队列元素
编码
public class Deque<E> {
//利用双向链表封装好的方法实现队列
private List<E> list = new Both_LinkedList<>();
/**
* 获取队列元素数量
* @return
*/
public int size() {
return list.size();
}
/**
* 判断当前队列是否为空
* @return
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 入队，从队尾入队
* @param element
*/
public void enQueueRear(E element) {
list.add(element);
}
/**
* 出队，从队尾出队
* @return
*/
public E deQueueRear() {
return list.remove(list.size() - 1);
}
/**
* 入队，从队头入队
* @param element
*/
public void enQueueFront(E element) {
list.add(0, element);
}
/**
* 出队，从对头出队
* @return
*/
public E deQueueFront() {
return list.remove(0);
}
/**
* 获取队头元素
* @return
*/
public E front() {
return list.get(0);
}
/**
* 获取队尾元素
* @return
*/
public E rear() {
return list.get(list.size() - 1);
}
/**
* 清空队列元素
*/
public void clear() {
list.clear();
}
}
循环队列
循环队列
概念：
循环队列：用数组实现并且优化之后的队列
图示结构：
设计：
循环队列又叫环形队列，是基于Java数组实现的，使用front指针指向的位置是队头，设计上，删除元素后不会像数组一样，挪动元素往前覆盖，而是将值置空，front往后移动，以这样的机制删除元素，删除后的位置，当front指针后边的位置满了，新元素就可以填补刚刚删除的空位，起到环形的作用
循环接口设计
1、属性：
private int front;—— 循环队列队头指针private int size;—— 队列元素数量private E[] elements;—— 使用顺序结构数组存储private static final int DEFAULT_CAPACITY = 10;—— 数组的默认初始化值
2、接口方法：
int size();—— 查看当前队列元素的数量boolean isEmpty();—— 判断队列是否为空public void enQueue(E element);—— 入队，从队尾入队public E deQueue();—— 出队，删除头部元素public E front();—— 添获取队头元素void clear();—— 清除队列元素private void ensureCapacity(int capacity)—— 保证要有capacity的容量,不足则扩容private int index(int index);—— 索引映射函数，返回真实数组下标
1、出队操作
2、入队操作
3、再入队
4、注意点：
(1) 入队
(2)入队
(3)出队
(4)扩容
编码：
public class CircleQueue<E> {
//数组的默认初始化值
private static final int DEFAULT_CAPACITY = 10;
//循环队列队头指针
private int front;
//队列元素数量
private int size;
//使用顺序结构数组存储
private E[] elements;
/**
* 构造函数初始化数组
*/
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* 获取队列元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 入队，从队尾添加元素
* @param element
*/
public void enQueue(E element) {
ensureCapacity(size + 1);
//elements[(front + size) % elements.length] = element;
//调用封装函数
elements[index(size)] = element;
size++;
}
/**
* 出队，从队头移除元素
* @return
*/
public E deQueue() {
E element = elements[front];
elements[front] = null;
//front = (front + 1) % elements.length;
//调用封装函数
front = index(1);
size--;
return element;
}
/**
* 获取队头元素
* @return
*/
public E front(){
return elements[front];
}
/**
* 清空队列元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
//elements[(i + front) % elements.length] = null;
//调用封装函数
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 保证要有capacity的容量,不足则扩容
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
//newElements[i] = elements[(i + front) % elements.length];
//调用封装函数
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
/**
* 索引映射函数，返回真实数组下标
* @param index
* @return
*/
private int index(int index){
return (front + index) % elements.length;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
循环双端队列
概念：
循环双端队列：可以进行两端添加、删除操作的循环队
图示结构：
事实上，在结构上，与循环队列是一样的，没有必要设置一个last指针指向队尾，因为我们采用的是数组这种顺序存储结构，实际上，last = (font + size - 1) % array.length，只是我们在方法上对其功能进行了扩展而已
循环接口设计
1、属性：
private int front;—— 循环队列队头指针private int size;—— 队列元素数量private E[] elements;—— 使用顺序结构数组存储private static final int DEFAULT_CAPACITY = 10;—— 数组的默认初始化值
2、接口方法：
int size();—— 查看当前队列元素的数量boolean isEmpty();—— 判断队列是否为空public void enQueueRear(E element);—— 入队，从队尾入队public E deQueueRear();—— 出队，从队尾出队public void enQueueFront(E element);—— 入队，从队头入队public E enQueueFront();—— 出队，从队头出队public E front();—— 添获取队头元素public E rear();—— 添获取队尾元素void clear();—— 清除队列元素private void ensureCapacity(int capacity)—— 保证要有capacity的容量,不足则扩容private int index(int index);—— 索引映射函数，返回真实数组下标
编码实现
上面也说到了，在结构上，与循环队列是一样的，所以大多数的方法是一样了，只是对其功能进行了增强，调整了部分方法逻辑
方法变动：
(1) 新增public void enQueueFront(E element); —— 入队，从队头入队
/**
* 入队，从队头入队
* @param element
*/
public void enQueueFront(E element) {
//front指向当前节点前一位置
front = index(-1);
//假设虚拟索引，以front指向的位置为0，则向队头添加元素时往-1添加
elements[front] = element;
size++;
}
(2) 新增public E deQueueRear(); —— 出队，从队尾出队
/**
* 出队，从队尾出队
* @return
*/
public E deQueueRear() {
//找到尾部元素的真实索引
int last = index(size - 1);
E element = elements[last];
elements[last] = null;
size--;
return element;
}
(3) 新增public E rear(); —— 添获取队尾元素
/**
* 获取队尾元素
* @return
*/
public E rear() {
return elements[index(size - 1)];
}
(4) 变动private int index(int index); —— 索引映射函数，返回真实数组下标
/**
* 索引映射函数，返回真实数组下标
* @param index
* @return
*/
private int index(int index){
index += front;
//但真实index为0时，往队头添加元素，传入 -1，小于0
if (index < 0){
index += elements.length;
}
return index % elements.length;
}
声明
个人能力有限，有不正确的地方，还请指正
文章为原创，欢迎转载，注明出处即可
本文的代码已上传github,欢迎star
最新文章
- JQuery中ajax的相关方法总结
- Caffe学习
- 嵌入式Linux驱动学习之路(十二)按键驱动-poll机制
- Struts学习总结-02 类型转换
- python拷贝文件到多个文件夹
- Node.js规范化应用
- 使用Qt Style Sheets制作UI特效
- MySQL replace 的简介
- Unity3D手机斗地主游戏开发实战（03）_地主牌显示和出牌逻辑(不定期更新中~~~)
- 3.Properties文件的加载和使用
- 『集群』007 如何测试Slithice源代码
- TCPDF说明文档
- 上位机与三菱FX3U通过FX-232-BD通信
- 【刷题】LOJ 556 「Antileaf's Round」咱们去烧菜吧
- [MacOS] Genymotion***下载模拟器方法
- UOJ347 WC2018 通道 边分治、虚树
- Scala进阶之路-Spark本地模式搭建
- 本地广播的简单示例 --Android开发
- pycharm 出现Process finished with exit code 0 或 Process finished with exit code -1
- 【Java并发编程】之十六：深入Java内存模型——happen-before规则及其对DCL的分析（含代码）