前言

---

         栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据项，依次类推。这种机制在不少编程环境中都很有用。

栈的Java代码

---

         下面来看一个程序，StackX.java public class StackX<T> { private int maxSize; // size of stack array private Object[] stackList; private int top; // top of stack public StackX(int maxSize) { // constructor this.maxSize = maxSize; // set array size stackList = new Object[maxSize]; // create array top = -1; // no items yet } public synchronized void push(T data) { // put item on top of stack stackList[++top] = data; // increment top, insert item } @SuppressWarnings("unchecked") public synchronized T pop() { // take item from top of stack return (T) stackList[top--]; // access item, decrement top } @SuppressWarnings("unchecked") public synchronized T peek() { // peek at top of stack return (T) stackList[top]; } public synchronized boolean isFull() { // true if stack is full return top == maxSize-1; } public synchronized boolean isEmpty() { // true if stack is empty return top == -1; } } StackTest.java public class StackTest {   public static void main(String[] args) throws IOException { int[] datas = {1,2,3,4}; StackX<Integer> stackX = new StackX<Integer>(4); for(int i=0; i<datas.length; i++) { stackX.push(datas[i]); } while(!stackX.isEmpty()) { System.out.print(stackX.pop()); System.out.print(" "); } } public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String line = br.readLine(); return line; }   } 输出结果如下： 4 3 2 1          请注意显示数据的顺序和输入的顺序正好相反。这是因为最后入栈的数据项最先弹出，所以输出结果中4显示在最前面。

StackX类方法

---

          构造方法根据参数规定的容量创建一个新栈。栈的域包括表示最大容量的变量(即数组的大小)、数组本身以及变量top，它存储栈顶元素的下标。(注意，由于栈是由数组实现的，需要先规定栈的大小。但是，如果使用链表来实现栈，就不需要先规定栈的容量。)          push()方法中将top值增加一，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据项。再次提醒，top是在插入数据项之前递增的。          pop()方法返回top标识的数据项值，然后top减一。这个方法有效地从栈中移除了数据项，虽然数据项仍然存在数组中(直到有新的数据项压入栈中覆盖这个数据项)，但不能再访问它了。          peek()方法仅返回top所指的数据项的值，不对栈做任何改动。          isEmpty()和isFull()方法分别在栈空和栈满时返回true。栈空时top变量为-1，栈满时top变量为maxSize-1。

栈实例1：单词逆序

---

         栈的第一个例子是做一件非常简单的事情：单词逆序。运行程序，提示输入一个单词，点击"Enter"按钮后，屏幕上便显示字母顺序倒置后的词。          用栈进行单词逆序：首先，字母从输入的字符串中一个接一个地提取出来并且压入栈中。接着它们依次弹出栈，并显示出来。因为栈的后进先出的特性，所以字母的顺序就颠倒过来了。代码如下： public class Reverser {   private String input; private StringBuilder output; public Reverser(String in) { input = in; } public String doRev() { int stackSize = input.length(); StackX<Character> stackX = new StackX<>(stackSize); // 使用上文中的StackX类 for(int j=0; j<stackSize; j++) { char ch = input.charAt(j); stackX.push(ch); } output = new StringBuilder(); while(!stackX.isEmpty()) { output.append(stackX.pop()); } return output.toString(); } } public class StackTest {   public static void main(String[] args) throws IOException { String input, output; while(true) { System.out.println("Enter a string: "); System.out.flush(); input = getString(); if(input.equals("")) break; Reverser reverser = new Reverser(input); output = reverser.doRev(); System.out.println("Reversed:" + output); } } public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String line = br.readLine(); return line; }   }          建立Reverse类来处理输入字符串的逆序工作。该类的关键组成部分是doRev()方法，该方法利用栈实现逆置操作。在doRev()中创建了一个栈，它根据输入字符串的长度确定栈的大小。          main()方法中由用户输入一个字符串，创建Reverser对象，字符串作为一个参数传给构造方法，接着调用这个对象的doRev()方法，并显示返回值，这个返回值是逆序的字符串。下面是程序的 输出结果： Enter a string: abckde Reversed:edkcba Enter a string:

栈实例2：分隔符匹配

---

         栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析它们的程序就是编译器。          为了解析清楚，下面看一个检查用户输入的一行文本中分隔符的程序。文本不一定是实际的Java代码，但它需要使用和Java同样的分隔符。分隔符包括大括号 ‘ { ’和 ‘ } ’，中括号 ‘ [ ’和 ‘ ] ’，和小括号‘（’ 和‘）’。每个左分隔符需要和右分隔符匹配；这就是说，每个‘{’后面要有‘}’来匹配，依次类推。同时，在字符串中后出现的左分隔符应该比早出现的左分隔符先完成匹配。            分隔符匹配程序从字符串中不断地读取字符，每次读取一个字符。若发现它是左分隔符，将它压入栈中。当从输入中读到一个右分隔符时，弹出栈顶的左分隔符，并且查看它是否和右分隔符相匹配。如果它们不匹配，则程序报错。如果栈中没有左分隔符和右分隔符匹配，或者一直存在着没有被匹配的分隔符，程序也报错。分隔符没有被匹配，表现为把所有的字符读入之后，栈中仍留有分隔符。代码如下： public class BracketChecker { private String input; public BracketChecker(String in) { input = in; } public void check() { int stackSize = input.length(); StackX<Character> theStack = new StackX<>(stackSize); // 用上文中的StackX类 for(int i=0; i<stackSize; i++) { char ch = input.charAt(i); switch (ch) { case '{': case '(': case '[': theStack.push(ch); break; case '}': case ')': case ']': if(!theStack.isEmpty()) { // 如果栈中没有左分隔符，再插入右分隔符，则报错 char chx = theStack.pop(); if((ch == '}' && chx != '{') || // 如果左分隔符和右分隔符不匹配，则报错 ch == ')' && chx != '(' || ch == ']' && chx != '[') { System.out.println("Error: " + ch + " at " + i); } } else { System.out.println("Error: " + ch + " at " + i); } break;   default: break; } } if(!theStack.isEmpty()) { // 如果栈中还有分隔符，则报错 System.out.println("Error: missing right delimiter"); } } } 输出结果： Enter a string: asdaf} Error: } at 5 // 栈中没有左分隔符 Enter a string: asdfa{dasf] Error: ] at 10     // 分隔符不匹配 Enter a string: asfda{ Error: missing right delimiter     // 栈中还有剩余分隔符 Enter a string: {}[]()     // 匹配成功 Enter a string:

栈的效率

---

         StackX类中实现的栈，数据项入栈和出栈的时间复杂度都为常数O(1)。这也就是说，栈操作所耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。