数据结构的Java实现——栈和队列时间:2022-06-06 17:38:17栈(Stack)作为一个先进后出(FILO) 的线性结构,只支持在栈顶的插入和弹出。 队列(Queue)作为一个先进先出(FIFO) 的线性结构,支持在队首获取元素,在对尾插入元素。 栈的实现: package ds.linerlist; /** * 栈的实现 * @param <E> * @author <a href="mailto:bao.yiming@live.cn" mce_href="mailto:bao.yiming@live.cn">Bao Yiming</a> */ public class Stack<E> { private Object[] data = null; private int capacity; // capacity: 栈的容量 private int top; // top: 栈顶指针 Stack() { this(10); } /** * 初始化栈,声明保存数据的数组大小。 * @param initialSize 栈的初始化大小 */ Stack(int initialSize) { if (initialSize >= 0) { this.capacity = initialSize; data = new Object[initialSize]; top = 0; } else { throw new RuntimeException("初始化大小不能小于0:" + initialSize); } } /** * 判断栈是否为空 * @return */ boolean empty() { return top == 0 ? true : false; } /** * 获取栈顶元素的内容,但是不弹出 * @return */ E peek() { return (E) data[top - 1]; } /** * 弹出栈顶元素 * @return */ E pop() { E e = (E) data[top - 1]; --top; return e; } /** * 在栈顶插入元素 * @param e 待插入的元素 * @return */ boolean push(E e) { ensureCapacity(); data[top] = e; ++top; return true; } /** * 检查存储数据的数组容量,如果数组已经满,则扩充容量;否则不操作。 */ private void ensureCapacity() { int index; if (top == capacity) { capacity *= 2; Object[] newData = new Object[capacity]; for (index = 0; index < top; ++index) { newData[index] = data[index]; } data = newData; } } @Override public String toString() { String str = ""; for (int index = 0; index <= top - 1; ++index) { str += (data[index] + " "); } return str; } } 队列的实现 package ds.linerlist; /** * 队列的实现 * @param <E> * @author <a href="mailto:bao.yiming@live.cn" mce_href="mailto:bao.yiming@live.cn">Bao Yiming</a> */ public class Queue<E> { Object[] data = null; private int capacity; // capacity: 队的容量 private int tail; // tail: 队尾指针 /** * 初始化为声明大小,则设置为10。 */ Queue() { this(10); } /** * 初始化队列,声明保存数据的数组大小。 * @param initialSize 队列的初始化大小 */ Queue(int initialSize) { if (initialSize >= 0) { this.capacity = initialSize; data = new Object[initialSize]; tail = 0; } else { throw new RuntimeException("初始化大小不能小于0:" + initialSize); } } /** * 判断队列是否为空 * @return */ public boolean empty() { return tail == 0 ? true : false; } /** * 在队尾插入元素 * @param e 待插入的元素 * @return */ public boolean add(E e) { ensureCapacity(); data[tail] = e; ++tail; return true; } /** * 获取队首的元素内容,但不将该元素出队。 * @return */ public E peek() { return (E) data[0]; } /** * 将队首元素出队。 * @return */ public E poll() { E e = (E) data[0]; for (int index = 1; index < tail; ++index) { data[index - 1] = data[index]; } data[tail - 1] = null; --tail; return e; } /** * 检查存储数据的数组容量,如果数组已经满,则扩充容量;否则不操作。 */ private void ensureCapacity() { int index; if (tail == capacity) { capacity *= 2; Object[] newData = new Object[capacity]; for (index = 0; index < tail; ++index) { newData[index] = data[index]; } data = newData; } } @Override public String toString() { String str = ""; for (int index = 0; index < tail; ++index) { if (data[index] != null) { str += (data[index] + " "); } } return str; } }