题解 | #【模板】链表#

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    
    // 数组实现链表
    static void solve2() {
        int n = sc.nextInt();
        sc.nextLine();
        ArrayStack<Integer> stack = new ArrayStack<Integer>();
        while (n-- > 0) {
            String s = sc.nextLine();
            String arr[] = s.split(" ");
            if (arr[0].equals("push")) {
                stack.push(Integer.parseInt(arr[1]));
            } else if (arr[0].equals("pop")) {
                Integer pop = stack.pop();
                if (pop == null) {
                    System.out.println("error");
                } else {
                    System.out.println(pop);
                }
            } else if (arr[0].equals("top")) {
                Integer top = stack.top();
                if (top == null) {
                    System.out.println("error");
                } else {
                    System.out.println(top);
                }
            }
        }
    }
    
    // 链表实现栈的写法
    static void solve() {
        int n = sc.nextInt();
        sc.nextLine();
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        while (n-- > 0) {
            String s = sc.nextLine();
            String arr[] = s.split(" ");
            if (arr[0].equals("push")) {
                stack.push(Integer.parseInt(arr[1]));
            } else if (arr[0].equals("pop")) {
                Integer pop = stack.pop();
                if (pop == null) {
                    System.out.println("error");
                } else {
                    System.out.println(pop);
                }
            } else if (arr[0].equals("top")) {
                Integer top = stack.top();
                if (top == null) {
                    System.out.println("error");
                } else {
                    System.out.println(top);
                }
            }
        }
    }
    public static void main(String[] args) {
        solve();
//         solve2();
    }
}

/////////////////////数组
/**
 * 栈的实现 -- 数组
 * 优点: 一个元素占用一个储存空间
 * 缺点: 初始化申请储存空间太大, 会造成空间的浪费, 初始化申请的储存空间太小, 后期会经常需要对数组扩容, 从而导致性能的下降.
 */
/**
 * 栈的实现 -- 数组
 * 优点: 一个元素占用一个储存空间
 * 缺点: 初始化申请储存空间太大, 会造成空间的浪费, 初始化申请的储存空间太小, 后期会经常需要对数组扩容, 从而导致性能的下降.
 */
/**
 * 使用泛型，以便栈中能够存储我们想要的数据
 * 基于数组的栈实现
 * */
class ArrayStack<E> {

    private Object[] stack;
    private int size;		//栈中元素的个数
    public ArrayStack() {
        stack = new Object[10];	//初始长度为10
    }

    //判断栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回栈顶的一个元素，但是不进行出栈操作
     * */
    public E top() {
        if(isEmpty()) {
            return null;
        }
        return (E)stack[size -1];		//返回栈顶元素
    }

    public E pop() {
        E e = top();					//取得栈顶数据
        if(size > 0) {					//检查栈中是否有数据
            stack[size - 1] = null;			//将出栈后的位置置为空
            size--;
        }
        //将栈中元素个数减一
        return e;
    }

    public E push(E item) {
        ensureCapacity(size + 1);
        stack[size++] = item;
        return item;

    }

    /**
     * 当栈满的时候，对栈进行扩容
     * */
    private void ensureCapacity(int size) {
        int len = stack.length;
        if(size > len) {		//数组已满
            int newLen = 10;	//每次数组扩充的容量
            stack = Arrays.copyOf(stack, newLen);
        }
    }

    /**
     * 打印出栈中所有的数据
     * */
    public void printStack() {
        System.out.println("开始进行出栈：");
        while(size > 0) {
            System.out.println("出栈：" + pop());
        }
        System.out.println("出栈操作结束！");

    }

}
/////////////////////数组


/////////////////////链表
/**
 * 栈的实现 -- 链表
 * 优点: 使用灵活方便, 只要有需要的时候才会申请空间
 * 缺点: 除了要存储元素外, 还需要额外存储指针(引用)信息
 * @param <T>
 */
class Node<T> {
    T data;
    Node<T> next;
}

class LinkedListStack<T> {
    private Node<T> pHead;

    public LinkedListStack() {
        pHead = new Node<T>();
        pHead.data = null;
        pHead.next = null;
    }

    public int size() {
        int size = 0;
        Node<T> cur = pHead.next;

        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }


    public T pop() {
        Node<T> popNode = pHead.next;
        if (popNode == null) return null;
        pHead.next = popNode.next;
        return popNode.data;
    }

    public T top() {
        Node<T> topNode = pHead.next;
        if (topNode == null) return null;
        return topNode.data;
    }

    public void push(T e) {
        Node<T> tlNode = new Node<>();
        tlNode.data = e;
        tlNode.next = pHead.next;
        pHead.next = tlNode;
    }

    public boolean isEmpty() {
        return pHead.next == null;
    }


}
/////////////////////链表