栈和队列

栈和队列不适合作为数据的记录工具，它们更多地是作为程序员的工具来运用。主要作 为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比数组、链表等数据库类型的结构要短的多。在程序操作执行期间他们才被创建，通 常用它们去执行某项特殊的任务；当完成任务后，它们就被销毁。
       下面的StackX类，实现一个栈的功能：

class StackX
{
    private int maxSize;
    private char[] stackArray;
    private int top;

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

    public void push(char j)    //入栈，注意要先将top指针上移，然后将数据赋给新的top位置
    {
        stackArray[++top] = j;
    }

    public char pop()    //出栈，先取得数据，然后将top下移
    {
        return stackArray[top--];
    }

    public char peek()    //只查看栈顶的元素，top指针不动
    {
        return stackArray[top];
    }

    public boolean isEmpty()
    {
        return (top == -1);
    }
}//end class StackX

 

对这个类的解释：

StackX是构造方法，根据参数规定的容量创建一个新栈。栈的域包括表示最大容量的变量、数组本身以及变量top，它存储栈顶元素的下标。

Push方法中将top值增加一，使它指向原顶端数据项的上面的一个位置，并在在这个位置上存储一个数据项，再次提醒，top是在插入数据项之前递增的。

Pop方法返回top标识的数据项值，然后top减一。这个方法有效地从栈中移除了数据项；虽然数据项仍然存在数组中，直到有新的数据项压入栈中覆盖这个数据项。但是它不能再被访问了。

Peek方法仅返回top所指的数据项的值，不对栈做任何改动。

IsEmpty方法在栈空时返回true，栈空时top值为-1。

一种典型的应用是栈用于解析某种类型的文本串。 通常，文本串是计算机语言写的代码行，而解析它们的程序就是编译器。一个典型的例子是分隔符匹配程序，它从字符串中不断读取字符，每次读取一个字符。若发 现它是一个左分隔符，将它压入栈中。当从输入中读到一个右分隔符时，弹出栈顶的左分隔符，并且查看它是否合右分隔符相匹配。如果它们不匹配，则程序报错。 如果栈中没有左分隔符和右分隔符匹配，或者一直存在着没有被匹配的分隔符，程序也报错。这个方法的可行性在于，最后出现的左边分隔符需要最先匹配，这个规 律符合栈的后进先出的特点。
下面是分隔符匹配程序的代码：

import java.io.*;

class StackX{} 这个类的定义前面已经给出
class BracketChecker
{
    private String input;

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

    public void check()
    {
        int stackSize = input.length();
        StackX theStack = new StackX(stackSize);

        for(int j=0;j<input.length();j++)//get chars in turn
        {
            char ch = input.charAt(j);
            switch(ch)
            {
                case '{':    //opening symbols
                case '[':
                case '(':
                    theStack.push(ch);    //push them
                    break;
                
                case '}':    //closing symbols
                case ']':
                case ')':
                    if(!theStack.isEmpty())    //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:
                    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
//////////////////////////////////////////////////////

class  BracketsApp
{
    public static void main(String[] args) throws IOException
    {
        //System.out.println("Hello World!");
        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);
            theChecker.check();
        }
    }//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;
    }
}//end class BracketsApp

下面是一个队列的实现代码：

class Queue
{
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems;
    
    public Queue(int s)
    {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(long j) throws Exception    //put item at rear of queue
    {
        if(this.isFull())    //throw Exception if queue is full
            throw new Exception("Can't insert because queue is Full");
        if(rear == maxSize-1)    //deal with wraparound
            rear = -1;
        queArray[++color: #000000; padding: 0px; margin: 0

分享到：

三种简单排序算法及其对比 | 链表结构

• 2011-04-01 13:30
• 浏览 877
• 评论(0)
• 分类:编程语言
• 查看更多