Java实现栈(链表实现)

发布于 2021-07-22  34 次阅读


栈和头插法的区别:

头插法是一个链表可以删除一个节点

Stack类代码如下:

package com.apesblog.Stack;

import java.util.Iterator;

public class Stack<T> implements Iterable<T> {
    private Node head;
    private int N;

    private class Node {
        private T item;
        private Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public Stack() {
        head = new Node(null, null);
        N = 0;
    }

    public void push(T t) {
        head.next = new Node(t, head.next);
        N++;
    }

    public T pop() {
        Node p = head.next;
        head.next = head.next.next;
        return p.item;
    }

    @Override
    public Iterator<T> iterator() {

        return new Iterator() {
            Node p = head;

            @Override
            public boolean hasNext() {
                return p.next != null;
            }

            @Override
            public Object next() {
                p = p.next;
                return p.item;
            }

        };
    }

}

测试类如下:

package com.apesblog.Stack;

public class Test {

    public static void main(String[] args) {
        Stack<String> l = new Stack<String>();
        l.push("1");
        l.push("2");
        l.push("3");

        StringBuilder str = new StringBuilder(300);
        str.append("遍历:");
        for (String s : l) {
            str.append(s + " ");
        }
        System.out.println(str);

        System.out.println("弾栈:" + l.pop());
        System.out.println("弾栈:" + l.pop());

    }

}

运行结果: