目录结构

Stack接口

package LinkedListStack;public interface Stack<E> {int getSize();boolean isEmpty();void push(E e); //向栈中添加元素E pop();//向栈中取出元素E peek();//查看栈顶的元素
}

LinkedList类

package LinkedListStack;public class LinkedList<E> {//内部类private class Node {public E e;public Node next;//      用户传来e 和 nextpublic Node(E e, Node next) {this.e = e;this.next = next;}//      用户传来只传来epublic Node(E e) {this(e, null);}//      用户没有传任何参数public Node() {this(null, null);}@Overridepublic String toString() {return e.toString();}}//虚拟头结点private Node dummyhead;//记录链表中有多少个元素private int size;//对于一个空的链表来说 他是存在一个空的节点的，这个节点就是唯一的虚拟头结点public LinkedList() {dummyhead = new Node(null, null);size = 0;}//获取当前链表中元素的个数public int getSize() {return size;}//返回链表是否为空public boolean isEmpty() {return size == 0;}//在链表的index(0-based)位置添加新的元素epublic void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed. Illegal index");}Node prev = dummyhead;for (int i = 0; i < index; i++) {//prev一直向前移动  直到移动到index-1的位置prev = prev.next;}//新插入的node    prev.next = new Node(e, prev.next);  与下面三句话等价Node node = new Node(e);node.next = prev.next;prev.next = node;size++;}//在链表的头插入新的元素public void addFirst(E e) {add(0, e);}//在链表的尾插入新的元素public void addLast(E e) {add(size, e);}// 获得链表的第index(0-based)个位置的元素// 在链表中不是一个常用的操作public E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed. Illegal index");}Node cur = dummyhead.next;for (int i = 0; i < index; i++) {cur = cur.next;}return cur.e;}//获取列表的第一个元素public E getFirst() {return get(0);}//获取列表的最后一个元素public E getLast() {return get(size - 1);}// 修改链表的第index(0-based)个位置的元素为e// 在链表中不是一个常用的操作public void set(int index, E e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed. Illegal index");}Node cur = dummyhead.next;for (int i = 0; i < index; i++) {cur = cur.next;}cur.e = e;}// 查找链表中是否有元素epublic boolean contains(E e) {Node cur = dummyhead.next;while (cur != null) {if (cur.e.equals(e)) {return true;}cur = cur.next;}return false;}//从链表中删除index(0-based)位置的元素，返回删除的元素epublic E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed. Illegal index");}Node prev = dummyhead;for (int i = 0; i < index; i++) {prev = prev.next;}Node retNode = prev.next;prev.next = retNode.next;retNode.next= null;size--;return retNode.e;}public E removeFirst() {return remove(0);}public E removeLast() {return remove(size - 1);}@Overridepublic String toString() {StringBuffer res = new StringBuffer();Node cur = dummyhead.next;while (cur != null) {res.append(cur + "->");cur = cur.next;}//        与上面等价
//        for (Node cur = dummyhead.next; cur != null; cur = cur.next) {
//            res.append(cur + "->");
//        }res.append("NULL");return res.toString();}public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<Integer>();for (int i = 0; i < 5; i++) {linkedList.addFirst(i);System.out.println(linkedList);}linkedList.add(2,666);System.out.println(linkedList);linkedList.remove(2);System.out.println(linkedList);linkedList.removeFirst();System.out.println(linkedList);linkedList.removeLast();System.out.println(linkedList);}
}

具体实现类 LinkedListStack

package LinkedListStack;public class LinkedListStack<E> implements Stack<E> {private LinkedList<E> list;public LinkedListStack() {list = new LinkedList<E>();}@Overridepublic int getSize() {return list.getSize();}@Overridepublic boolean isEmpty() {return list.isEmpty();}@Overridepublic void push(E e) {list.addFirst(e);}@Overridepublic E pop() {return list.removeFirst();}@Overridepublic E peek() {return list.getFirst();}@Overridepublic String toString() {StringBuffer res = new StringBuffer();res.append("Stack: top ");res.append(list);return res.toString();}public static void main(String[] args) {LinkedListStack<Integer> stack = new LinkedListStack<Integer>();for (int i = 0; i < 5; i++) {stack.push(i);System.out.println(stack);}stack.pop();System.out.println(stack);}
}