如何用数组和链表实现栈

数据结构与算法

1.数组实现栈

栈，首先考虑比较厉害的泛型。不是简单的整数就可以了。数组一定要是Obejct[]创建，后面直接进行Cast就可以了。因为
T [] t=new T[length]；；不合法

class MyStack<T> {
    private Object[] items;
    public MyStack() {
        items = new Object[10];
    }
    public void push(T t) {
        if (isFull()) {
            int newLength = length() + 10;
            items = Arrays.copyOf(items, newLength);
        }
        for (int i = 0; i < items.length; i++) {
            if (items[i] == null) {
                items[i] = t;
                return;
            }
        }
    }
    public T pop() {
        T t;
        for (int i = items.length - 1; i >= 0; i--) {
            if (items[i] != null) {
                t = (T) items[i];
                items[i] = null;
                return t;
            }
        }
        return null;
    }
    public boolean empty() {
        if (items.length == 0) {
            return true;
        }
        return false;
    }
    public int search(T t) {
        for (int i = 0; i < items.length; i++) {
            if (items[i].equals(t)) {
                return i;
            }
        }
        return 0;
    }
    public int length() {
        return items.length;
    }
    private boolean isFull() {
        for (Object t : items) {
            if (t == null) {
                return false;
            }
        }
        return true;
    }
}

2.链表实现栈

链表泛型
栈泛型

class ListNode<T> {
    T data;
    ListNode<T> next;
    public ListNode(T data) {
        this.data = data;
    }
}
class MyStack<T> {
    private ListNode<T> top;
    public MyStack() {
        top = null;
    }
    public boolean isEmpty() {
        if (top == null) {
            return true;
        }
        return false;
    }
    public void push(T t) {
        ListNode<T> node = new ListNode<>(t);
        node.next = top;
        top = node;
    }
    public T pop() {
        T t = top.data;
        top = top.next;
        return t;
    }
    public T peek() {
        return top.data;
    }
}
public class Solution {
    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        stack.push(2);
        System.out.println(stack.isEmpty());
        stack.pop();
        System.out.println(stack.isEmpty());
    }
}

false
true
链表实现栈实在是太简单了