常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
栈概念
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出的原理运作。
栈可以用顺序表实现，也可以用链表实现。
栈的操作
Stack() 创建一个新的空栈
push(element) 添加一个新的元素element到栈顶
pop() 取出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数
实现类：
package mystack; public class MyStack { //栈的底层使用数组来存储数据 //private int[] elements; int[] elements; //测试时使用 public MyStack() { elements = new int[0]; } //添加元素 public void push(int element) { //创建一个新的数组 int[] newArr = new int[elements.length + 1]; //把原数组中的元素复制到新数组中 for (int i = 0; i < elements.length; i++) { newArr[i] = elements[i]; } //把添加的元素放入新数组中 newArr[elements.length] = element; //使用新数组替换旧数组 elements = newArr; } //取出栈顶元素 public int pop() { //当栈中没有元素 if (is_empty()) { throw new RuntimeException("栈空"); } //取出数组的最后一个元素 int element = elements[elements.length - 1]; //创建一个新数组 int[] newArr = new int[elements.length - 1]; //原数组中除了最后一个元素其他元素放入新数组 for (int i = 0; i < elements.length - 1; i++) { newArr[i] = elements[i]; } elements = newArr; return element; } //查看栈顶元素 public int peek() { return elements[elements.length - 1]; } //判断栈是否为空 public boolean is_empty() { return elements.length == 0; } //查看栈的元素个数 public int size() { return elements.length; } }
测试类：
package mystack; public class Demo { public static void main(String[] args) { MyStack ms = new MyStack(); //添加元素 ms.push(9); ms.push(8); ms.push(7); //取出栈顶元素 // System.out.println(ms.pop()); //7 // System.out.println(ms.pop()); //8 // System.out.println(ms.pop()); //9 //查看栈顶元素 System.out.println(ms.peek()); //7 System.out.println(ms.peek()); //7 //查看栈中元素个数 System.out.println(ms.size()); //3 } }
