本文来自真实面试题：能说一下栈的特性吗？栈一定得用数组才能实现吗？
答案：不一定，栈既可以用数组实现，也可以用链表实现。
下面贴上代码：
/**
* 实现一个栈，用数组。
* 也可以用链表
*/
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;
}
}
}
