链表
- 在内存空间中，数组和链表都是基本的数据结构，都是【表】，或者叫【线性表】。
- 线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点，说人话，就是有头有尾一条线。
还不明白再来一张图
代码实现：
写链表首先要封装一个保存数据和引用的节点，我们俗称node
public class Node {
// 数据
private Integer data;
// 该节点的下一个节点
private Node next;
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class SuperLinked {
// 链表的长度
private int size;
// 维护一个头节点
private Node first;
// 维护一个尾节点
private Node last;
// 无参构造器
public SuperLinked(){
}
//添加元素至链表尾部
public boolean add(Integer data){
Node node = new Node(data,null);
if (first == null){
first = node;
} else {
last.setNext(node);
}
last = node;
size++;
return true;
}
//在指定下标添加元素
public boolean add(int index,Integer data){
Node node = getNode(index);
Node newNode = new Node(data,null);
if (node != null){
newNode.setNext(node.getNext());
node.setNext(newNode);
} else {
first = newNode;
last = newNode;
}
size++;
return true;
}
// 删除头元素
public boolean remove(){
if (size < 0){
return false;
}
if (first != null ){
first = first.getNext();
size--;
}
return true;
}
// 删除指定元素
public boolean remove(int index){
if (size < 0){
return false;
}
if(size == 1){
first = null;
last = null;
} else {
Node node = getNode(index-1);
node.setNext(node.getNext().getNext());
}
size--;
return true;
}
// 修改指定下标的元素
public boolean set(int index,Integer data){
// 找到第index个
Node node = getNode(index);
node.setData(data);
return true;
}
// 获取指定下标的元素
public Integer get(int index){
return getNode(index).getData();
}
//查看当前有多少个数字
public int size(){
return size;
}
//添加元素
private Node getNode(int index){
// 边界判断
if(index <= 0){
index = 0;
}
if(index >= size-1){
index = size-1;
}
// 找到第index个
Node cursor = first;
for (int i = 0; i < index; i++) {
cursor = cursor.getNext();
}
return cursor;
}
public static void main(String[] args) {
SuperLinked linked = new SuperLinked();
linked.add(1);
linked.add(2);
linked.add(4);
linked.add(6);
linked.add(3);
linked.add(2);
linked.add(7);
linked.add(6);
linked.remove();
linked.remove(2);
linked.set(0,3);
for (int i = 0; i < linked.size(); i++) {
System.out.println(linked.get(i));
}
}
}
封装一个栈和队列
栈（Stack）和队列（Queue）是两种操作受限的线性表。
这种受限表现在：栈的插入和删除操作只允许在表的尾端进行（在栈中成为“栈顶”），满足“FILO：First In Last Out”；队列只允许在表尾插入数据元素，在表头删除数据元素,满足“First In First Out”。
栈与队列的相同点：
- 都是线性结构。
- 插入操作都是限定在表尾进行。
- 都可以通过顺序结构和链式结构实现。、
栈与队列的不同点：
- 队列先进先出，栈先进后出。
栈
public class ArrayStack {
// 栈大小
private int maxStack;
// 数组用来模拟栈
private int[] stack;
// 表示栈顶所在的位置，默认情况下如果没有数据时，使用-1
private int top;
public ArrayStack(int maxStack){
this.maxStack = maxStack;
stack = new int[maxStack];
}
// 判断是否已经满栈
public boolean isFull(){
return this.top == this.maxStack-1;
}
// 判断是否是空栈
public boolean isEmpty(){
return this.top == -1;
}
public void push(int val){
// 是否已经满栈
if (isFull()){
throw new RuntimeException("栈已经满了");
}
top++;
stack[top] = val;
}
public int pop(){
// 如果栈中时空
if (isEmpty()){
throw new RuntimeException("空栈，未找到数据");
}
int value = stack[top];
top--;
return value;
}
public void list(){
//是否是空栈
if (isEmpty()){
throw new RuntimeException("空栈，未找到数据");
}
for (int i = 0;i
System.out.printf("stack[%d]=%dn",i,stack[i]);
}
}
public int length(){
return this.top+1;
}
}
需求:使用栈判断数据是否是回文数据
public class TestApp {
public static void main(String[] args) {
delecation("hello");
delecation("aba");
}
public static boolean delecation(String val){
ArrayStack arrayStack = new ArrayStack(10);
// 获取传递进来的字符串的长度
int length = val.length();
for (int i = 0; i
arrayStack.push(val.charAt(i));
}
String newVal = "";
int length1 = arrayStack.length();
for (int i = 0; i
// 如果不是一个空栈
if (!arrayStack.isEmpty()){
char pop =(char) arrayStack.pop();
newVal = newVal+pop;
}
}
if (val.equals(newVal)){
return true;
}
return false;
}
}
队列
public class Queue {
private SuperLinked superLinked = new SuperLinked();
// 出队的方法
public Integer poll(){
if(empty()){
return null;
}
Integer integer = superLinked.get(0);
superLinked.remove();
return integer;
}
// 返回队首，不出队
public Integer peek(){
if(empty()){
return null;
}
return superLinked.get(0);
}
// 入队的方法
public void add(Integer item){
superLinked.add(item);
}
// 判断这个队列是否为空
public boolean empty(){
return superLinked.size() == 0;
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
