1，栈

• 栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据项，以此类推。这种机制在不少编程环境中都很有用。将演示如何利用栈来检验源程序中的小括号、中括号和大括号是否匹配的问题。最后会演示栈在解析算术表达式时起到的重要作用，比如解析3*(4+5)。
• 栈也是那些应用了相当复杂的数据结构算法的便利工具。比如在二叉树中，用栈来辅助遍历树的节点，在图中，用栈来辅助查找图的顶点（一种可以用来解决迷宫问题的技术）。
• 大部分微处理器运用基于栈的体系结构。当调用一个方法时，把它的返回地址和参数压入栈，当方法结束返回时，那些数据出栈。栈操作就嵌入在微处理器中。

2，邮政模拟例子

• 为了理解栈的思想，从美国邮政服务的一个模拟例子入手。许多人在工作时收到信后，会随手将它放在大厅桌子上的信堆上，或者把它投入一个"专门"的筐里。等他们有空闲时间的时候，就会从上到下处理那些堆积的邮件。他们首先打开堆叠在最上面的信，然后做相应的处理-付账单、扔掉邮件或其他的什么事情。第一封信处理完之后，接下来会处理下一封信，此时它正处于信堆的最上面。按照此方法处理下去，直到最后轮到处理信堆最下面的一份（此时它在信堆的最上面）。

3，栈的Java代码例子

• 实现一个stack.java文件，用StackX类实现栈。

class StackX
{
    private int maxSize;//size of stack array
    private long[] stackArray;
    private int top;//top of stack

    //---------------------------------------------
    public StackX(int s) //constructor
    {
        maxSize = s;//set array size
        stackArray = new long[maxSize];//create array
        top = -1;//no items yet
    }

    //---------------------------------------------
    public void push(long j)//put item on top of stack
    {
        stackArray[++top] = j;//increment top, insert item
    }

    //---------------------------------------------
    public long pop()//take item from top of stack
    {
        return stackArray[top--];//access item, decrement top
    }

    //---------------------------------------------
    public long peek()//peek at top of stack
    {
        return stackArray[top];
    }

    //---------------------------------------------
    public boolean isEmpty()//true if stack is empty
    {
        return (top == -1);
    }

    //---------------------------------------------
    public boolean isFull()//true if stack is full
    {
        return (top == maxSize - 1);
    }
    //---------------------------------------------
}//end class StackX

///////////////////////////////////////////////////////////
public class StackApp
{
    public static void main(String[] args)
    {
        StackX theStack = new StackX(10);//make new stack
        theStack.push(20);//push item onto stack
        theStack.push(40);
        theStack.push(60);
        theStack.push(80);
        System.out.println("Top item: " + theStack.peek());//peek the top item

        while (!theStack.isEmpty())//until it's empty, delete item from stack
        {
            long value = theStack.pop();
            System.out.print(value);//display it
            System.out.print("  ");
        }//end while
        System.out.println("");
    }//end main
    /*
     * 输出结果
     *  Top item: 80
        80  60  40  20  
     * */
}//end class StackApp

4，栈实例：单词逆序

• 用栈完成单词逆序。运行程序，提示输入一个单词，点击"Enter"按钮后，屏幕上便显示字母顺序倒置后的词。
• 首先，字母从输入的字符串中一个接一个地提取出来并且压入栈中。接着它们依次弹出栈，并显示出来。因为栈的后进先出的特点，所以字母的顺序就颠倒过来了。

import java.io.*;//for I/O

/*
 * stack used to reverse a string
 * */
class StackX
{
    private int maxSize;
    private char[] stackArray;
    private int top;

    public StackX(int max)//constructor
    {
        maxSize = max;
        stackArray = new char[maxSize];
        top = -1;
    }

    public void push(char j)//put item on top of stack
    {
        stackArray[++top] = j;
    }

    public char pop()//take item from top of stack
    {
        return stackArray[top--];
    }

    public char peek()//peek at top of stack
    {
        return stackArray[top];
    }

    public boolean isEmpty()//true if stack is empty
    {
        return (top == -1);
    }
}//end class StackX

class Reverser
{
    private String input;//input string
    private String output;//output string

    public Reverser(String in)//constructor
    {
        input = in;
    }

    public String doRev()//reverse the string
    {
        int stackSize = input.length();//get max stack size
        StackX theStack = new StackX(stackSize);//make stack
        for (int j = 0; j < input.length(); j++)
        {
            char ch = input.charAt(j);//get a char from input
            theStack.push(ch);//push it
        }
        output = "";
        while (!theStack.isEmpty())
        {
            char ch = theStack.pop();//pop a char
            output = output + ch;//append to output
        }
        return output;
    }//end doRev()
}//end class Reverser

public class ReverseApp
{
    public static void main(String[] args) throws IOException
    {
        String input, output;
        while (true)
        {
            System.out.print("Enter a string: ");
            System.out.flush();
            input = getString();//read a string from kbd
            if (input.equals(""))//quit if [Enter]
            {
                break;
            }
            Reverser theReverser = new Reverser(input);//make a Reverser
            output = theReverser.doRev();//use it
            System.out.println("Reversed: " + output);
        }//end while
    }//end main()

    public static String getString() throws IOException
    {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }
    
    /*
    * 输出结果：
    *   Enter a string: hello world
        Reversed: dlrow olleh
    * */
}//end class ReverseApp

5，栈实例：分隔符匹配

• 栈通常用于解析某种类型的文本串。通常，文本串是用计算机语言写的代码行，而解析它们的程序就是编译器。
• 分隔符包括大括号’{‘和’}’，中括号’[‘和’]’，和小括号’(‘和’)’。每个左分隔符需要和右分隔符匹配；同时，在字符串中后出现的左分隔符应该比早出现的左分隔符先完成匹配。
• 分隔符匹配程序从字符串中不断地读取字符，每次读取一个字符。若发现它是左分隔符，将它压入栈中。当从输入中读到一个右分隔符时，弹出栈顶的左分隔符，并且查看它是否和右分隔符相匹配。如果它们不匹配（比如，一个左大括号和一个右小括号），则程序报错。如果栈中没有左分隔符和右分隔符匹配，或者一直存在着没有被匹配的分隔符，程序也报错。分隔符没有被匹配，表现为把所有的字符读入之后，栈中仍留有分隔符。

import java.io.*;

/*
 * stacks used to check matching brackets
 * */
class StackX
{
    private int maxSize;
    private char[] stackArray;
    private int top;

    public StackX(int max)//constructor
    {
        maxSize = max;
        stackArray = new char[maxSize];
        top = -1;
    }

    public void push(char j)//put item on top of stack
    {
        stackArray[++top] = j;
    }

    public char pop()//take item from top of stack
    {
        return stackArray[top--];
    }

    public char peek()//peek at top of stack
    {
        return stackArray[top];
    }

    public boolean isEmpty()//true if stack is empty
    {
        return (top == -1);
    }
}//end class StackX

class BracketChecker
{
    private String input;//input string

    public BracketChecker(String in)//constructor
    {
        input = in;
    }

    public void check()
    {
        int stackSize = input.length();//get max stack size
        StackX theStack = new StackX(stackSize);//make stack
        for (int j = 0; j < input.length(); j++)//get chars in turn
        {
            char ch = input.charAt(j);//get char
            switch (ch)
            {
                case '{'://opening symbols
                case '[':
                case '(':
                    theStack.push(ch);//push them
                    break;
                case '}'://closing symbols
                case ']':
                case ')':
                    if (!theStack.isEmpty())//if stack not empty
                    {
                        char chx = theStack.pop();//pop and check
                        if (
                                (ch == '}' && chx != '{') ||
                                        (ch == ']' && chx != '[') ||
                                        (ch == ')' && chx != '('))
                            System.out.println("Error: " + ch + " at " + j);
                    }
                    else//prematurely empty
                    {
                        System.out.println("Error: " + ch + " at " + j);
                    }
                    break;
                default://no action on other characters
                    break;
            }//end switch
        }//end for
        //at this point, all characters have been processed
        if (!theStack.isEmpty())
        {
            System.out.println("Error: missing right delimiter");
        }
    }//end check()
}//end class BracketChecker

public class BracketsApp
{
    public static void main(String[] args) throws IOException
    {
        String input;
        while (true)
        {
            System.out.print("Enter string containing delimiters: ");
            System.out.flush();
            input = getString();//read a string from kbd
            if (input.equals(""))//quit if [Enter]
            {
                break;
            }
            BracketChecker theChecker = new BracketChecker(input);//make a BracketChecker
            theChecker.check();//check brackets
        }//end while
    }//end main()

    public static String getString() throws IOException
    {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }
    /*
    * 输出结果
    *   Enter string containing delimiters: a{b(c]d}e
        Error: ] at 4
    * */
}

6，栈的效率

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