使用链表来实现栈比用数组更加方便,也易于节省空间,因为栈只能在栈顶进行操作,不需要进行随机访问栈元素
首先实现栈接口IStack,提供出栈、入栈、获取栈顶元素、判断是否为空以及清空栈等基本功能:
定义一个Node类,用于保存链中点的信息:
package my.stack; public class Node<T> { private T data; private Node<T> next; public Node(){ data = null; next = null; } public Node(T data){ this.data = data; this.next = null; } public Node(T data, Node<T> next){ this.data = data; this.next = next; } public void setData(T data){ this.data = data; } public T getData(){ return this.data; } public void setNext(Node<T> next){ this.next = next; } public Node<T> getNext(){ return this.next; } }
然后再实现该IStack接口;
package my.stack; public class LinkedStack<T> implements IStack<T> { private Node<T> top; private int size; public LinkedStack(){ this.top = null; this.size = 0; } public LinkedStack(T data){ this(); Node<T> node = new Node<T>(data); this.top = node; this.size ++; } @Override public void clear() { this.top = null; this.size = 0; } @Override public boolean isEmpty() { return this.top == null; } @Override public T peek() { return this.top.getData(); } @Override public T pop() { Node<T> oldTop = this.top; if(top == null){ return null; } this.top = this.top.getNext(); this.size --; return oldTop.getData(); } @Override public void push(T element) { Node<T> node = new Node<T>(element,top); this.top = node; this.size ++; } public int size(){ return this.size; } }
编写一个基本客户端用来测试功能是否满足,是否有明显的错误;
package my.stack; public class MyArrayStackClient { public static void main(String[] args) { ArrayStack<Integer> stack = new ArrayStack<Integer>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.isEmpty()); System.out.println(stack.peek()); // System.out.println(stack.pop()); System.out.println(stack.size()); stack.clear(); System.out.println(stack.size()); } }