java 自己实现 栈 demo (链表存储)

Java

2017-07-06

39

0

技术:java8

运行环境:IDEA 15.2 + jdk8 + windows 10

demo功能:java 自己实现 栈 demo (链表存储)

源代码

http://git.oschina.net/youlixishi/demo-world/blob/master/src/algorithm/binary-search/src/main/java/com/demoworld/JLinkedListStack.java

 

public class JLinkedListStack implements IStack {
    public JLinkedListStack() {
        tail = null;
        head = null;
    }

    @Override
    public void push(int n) {
        JLinkedListStackNode node = new JLinkedListStackNode();
        node.value = n;
        if (this.isEmpty()) {//添加第一个元素
            tail = node;
            head = node;
            return;
        }
        if (head == tail) {//添加第二个元素
            head.next = node;
            tail = node;
            return;
        }
        tail.next = node;//添加第三个元素及以上
        tail = node;
    }

    @Override
    public int pop() {
        if (this.isEmpty()) {
            return -1;//为了测试, 在push时 不要push -1
        }
        int n = tail.value;
        if (head == tail) {
            tail = null;
            head = null;
        } else {
            JLinkedListStackNode tmpPreNode = findPreNode(tail);
            tail = tmpPreNode;
        }
        return n;
    }
   //查找node元素前一个元素, 如果使用双向链表就不用查找了
    private JLinkedListStackNode findPreNode(JLinkedListStackNode node) {
        if (this.isEmpty()) {
            return null;
        }

        JLinkedListStackNode tmpNode = head;
        boolean hasFound = false;
        while (true) {
            if (tmpNode.next == null) {
                tmpNode = null;
                break;
            }
            if (tmpNode.next == node) {
                hasFound = true;
                break;
            }
            tmpNode = tmpNode.next;
        }
        return tmpNode;
    }

    @Override
    public boolean isEmpty() {
        return (tail == null && head == null);
    }

    public JLinkedListStackNode tail;
    public JLinkedListStackNode head;
}

测试类

public class JLinkedListStackTest {
    //正常的 push pop
    @Test
    public void test1() {
        JLinkedListStack j = new JLinkedListStack();
        for (int i = 1; i <= 2; i++) {
            j.push(i);
        }

        while (!j.isEmpty()) {
            System.out.println(j.pop());
        }
    }

    //超过最长长度
    @Test
    public void test2() {
        JLinkedListStack j = new JLinkedListStack();
        for (int i = 1; i <= 10; i++) {
            j.push(i);
            if (i == 5) {
                System.out.println(j.pop());
            }
        }

        while (!j.isEmpty()) {
            System.out.println(j.pop());
        }
    }

    //push pop混合操作
    @Test
    public void test3() {
        JLinkedListStack j = new JLinkedListStack();
        for (int i = 1; i <= 10; i++) {
            j.push(i);
            if (i == 5) {
                System.out.println(j.pop());
                j.push(12);
            }
        }

        while (!j.isEmpty()) {
            System.out.println(j.pop());
        }
    }
}

欢迎添加微信,互相学习↑↑↑ -_-

发表评论

全部评论:0条

白老虎

programming is not only to solve problems, ways to think