基础知识
栈
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。
栈是一种后进先出（LIFO）的数据结构。
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列是一种先进先出（FIFO）的数据结构。
制定手写方案
如果我们要手写一个栈或者队列，先要确定用什么数据结构保存数据，需要实现哪些功能？
选取数据结构
为了更好的理解栈和队列的原理，尽量采用简单的数据结构来保存数据，这样实现的逻辑会变得简单易懂，所以本次采用的是数组。
实现哪些功能
对于栈：
- 入栈和出栈
- 获取栈顶元素但不删除此元素
- 获取栈是否为空的方法
- 获取栈大小的方法
对于队列：
- 进队列和出队列
- 获取队列头元素但不删除此元素
- 获取队列是否为空的方法
- 获取队列大小的方法
使用数组实现栈：
import java.util.Arrays;
import java.util.EmptyStackException;
class Stack<E> {
private E[] _data; // 数据
private int _size; // 数组长度
private int _realLength; // 数组已用长度
@SuppressWarnings("unchecked")
public Stack(int initSize) {
this._size = initSize;
this._data = (E[]) new Object[initSize];
this._realLength = 0;
}
/**
* 默认数组长度为20
*/
public Stack() {
this(20);
}
/**
* 入栈
*
* @param element 添加的元素
*/
public void push(E element) {
if (size() >= _size) {
grow();
}
_data[_realLength++] = element;
}
/**
* 出栈
*
* @return 返回栈顶的元素
*/
public E pop() {
if (size() < 1) {
throw new EmptyStackException();
}
E top = _data[_realLength - 1];
_data[--_realLength] = null;
return top;
}
/**
* 获取栈顶元素
*
* @return 返回的是栈顶元素
*/
public E peek() {
if (size() < 1) {
throw new EmptyStackException();
}
return _data[_realLength - 1];
}
/**
* 判断栈是否为空栈
*
* @return true代表空栈
*/
public boolean isEmpty() {
return _realLength == 0;
}
/**
* 栈的大小
*
* @return 大小值
*/
public int size() {
return _realLength;
}
/**
* 数组的扩容，扩容大小为原先的2倍
*/
private void grow() {
// 扩容后size也要变化
_size = _size * 2;
_data = Arrays.copyOf(_data, _size);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>(1);
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("stack is empty: " + stack.isEmpty());
System.out.println("stack size is: " + stack.size());
System.out.println("stack pop is: " + stack.pop());
System.out.println("stack top is: " + stack.peek());
// stack is empty: false
// stack size is: 4
// stack pop is: 3
// stack top is: 2
}
}
需要注意的几个点：
- 数组的扩容，做法是每次扩容原先长度的2倍
- 出栈后数组的变更，元素出栈后需要将之前的元素置空，便于
GC - 对数组越界问题的把握，只要涉及到获取元素的操作，都需要对下标进行是否越界判断，可以返回
null，也可以直接抛出异常，具体看个人
使用数组实现队列：
import java.util.Arrays;
import java.util.NoSuchElementException;
/**
* FIFO
*/
class Queue<E> {
private E[] _data;
private int _realLength;
private int _size;
@SuppressWarnings("unchecked")
public Queue(int initSize) {
this._data = (E[]) new Object[initSize];
this._size = initSize;
this._realLength = 0;
}
/**
* 默认数组长度为20
*/
public Queue() {
this(20);
}
/**
* 向队列尾端添加元素
*
* @param element 元素
*/
public void offer(E element) {
if (size() >= _size) {
grow();
}
_data[_realLength++] = element;
}
/**
* 取出队列头元素，并且从队列中删除它
*
* @return 头元素
*/
public E poll() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty");
}
E first = _data[0];
_data = Arrays.copyOfRange(_data, 1, _size);
_realLength--;
return first;
}
/**
* 取出队列头元素，但是不删除它
*
* @return 头元素
*/
public E element() {
if (isEmpty()) {
throw new NoSuchElementException("queue is empty");
}
return _data[0];
}
/**
* 判断队列是否为空
*
* @return true代表空队列
*/
public boolean isEmpty() {
return _realLength == 0;
}
/**
* 队列的大小
*
* @return 大小值
*/
public int size() {
return _realLength;
}
/**
* 数组的扩容，扩容大小为原先的2倍
*/
private void grow() {
// 扩容后size也要变化
_size = _size * 2;
_data = Arrays.copyOf(_data, _size);
}
public static void main(String[] args) {
Queue<Integer> queue = new Queue<Integer>();
queue.offer(0);
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("queue is empty: " + queue.isEmpty());
System.out.println("queue size is: " + queue.size());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
System.out.println("queue poll: " + queue.poll());
// queue is empty: false
// queue size is: 4
// queue poll: 0
// queue poll: 1
// queue poll: 2
// queue poll: 3
}
}
使用数组来实现队列相比较栈更加的容易，添加元素、判空和 size() 两者都相似，只是在出队列的时候做法与出栈不相同而已，出队列出的是头部元素，也就是最先添加的元素，出队列之后需要重新调整数组，使用系统提供的 Arrays.copyOfRange(_data, 1, _size) 可轻松的复制数组一段元素。
手写栈和队列不仅可以用数组来实现，也可以用链表来实现，用链表可以可以更好的控制添加和删除操作，毕竟链表采用的是指针方案。有兴趣的可以自行实现一波。
如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！
网友评论