本文共 9423 字，大约阅读时间需要 31 分钟。
栈这个数据结构相对简单，它是一种“先进后出”（First In Last Out，FILO）的数据结构，即操作数据的进出只能在一端进行，所以从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
栈的实现可以用数组来实现，此时属于顺序栈，同时可以增加动态扩容的属性。如果使用链表实现，此时是链式栈，无需要进行扩容，因为链表不需要设置容量，只要内存中有空间，就可以进行申请。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
栈的应用很广泛，一般讲栈的文章都给出浏览器的例子，浏览网页时，每次开启一个链接都会将这个网页进行入栈操作，当你想回退到历史页面时，就会执行出栈操作，这样就能查看栈顶的网页了，这里留一个疑问，大家都知道，网页不但有后退键，还有前进键，那么前进的操作是怎么实现的，可以思考下。
还有 JVM 在执行函数时，也是使用栈这个数据结构来进行的，每次调用一个函数，就是一个栈帧，会执行入栈操作，然后 JVM 的执行引擎执行时，从栈中出栈一个一个的栈帧，逐个执行，这就完成函数的调用过程。
还有 Android 中的任务栈，每次开启一个 Activity（这里假设是 Standard 模式），都会执行入栈操作，上面的 Activity 销毁后，就会出栈，然后下面的 Activity 就显示出来了。
所有栈这种数据结构很常见，那么我们自己也来实现一个简单，本篇先来实现顺序栈，使用数组来实现，链式栈，等我们学习链表后再实现一下。
(1)栈实现
public class RStack{ private static final int DEFAULT_CAPACITY = 10; private int size = 0; private T[] elements; public RStack() { this(DEFAULT_CAPACITY); } @SuppressWarnings("unchecked") public RStack(int capacity) { if (capacity < 1) { capacity = DEFAULT_CAPACITY; } Object[] objs = new Object[capacity]; elements = (T[]) objs; } public T pop() { checkIsValid(); if (isEmpty()) { return null; } T data = elements[size - 1]; elements[size - 1] = null; size--; return data; } public boolean push(T t) { if (isFull()) { return false; } elements[size] = t; size++; return true; } public T peek() { checkIsValid(); if (isEmpty()) { return null; } return elements[size - 1]; } public boolean pushExt(T t) { checkIsValid(); if (!isFull()){ return push(t); } ensureCapacity(elements.length * 2); return push(t); } @SuppressWarnings("unchecked") private void ensureCapacity(int newLength) { T[] newItems = (T[]) new Object[newLength]; System.arraycopy(elements,0,newItems,0,elements.length); elements = newItems; } public int size() { return size; } public boolean isEmpty() { return elements == null || size < 1; } public boolean isFull() { checkIsValid(); return size == elements.length; } private void checkIsValid() { if (elements == null) { throw new NullPointerException("init first"); } if (elements.length < size) { throw new IndexOutOfBoundsException(); } } @Override public String toString() { if (elements == null || size < 1) { return "[]"; } StringBuilder builder = new StringBuilder(); builder.append("["); for (int i = 0; i < size; i++) { T t = elements[i]; if (i == size - 1) { builder.append(t.toString()); } else { builder.append(t.toString()).append(","); } } builder.append("]"); return builder.toString(); }}
(2)栈结构的测试：这里的测试不全面，只测试了普通情况，边界部分还需要考虑
public class RStackTest { RStack rStack; @Before public void init() { rStack = new RStack<>(10); for (int i = 0; i < 10; i++) { rStack.push(i); } } @Test public void isEmpty(){ Assert.assertFalse(rStack.isEmpty()); RStack stack = new RStack<>(); Assert.assertTrue(stack.isEmpty()); } @Test public void isFull(){ Assert.assertTrue(rStack.isFull()); RStack stack = new RStack<>(); Assert.assertFalse(stack.isFull()); } @Test public void pop(){ for (int i = 0; i < 10; i++) { Assert.assertEquals(10 - i - 1,rStack.peek().intValue()); Assert.assertEquals(10 - i - 1,rStack.pop().intValue()); } } @Test public void size(){ RStack stack = new RStack<>(); for (int i = 0; i < 10; i++) { Assert.assertTrue(stack.push(i)); Assert.assertEquals(i+1,stack.size()); } Assert.assertFalse(stack.push(10)); System.out.println(stack.toString()); } @Test public void pushExt(){ for (int i = 10; i < 20; i++) { Assert.assertTrue(rStack.pushExt(i)); Assert.assertEquals(i+1,rStack.size()); } System.out.println(rStack.toString()); }} (3)栈的练习：
public class StackUtil { /** * 假设栈中的元素是Integer, 从栈顶到栈底是 : 5,4,3,2,1 调用该方法后， 元素次序变为: 1,2,3,4,5 * 注意：只能使用Stack的基本操作，即push,pop,peek,isEmpty， 可以使用另外一个栈来辅助 */ public static void reverse(RStack stack) { if (checkStackNull(stack)) return; RStack stack1 = new RStack<>(stack.size()); RStack stack2 = new RStack<>(stack.size()); while (!stack.isEmpty()) { stack1.push(stack.pop()); } while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } while (!stack2.isEmpty()) { stack.push(stack2.pop()); } // 对列最方便，但是违规了。。。// Queue queue = new LinkedList<>();// while (!stack.isEmpty()){ // queue.offer(stack.pop());// }// while (!queue.isEmpty()){ // stack.push(queue.poll());// } } private static boolean checkStackNull(RStack stack) { if (stack == null || stack.size() < 1) { return true; } return false; } /** * 删除栈中的某个元素 注意：只能使用Stack的基本操作，即push,pop,peek,isEmpty， 可以使用另外一个栈来辅助 * * @param o 被删除的对象 */ public static void remove(RStack stack, T o) { if (checkStackNull(stack)) return; RStack tempStack = new RStack<>(stack.size()); while (!stack.isEmpty() && !stack.peek().equals(o)) { tempStack.push(stack.pop()); } if (!stack.isEmpty()) { stack.pop(); } while (!tempStack.isEmpty()) { stack.push(tempStack.pop()); } } /** * 从栈顶取得len个元素, 原来的栈中元素保持不变 * 注意：只能使用Stack的基本操作，即push,pop,peek,isEmpty， 可以使用另外一个栈来辅助 * * @param len 长度 */ public static T[] getTop(RStack stack, int len) { if (stack == null || stack.size() < 1) { return null; } else if (len > stack.size()) { throw new IndexOutOfBoundsException(); } RStack tempStack = new RStack<>(stack.size()); @SuppressWarnings("unchecked") T[] results = (T[]) new Object[len]; for (int i = 0; i < len; i++) { results[i] = stack.peek(); tempStack.push(stack.pop()); } while (!tempStack.isEmpty()) { stack.push(tempStack.pop()); } return results; } /** * 字符串s 可能包含这些字符： ( ) [ ] { }, a,b,c... x,yz * 使用堆栈检查字符串s中的括号是不是成对出现的。 * 例如s = "([e{d}f])" , 则该字符串中的括号是成对出现， 该方法返回true * 如果 s = "([b{x]y})", 则该字符串中的括号不是成对出现的， 该方法返回false; * * @param s 输入字符串 */ public static boolean isValidPairs(String s) { if (s == null || s.equals("")) { return true; } char[] chars = s.toCharArray(); RStack stack = new RStack<>(chars.length / 2); RStack rightStack = new RStack<>(chars.length / 2); for (char chr : chars) { if (chr == '{') { stack.push('}'); } else if (chr == '[') { stack.push(']'); } else if (chr == '(') { stack.push(')'); } if (chr == '}') { if ('}' != stack.pop()) { return false; } } else if (chr == ']') { if (']' != stack.pop()) { return false; } } else if (chr == ')') { if (')' != stack.pop()) { return false; } } } return true; }} (4)测试：
public class StackUtilTest { @Test public void reverseStack() { RStack stack = new RStack<>(); for (int i = 1; i < 6; i++) { stack.push(i); } StackUtil.reverse(stack); Assert.assertTrue(!stack.isEmpty()); System.out.println(stack); for (int i = 1; i < 6; i++) { Assert.assertEquals(i, stack.pop().intValue()); } Assert.assertTrue(stack.isEmpty()); } @Test public void removeStack() { RStack stack = new RStack<>(); for (int i = 1; i < 6; i++) { stack.push(i); } Assert.assertTrue(!stack.isEmpty()); StackUtil.remove(stack, 2); Assert.assertTrue(!stack.isEmpty()); Assert.assertEquals(4, stack.size()); System.out.println(stack); StackUtil.remove(stack, 1); Assert.assertTrue(!stack.isEmpty()); Assert.assertEquals(3, stack.size()); System.out.println(stack); StackUtil.remove(stack, 6); Assert.assertTrue(!stack.isEmpty()); System.out.println(stack); StackUtil.remove(stack, 5); Assert.assertTrue(!stack.isEmpty()); Assert.assertEquals(2, stack.size()); System.out.println(stack); } @Test public void getTopStack() { RStack stack = new RStack<>(); for (int i = 1; i < 6; i++) { stack.push(i); } Object[] integers = StackUtil.getTop(stack, 4); Assert.assertEquals(5, stack.size()); for (int i = 0; i < integers.length; i++) { Assert.assertEquals(5-i, ((Integer) integers[i]).intValue()); } } @Test public void isValidPairs(){ String s1 = "([e{d}f])"; String s2 = "([b{x]y})"; Assert.assertTrue(StackUtil.isValidPairs(s1)); Assert.assertFalse(StackUtil.isValidPairs(s2)); }} 以上就是栈简单的实现和练习，这里不讲解代码的具体细节，相对来说比较简单，因为栈的方法不多。如果代码有问题或者需要优化的地方，欢迎指正。
转载地址：http://sidws.baihongyu.com/