栈一定得用数组实现吗？

本文来自真实面试题：能说一下栈的特性吗？栈一定得用数组才能实现吗？

答案：不一定，栈既可以用数组实现，也可以用链表实现。

下面贴上代码：

/**
 * 实现一个栈，用数组。
 * 也可以用链表
 */
public class ArrayStack {

    private String[] items; // 栈
    private int count; // 目前栈中元素个数
    private int n; // 元素总数

    public ArrayStack(int n) {
        this.count = 0;
        items = new String[n];
        this.n = n;
    }

    // 入栈操作
    public boolean push(String item) {
        if(count == n) return false;
        items[count++] = item;
        return true;
    }

    // 出栈操作
    public String pop() {
        if(count == 0) return null;
        return items[--count];

    }

    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(3);
        arrayStack.push("1");
        arrayStack.push("2");
        arrayStack.push("3");
        System.out.println(arrayStack.push("4"));
        System.out.println(arrayStack.pop());
    }
}

/**
 * 基于链表实现的栈，栈长不限制
 */
public class LinkedListStack {
    private Node head = null;

    public boolean push(int  item) {
        Node newNode = new Node(item, null);
        if (head == null) {
            head = newNode;
        }

        newNode.next = head;
        head =  newNode;
        return true;
    }
    public int pop() {
        if(head ==null) return -1; // 栈为空时，返回 -1
        int res = head.data;
        head = head.next;
        return res;
    }



    private static class Node{

        private Node next;
        private int data;

        public Node(int data, Node next ) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }

    }

}