1.栈的基本概念 栈 (英语:stack)又称为堆栈 或堆叠 ,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。
2.Java模拟简单的顺序栈实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public class MyStack { private int [] array; private int maxSize; private int top; public MyStack (int size) { this .maxSize = size; array = new int [size]; top = -1 ; } public void push (int value) { if (top < maxSize-1 ){ array[++top] = value; } } public int pop () { return array[top--]; } public int peek () { return array[top]; } public boolean isEmpty () { return (top == -1 ); } public boolean isFull () { return (top == maxSize-1 ); } }
这个栈是用数组实现的,内部定义了一个数组,一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈,push()方法是向栈中压入元素,指向栈顶的变量top加一,使它指向原顶端数据项上面的一个位置,并在这个位置上存储一个数据。pop()方法返回top变量指向的元素,然后将top变量减一,便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。
** 产生的问题: ①、上面栈的实现初始化容量之后,后面是不能进行扩容的(虽然栈不是用来存储大量数据的),如果说后期数据量超过初始容量之后怎么办?(自动扩容) ②、我们是用数组实现栈,在定义数组类型的时候,也就规定了存储在栈中的数据类型,那么同一个栈能不能存储不同类型的数据呢?(声明为Object) ③、栈需要初始化容量,而且数组实现的栈元素都是连续存储的,那么能不能不初始化容量呢?(改为由链表实现)**
3.增强功能版栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 import java.util.Arrays;import java.util.EmptyStackException;public class ArrayStack { private Object[] elementData; private int top; private int size; public ArrayStack () { this .elementData = new Object [10 ]; this .top = -1 ; this .size = 10 ; } public ArrayStack (int initialCapacity) { if (initialCapacity < 0 ){ throw new IllegalArgumentException ("栈初始容量不能小于0: " +initialCapacity); } this .elementData = new Object [initialCapacity]; this .top = -1 ; this .size = initialCapacity; } public Object push (Object item) { isGrow(top+1 ); elementData[++top] = item; return item; } public Object pop () { Object obj = peek(); remove(top); return obj; } public Object peek () { if (top == -1 ){ throw new EmptyStackException (); } return elementData[top]; } public boolean isEmpty () { return (top == -1 ); } public void remove (int top) { elementData[top] = null ; this .top--; } public boolean isGrow (int minCapacity) { int oldCapacity = size; if (minCapacity >= oldCapacity){ int newCapacity = 0 ; if ((oldCapacity<<1 ) - Integer.MAX_VALUE >0 ){ newCapacity = Integer.MAX_VALUE; }else { newCapacity = (oldCapacity<<1 ); } this .size = newCapacity; int [] newArray = new int [size]; elementData = Arrays.copyOf(elementData, size); return true ; }else { return false ; } } }
测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @Test public void ArrayStackTest () { ArrayStack stack = new ArrayStack (3 ); stack.push(1 ); stack.push(2 ); stack.push(3 ); stack.push("abc" ); System.out.println(stack.peek()); stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.peek()); }
4.利用栈实现字符串逆序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 @Test public void testStringReversal () { ArrayStack stack = new ArrayStack (); String str = "HelloWorld" ; char [] c = str.toCharArray(); for (char item: c){ stack.push(item); } while (!stack.isEmpty()){ System.out.print(stack.pop()); } }
5.利用栈判断分隔符是否匹配 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 @Test public void testMatch () { ArrayStack stack = new ArrayStack (); String str = "12<a[b{c}]>" ; char [] cha = str.toCharArray(); for (char c: cha){ switch (c){ case '{' : case '[' : case '<' : stack.push(c); break ; case '}' : case ']' : case '>' : if (!stack.isEmpty()){ char left = stack.pop().toString().toCharArray()[0 ]; if (c=='}' && left != '{' || c==']' && left != '[' || c==')' && left != '(' ){ System.out.println("Error:" +left+"-" +c); } } break ; default : break ; } } }
6.总结 根据栈后进先出的特性,我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。 对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。