数组实现栈

栈接口

public interface Stack<E> {int getSize();boolean isEmpty();void push(E e);E pop();E peek();}

实现类

//用数组实现栈public class ArrayStackDemo {public static void main(String[] args) {ArrayStack stack = new ArrayStack(5);stack.push(1);stack.push(4);stack.push(6);stack.push(3);stack.traverse();System.out.println("出栈的元素为"+stack.pop());stack.traverse();}}class ArrayStack implements Stack<Integer>{public int maxSize;//栈的最大长度public int[] stack;public int top = -1;//栈顶public ArrayStack() {}public ArrayStack(int maxSize) {this.maxSize = maxSize;stack=new int[this.maxSize];}@Overridepublic int getSize() {return stack.length;}@Overridepublic boolean isEmpty() {return top==-1;}@Overridepublic void push(Integer value) {if (isFull()){System.out.println("栈满！");return;}top++;stack[top]=value;}public boolean isFull(){return top==maxSize-1;}@Overridepublic Integer pop() {if (isEmpty()){throw new RuntimeException("栈空，无法取出数据！");}int value = stack[top];top--;return value;}@Overridepublic Integer peek() {//返回栈顶的值return stack[top];}public void traverse(){if (isEmpty()){System.out.println("栈空，无法取出数据！");return;}for (int i = top; i >=0 ; i--) {System.out.println("stack["+i+"]"+"="+stack[i]);}}}

用链表实现栈

public interface Stack<E> {int getSize();boolean isEmpty();void push(E e);E pop();E peek();}

//用链表实现栈public class LinkedListStackDemo {//测试public static void main(String[] args) {LinkedListStack<Integer> stack = new LinkedListStack<>();for(int i = 0 ; i < 5 ; i ++){stack.push(i);System.out.println(stack);}stack.pop();System.out.println(stack);}}class LinkedListStack<E> implements Stack<E> {private LinkedList<E> list;public LinkedListStack(){list = new LinkedList<>();}@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(){StringBuilder res = new StringBuilder();res.append("Stack: top ");res.append(list);return res.toString();}}class LinkedList<E> {private class Node{public E e;public Node next;public Node(E e, Node next){this.e = e;this.next = next;}public 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();size = 0;}// 获取链表中的元素个数public int getSize(){return size;}// 返回链表是否为空public boolean isEmpty(){return size == 0;}// 在链表的index(0-based)位置添加新的元素e// 在链表中不是一个常用的操作，练习用：）public 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 = prev.next;prev.next = new Node(e, prev.next);size ++;}// 在链表头添加新的元素epublic void addFirst(E e){add(0, e);}// 在链表末尾添加新的元素epublic 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("Update 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)位置的元素, 返回删除的元素// 在链表中不是一个常用的操作，练习用：）public E remove(int index){if(index < 0 || index >= size)throw new IllegalArgumentException("Remove failed. Index is illegal.");// E ret = findNode(index).e; // 两次遍历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);}// 从链表中删除元素epublic void removeElement(E e){Node prev = dummyHead;while(prev.next != null){if(prev.next.e.equals(e))break;prev = prev.next;}if(prev.next != null){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;}}@Overridepublic String toString(){StringBuilder res = new StringBuilder();Node cur = dummyHead.next;while(cur != null){res.append(cur + "->");cur = cur.next;}res.append("NULL");return res.toString();}}