数据结构——栈

一、栈的介绍

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 栈分顺序栈和链式栈。

栈的模型

二、代码实现

创建一个栈接口 public interface Stack<T> { // 进栈 boolean push(T data); // 出栈 T pop(); // 清空栈 void clear(); // 获取栈顶元素,但不出栈 T peek(); // 栈元素个数 int size(); // 判空 boolean isEmpty(); }

1. 以数组的形式来实现栈（顺序栈）

public class ArrayStack<T> implements Stack<T> { private Object[] toArray = {}; // 默认数组的容量 private static int DEFAULT_CAPACITY = 10; private static int size = 0; public ArrayStack() { this(DEFAULT_CAPACITY); } public ArrayStack(int capacity) { toArray = new Object[capacity]; } // 进栈 @Override public boolean push(T data) { if (size >= toArray.length) { System.out.println("栈满了，无法插入"); return false; } toArray[size++] = data; return true; } // 出栈 @Override public T pop() throws EmptyStackException { if (isEmpty()) { System.out.println("栈空了，无元素出栈"); throw new EmptyStackException(); } T data = (T) toArray[--size]; return data; } // 清栈 @Override public void clear() { for (int i = 0; i < toArray.length; i++) { toArray[i] = null; } size = 0; } // 返回栈顶元素，但不删除元素 @Override public T peek() { if (isEmpty()) { System.out.println("栈空了，无元素返回"); throw new EmptyStackException(); } T data = (T) toArray[size - 1]; return data; } // 栈中元素个数 @Override public int size() { // TODO Auto-generated method stub return size; } // 判空 @Override public boolean isEmpty() { if (size == 0) { return true; } return false; } }

2. 以链表的形式实现栈（链表栈）

public class LinkStack<T> implements Stack<T> { /* 栈顶指针 */ private Node<T> top; private int size;// 栈的大小 public LinkStack() { top = null; size = 0; } @Override public boolean push(T data) { Node<T> node = new Node<T>(); node.data = data; node.prev = node; top = node;// 改变栈顶指针 size++; return true; } @Override public T pop() { if (top != null) { T data = top.data; top = top.prev; size--; return data; } return null; } @Override public void clear() { top = null; size = 0; } @Override public T peek() { if(top!=null){ return top.data; } return null; } @Override public int size() { // TODO Auto-generated method stub return size; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size == 0; } private static class Node<T> { T data; Node<T> prev; } }

运行主程序

public static void main(String[] args) { ArrayStack<String> arrayStack = new ArrayStack<String>(); arrayStack.push("hello"); arrayStack.push("world"); arrayStack.push("java"); arrayStack.push("android"); arrayStack.pop(); System.out.println("ArrayStack-" + arrayStack.peek()); System.out.println("ArrayStack-" + arrayStack.size()); arrayStack.clear(); System.out.println("ArrayStack-" + arrayStack.size()); LinkStack<String> linkStack = new LinkStack<String>(); linkStack.push("hello"); linkStack.push("world"); linkStack.push("java"); linkStack.push("android"); System.out.println("LinkStack-" + linkStack.size()); System.out.println("LinkStack-" + linkStack.peek()); linkStack.pop(); System.out.println("LinkStack-" + linkStack.size()); }

运行结果

三、总结

      上面分别介绍了顺序栈和链栈。对于顺序栈和链栈，它们时间复杂度都是一样，那么空间复杂度呢？对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题。       顺序栈的优势是存取时定位很方便。而链栈则要求每个元素都有指针域，这也会增加了一些内存开销，但栈的长度就可以无限制了。       如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。