一、什么是表
- 表是一种集合，一个表有一个大小，同时还有一些操作，比如插入、删除、遍历一个表、查找表中某一个位置的元素等
- 表中某个元素的前一个元素叫做前驱，后一个元素叫做后继
- 表的实现：首先用数组实现是不可行的，因为假如删除或者插入一个给定数组的第一个元素的做法是将所有元素往前或往后迁移一个位置，这中最坏情况时间复杂度为O(N)。因为插入和删除的运行时间太慢以及表的大小必须已知，所以简单数组不用实现表这种结构，这种时候我们要考虑链表
二、链表
链表解释网上有很多，这里只列出实现代码
1. 数据结构
package com.shan.list;
/**
* 链表的Node节点数据结构
*/
public class Node {
private int element;
private Node next;
public Node() {}
public Node(int element) {
this.element = element;
}
public int getElement() {
return element;
}
public void setElement(int element) {
this.element = element;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
2. 链表的实现，使用了表头
package com.shan.list;
/**
* 链表的实现
* 包括链表的方法，总体上使用了标头(headNode)
*/
public class LinkedList {
public Node headNode;
public LinkedList(){
this.headNode = new Node();
}
/**
* 判断是否为空
* @return
*/
public boolean isEmpty() {
return headNode.getNext() == null;
}
public boolean isLast(Node nowNode) {
return nowNode.getNext() == null;
}
/**
* 根据element找到相应的Node
* @param element
* @return
*/
public Node findByElement(int element) {
Node nowNode = headNode.getNext();
while(nowNode != null && nowNode.getElement() != element) {
nowNode = nowNode.getNext();
}
return nowNode;
}
/**
* 查找ele的前一个Node
* 若没找到则返回最后一个Node
* @param element
* @return
*/
public Node findPreviousByElement(int element) {
Node nowNode = headNode;
while(nowNode.getNext()!=null && nowNode.getNext().getElement()!=element) {
nowNode = nowNode.getNext();
}
return nowNode;
}
/**
* 删除指定ele的node
* @param element
*/
public void delete(int element) {
Node preNode = findPreviousByElement(element);
if(!isLast(preNode)) {
Node tempNode = preNode.getNext();
preNode.setNext(tempNode.getNext());
tempNode.setNext(null);
}
}
/**
* 在指定node后插入新元素
* @param element
* @param positionNode
*/
public void insert(int element, Node positionNode) {
Node newNode = new Node(element);
newNode.setNext(positionNode.getNext());
positionNode.setNext(newNode);
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
System.out.println(list.isEmpty());
}
}
三、栈(后进先出)
- 栈是一种表，链表和数组都能实现栈
1. 链表实现
- Stack类有唯一成员变量stackHead，用于栈头，stackHead的下一个元素才是栈顶元素
- 所有操作为常数时间
package com.shan.list;
// 用链表实现的栈
public class StackWithLinkedList {
private Node stackHead;
public StackWithLinkedList() {
Node head = new Node();
this.stackHead = head;
}
public StackWithLinkedList(Node stackHead ) {
this.stackHead = stackHead;
}
public boolean isEmpty() {
return stackHead.getNext() == null;
}
public int pop() {
if(isEmpty()) {
System.out.println("Stack 空了！");
return -1;
}else {
Node topNode = stackHead.getNext();
stackHead.setNext(topNode.getNext());
topNode.setNext(null);
return topNode.getElement();
}
}
public void push(int newEle) {
Node newNode = new Node(newEle);
newNode.setNext(stackHead.getNext());
stackHead.setNext(newNode);
}
}
2. 数组方式实现
- 更流行，唯一潜在危险是需要提前声明作为栈的数组的大小
- 大小固定, 日常使用中以足够使用
- 使用数组实现比链表还要简单，就不贴代码了
3. 栈的应用(之后做题再贴代码)
- 计算后缀表达式
- 中缀到后缀的转换
