栈:这是一个先进后出的数据结构,生活中类似的浏览器的返回上一页就可以利用此结构实现,代码如下:
public class Stack<T> { private Object[] data;//存储数据 private int top;//表示栈顶元素 public Stack(){ data = new Object[100];//为了说明原理随意指定 top =-1; } public synchronized void put(T t){ //压栈 data[data.length] = t; top++; } public synchronized T pop(){ //出栈 if(top<0){ return null; } T t = (T) data[top]; top --; return t; } }
这只是我自己的 Java 实现只说明原理,但实际在java中是利用 vector 来存储数据的,我们知道vector其实是一个 线程安全 的ArrayList,而ArrayList的底层也是一个数组,所以原理上大同小异
队列:队列其实就是我们生活中的排队现象,先进入的先出,后进入的后出,代码实现如下:
public class Queue<T> {
private Object[] data; //存储数据
private int head; //头
private int tail ; //尾
public Queue(){
data = new Object[100];//为了说明原理随意指定
head =1;
tail =1;
}
public void put(T t){
data[tail] =t;
tail++;
}
public T get(){
T t =(T) data[head];
head ++;
return t;
}
}
如上所示,也只是说明原理,其实在java jdk中也有许多不同的对列,并且对列可以由数组实现,也可以由 链表 实现,下面介绍链表
链表是一个类似于现实中串项链的数据结构,前一个数据指向后一个数据,当然也可以后一个数据指向前一个数据,这就是 双向链表 ,这里不做讨论
public class MyNode<T> {
private Node <T> headNode ;
public MyNode(T t){
headNode = new Node<>(t,null);
}
public MyNode(){
}
private static class Node<E> {
Object e;
Node<E> next;
Node(E element, Node<E> next) {
this.e = element;
this.next = next;
}
}
public void put(T t){
if(headNode==null){
headNode = new Node<>(t,null);
}else {
headNode= new Node<>(t,headNode);
}
}
public T get(int index){
Node node = headNode;
for(int i=2;i<index;i++){
node= node.next;
}
T t = (T) node.e;
return t;
}
}
以上就是用Java实现的简单链表,还有双向链表是一个元素指向前一个元素和后一个元素,原理大概相同,这里可以看书链表中取固定位置的数据是非常麻烦的,必须从第一个开始依次查找,这也就是linklist不用for(int i=0;i++;i<size())遍历的原因,因为linklist的底层就是通过链表来实现的