链表定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的特点：
- 由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多。
- 查找一个节点或者访问特定编号的节点则需要O(n)的时间
- 综上，插入速度快，查找速度慢。
- 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间。
链表的实现：
链表有很多种不同的类型：单向链表，双向链表以及循环链表。
本文代码实现：Java代码
- 通过内部类定义了一个单向链表。
- 以链表为底层结构，实现了一个栈结构。
栈接口定义：
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 8:40
* 栈结构定义，定义了基本的6种操作
*/
public interface FlowerStack<T> {
/**
* 压栈
* @param item
*/
void push(T item);
/**
* 出栈
* @return
*/
T pop();
/**
* 栈的大小
* @return
*/
int size();
/**
* 栈是否为空
* @return
*/
boolean isEmpty();
/**
* 生成迭代器
*/
Iterator<T> iterator();
}
栈实现类代码：
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 19:12
* 基于链表的栈结构
*/
public class FlowerLinkedStack<T> implements FlowerStack<T> {
private Node<T> first; // 栈顶节点
private int length; // 元素数量
// 定义一个内部类, 作为链表结构
private class Node<T> {
T item;
Node next;
}
@Override
public void push(T item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
length++;
}
@Override
public T pop() {
if (first == null) {
return null;
}
T item = first.item;
first = first.next;
length--;
return item;
}
@Override
public int size() {
return length;
}
@Override
public boolean isEmpty() {
return first == null;
}
@Override
public Iterator<T> iterator() {
return new FlowerLinkedStackIterator<T>();
}
/**
* 定义一个迭代器
* @param <K>
*/
private class FlowerLinkedStackIterator<K> implements Iterator<K> {
private Node it = first;
@Override
public boolean hasNext() {
return it != null;
}
@Override
public K next() {
K next = (K) it.item;
it = it.next;
return next;
}
@Override
public void remove() {
}
}
}
测试用例代码：
import org.junit.Test;
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 19:27
* 链表实现的栈结构 测试用例
*/
public class FlowerLinkedStackTest {
@Test
public void test() {
FlowerLinkedStack<Integer> stack = new FlowerLinkedStack();
System.out.println("初始尺寸：" + stack.size());
System.out.println("是否为空" + stack.isEmpty());
System.out.println(stack.pop());
for(int i=0; i<20; i++) {
stack.push(i);
System.out.println("当前尺寸：" + stack.size());
System.out.println("是否为空" + stack.isEmpty());
}
System.out.println("-----------------------------------------");
Iterator<Integer> iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("----------------------------------------");
for(int i=0; i<30; i++) {
System.out.println(stack.pop());
System.out.println("当前尺寸：" + stack.size());
System.out.println("是否为空" + stack.isEmpty());
}
}
}
