Java代码实现顺序栈和链式栈

Java代码实现顺序栈和链式栈

栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入或者删除运算。后进先出（Last In First Out）。

栈中的数据操作主要有push(压入)和pop(弹出)操作。

实际上，栈就可以用数组来实现，也可以用链表来实现。用数组实现的叫做顺序栈，用链表实现的叫做链式栈。

为了简单起见，我们的栈不支持泛型。

顺序栈

public class StackBasedArray implements StackInterface{ private String[] values; // 存储栈中元素的数组 private int capacity;// 栈的容量 private int count;// 栈中已有数据个数 // 初始化栈，容量确定。 public StackBasedArray(int capacity) { this.values = new String[capacity]; this.capacity = capacity; this.count = 0; } /** * 入栈操作 * * @param value * @return */ public Boolean push(String value) { // 数组空间不够了 if (capacity == count) { return false; } values[count] = value; count++; return true; } /** * 出栈操作 * * @return */ public String pop() { // 栈为空，则直接返回null if (0 == count) { return null; } String tmp = values[count - 1]; --count; return tmp; } @Override public String toString() { return "StackBasedArray{" + "values=" + Arrays.toString(values) + ", capacity=" + capacity + ", count=" + count + '}'; } }

测试代码：

StackBasedArray as = new StackBasedArray(10); System.out.println(as); Boolean r1 = as.push("000"); System.out.println(as + ",r1:" + r1); for (int i = 1; i < 11; i++) { boolean r2 = as.push("" + i + i + i); System.out.println(as + ",r2:" + r2); } System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as); System.out.println("as.pop():" + as.pop() + "," + as);

输出结果：符合预期

StackBasedArray{values=[null, null, null, null, null, null, null, null, null, null], capacity=10, count=0} StackBasedArray{values=[000, null, null, null, null, null, null, null, null, null], capacity=10, count=1},r1:true StackBasedArray{values=[000, 111, null, null, null, null, null, null, null, null], capacity=10, count=2},r2:true StackBasedArray{values=[000, 111, 222, null, null, null, null, null, null, null], capacity=10, count=3},r2:true StackBasedArray{values=[000, 111, 222, 333, null, null, null, null, null, null], capacity=10, count=4},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, null, null, null, null, null], capacity=10, count=5},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, null, null, null, null], capacity=10, count=6},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, null, null, null], capacity=10, count=7},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, null, null], capacity=10, count=8},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, null], capacity=10, count=9},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=10},r2:true StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=10},r2:false as.pop():999,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=9} as.pop():888,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=8} as.pop():777,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=7} as.pop():666,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=6} as.pop():555,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=5} as.pop():444,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=4} as.pop():333,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=3} as.pop():222,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=2} as.pop():111,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=1} as.pop():000,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=0} as.pop():null,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=0} as.pop():null,StackBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, count=0}

链式栈

使用链表来实现栈，push进的数据添加至链表的头结点，pop数据时取的也是链表的头结点，这样就实现了栈的后进先出。代码如下：

public class StackBasedLinkedList implements StackInterface { private Node first; /** * 每次添加数据都向链表头结点添加。 * * @param value * @return */ @Override public Boolean push(String value) { Node newNode = new Node(value, null); if (null == first) { first = newNode; } else { newNode.next = first; first = newNode; } return true; } /** * 每次获取数据都从链表头结点获取。 * * @return */ @Override public String pop() { if (null == first) { return null; } else { String tmp = first.getValue(); first = first.next; return tmp; } } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); if (first != null) { Node curr = first; while (curr != null) { sb.append(String.valueOf(curr)); if (curr.next != null) { sb.append(",").append(" "); } curr = curr.next; } } sb.append("]"); return sb.toString(); } private static class Node { Node next; String value; public Node(String value, Node next) { this.next = next; this.value = value; } public String getValue() { return value; } @Override public String toString() { return value; } } }

测试代码：

StackBasedLinkedList sbll = new StackBasedLinkedList(); System.out.println(sbll); // 添加数据 for (int i = 0; i < 10; i++) { sbll.push("" + i + i + i); } System.out.println(sbll); // 获取数据 for (int i = 0; i < 11; i++) { System.out.println("sbll.pop():" + sbll.pop()); }

输出结果：符合预期。

[] [999, 888, 777, 666, 555, 444, 333, 222, 111, 000] sbll.pop():999 sbll.pop():888 sbll.pop():777 sbll.pop():666 sbll.pop():555 sbll.pop():444 sbll.pop():333 sbll.pop():222 sbll.pop():111 sbll.pop():000 sbll.pop():null

完整代码请查看

项目中搜索SingleLinkedList即可。 github传送门 https://github.com/tinyvampirepudge/DataStructureDemo

gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo

参考： 如何实现浏览器的前进和后退功能？