数据结构与算法(2)：基于链表实现的栈结构Java代码实现

链表定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点：

• 由于不必须按顺序存储，链表在插入的时候可以达到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());
        }

    }

}