Java基础 数据结构一【栈、队列】

什么是数据结构

数据结构是计算机科学中的一个重要概念，用于组织和存储数据以便有效地进行访问、操作和管理。它涉及了如何在计算机内存中组织数据，以便于在不同操作中进行查找、插入、删除等操作

数据结构可以看作是一种数据的组织方式，不同的数据结构适用于不同的应用场景，根据操作的需求和效率要求，选择合适的数据结构可以提高算法的执行效率。

1. 栈（Stack）

栈（Stack） 一种具有后进先出（LIFO）特性的数据结构，常用于处理函数调用、表达式求值等。

代码实现（Java）

import java.util.Arrays;
import java.util.Objects;public class Stack {private static final int DEFAULT_CAPACITY = 10;Object[] objects = new Object[DEFAULT_CAPACITY];int subscript = 0;/*** 将元素压入栈顶* 入栈* @param element 要压入的元素*/@Overridepublic void push(Object element) {ensureCapacity();objects[subscript] = element;subscript ++;}/*** 弹出栈顶元素并返回* 把栈顶元素删除，并返回* 出栈* @return 弹出的栈顶元素, 如果栈为空返回 null*/@Overridepublic Object pop() {if (subscript == 0) {return null;} else {Object obj = objects[--subscript];objects[subscript] = null;return obj;}}/*** 返回栈顶元素，但不弹出* @return 栈顶元素*/@Overridepublic Object peek() {return objects[subscript - 1];}/*** 检查栈是否为空* @return 如果栈为空则返回true，否则返回false*/@Overridepublic boolean isEmpty() {return subscript == 0;}/*** 返回栈中的元素个数* @return 栈中元素的个数*/@Overridepublic int size() {return subscript;}// 扩容private void ensureCapacity() {if (subscript == objects.length) {int newCapacity = objects.length * 2;objects = Arrays.copyOf(objects, newCapacity);}}@Overridepublic String toString() {Object[] tempArrays = new Object[subscript];System.arraycopy(objects, 0, tempArrays, 0, subscript);return Arrays.toString(tempArrays);}@Overridepublic boolean equals(Object obj) {if (obj == null || obj.getClass() != this.getClass()) {return false;}if (obj == this) {return true;}// 判断大小是否相等StackPractice other = (StackPractice) obj; // 对象类型匹配，进行类型转换if (other.size() != this.size()) {return false;}// 比较两个栈的底层数组是否相等。return Arrays.equals(this.objects, other.objects);}@Overridepublic int hashCode() {return Objects.hash(Arrays.hashCode(objects), subscript);}
}

2. 队列（Queue）

一种具有先进先出（FIFO）特性的数据结构，常用于任务调度、广度优先搜索等。

代码实现（Java）

import java.util.Arrays;
import java.util.Objects;public class QueuePractice extends Queue {private static final int DEFAULT_CAPACITY = 10;Object[] objects = new Object[DEFAULT_CAPACITY];int size = 0;/*** 将元素插入队尾* @param element 要插入的元素*/@Overridepublic void enqueue(Object element) {objects[size] = element;size ++;}/*** 移除并返回队首元素* 删除第一个元素，并返回* @return 队首元素, 如果队列为空时，返回 null*/@Overridepublic Object dequeue() {if (size == 0) {return null;} else {Object obj = objects[0];size --;System.arraycopy(objects, 1, objects, 0, size);return obj;}}/*** 返回队首元素，但不移除* @return 队首元素*/@OverrideObject peek() {return objects[0];}/*** 检查队列是否为空* @return 如果队列为空则返回true，否则返回false*/@Overrideboolean isEmpty() {return size == 0;}/*** 返回队列中的元素个数* @return 队列中元素的个数*/@Overrideint size() {return size;}@Overridepublic String toString() {Object[] tempArrays = new Object[size];System.arraycopy(objects, 0, tempArrays, 0, size);return Arrays.toString(tempArrays);}@Overridepublic boolean equals(Object obj) {if (obj == this) {return true;}if (obj == null || obj.getClass() != this.getClass()) {return false;}// 判断大小是否相等QueuePractice other = (QueuePractice) obj; // 对象类型匹配，进行类型转换if (other.size() != this.size()) {return false;}// 比较两个栈的底层数组是否相等。return Arrays.equals(this.objects, other.objects);}@Overridepublic int hashCode() {return Objects.hash(Arrays.hashCode(objects), size);}
}