链表
还不明白再来一张图
代码实现:
写链表首先要封装一个保存数据和引用的节点,我们俗称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];
}
/**
* 1. 压栈
* 2. 弹栈
* 3.判断是否是空栈
* 4. 当前栈中是否是满栈
*/
// 判断是否已经满栈
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<stack.length;i++){
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
/**
* 获取栈中元素存在的个数
*/
public int length(){
return this.top+1;
}
}
需求:使用栈判断数据是否是回文数据
public class TestApp {
public static void main(String[] args) {
/**
* 回文数据
* 回文: aba, racecar 意思就是从左往右和从右往左是一样的数据称之为回文数据
* 需求: 通过上面以数组模拟栈来判断一个字符串是否是一个回文数据
*
*/
delecation("hello");
delecation("aba");
}
public static boolean delecation(String val){
/**
* 初始化栈对向、象
*/
ArrayStack arrayStack = new ArrayStack(10);
// 获取传递进来的字符串的长度
int length = val.length();
for (int i = 0; i <length ; i++) {
arrayStack.push(val.charAt(i));
}
/**
* 获取弹出来的数据
*/
String newVal = "";
int length1 = arrayStack.length();
for (int i = 0; i <length1; 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());
}
}