数据结构(三):栈的实现以及应用

• 栈的描述
• 栈的接口实现
• • 顺序栈以及基本操作的实现
  • 链栈以及基本操作的实现
• 栈的应用
• • 分配符匹配问题:

栈是一中特殊的线性表,栈中的数据元素与数据元素之间的逻辑关系与线性表相同,他们的差别在于:线性表的插入和删除可以在表中任意位置,而栈的插入和删除只允许在表的尾端操作,允许插入和删除的一端叫做栈顶(top),另一端称为栈底(bottom),插入的操作称为入栈(push),删除的操作称为出栈(pop)。

public interface IStack {
    void clean();   //将已经存在的栈置成空栈
    boolean isEmpty();  //判断一个栈是否为空,空返回true,否则返回false
    int length();   //返回栈中数据元素的个数
    Object peek();  //取出栈顶元素并返回其值
    void push(Object x);    //将x元素压入栈顶
    Object pop();   //删除并返回删除的栈顶元素
}

与顺序表一样,顺序栈也是用链表来实现,假设数组名为stackElem。
由于入栈和出栈都是在栈顶操作,所以需要一个指针top时刻指向栈顶。
如下图:

public class SqStack implements IStack{
    //创建数组
    private Object[] stackElem;
    private int top;    //当栈不为空时,top指向栈顶元素的下一个存储位置
    public SqStack(int maxSize){
        top = 0;
        stackElem = new Object[maxSize];
    }
    @Override
    public void clean() {
        top = 0;
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public int length() {
        return top;
    }

    @Override
    public Object peek() {
        return stackElem[top-1];
    }

    @Override
    public void push(Object x)throws Exception {
        //判断栈是否满
        if(top==stackElem.length)
            throw new Exception("栈已满");
        else 
        stackElem[top++] = x;
    }

    @Override
    public Object pop()throws Exception {
        //判断栈是否为空
        if(isEmpty())
            throw new Exception("栈为空");
        else
            return  stackElem[--top];
        
    }
}

由于栈链表只能在栈顶进行,所以栈链表不需要设置头结点head。

//结点类
public class Node2 {
    public Object data;
    public  Node2 next;
    public Node2(){
            this(null,null);
        }
    public Node2(Object data){
            this(data,null);
        }
    public Node2(Object data, Node2 next){
            this.data = data;
            this.next = next;
        }
    }

public class linkStack implements IStack{
    public Node2 top;   //栈顶元素的引用
    @Override
    public void clean() {
        top = null;
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }

    @Override
    public int length() {
        Node2 p = top;
        int length = 0;
        while(p!=null){
            p = p.next;
            length++;
        }
        return length;
    }
    //取出栈顶元素并返回其值
    @Override
    public Object peek()throws Exception{
        //判断栈是否为空
        if(top == null)
            throw new Exception("栈为空");
        return top.next.data;
    }

    @Override
    public void push(Object x) throws Exception {
        Node2 p = new Node2(x);
        p.next = top;
        top = p;
    }

    @Override
    public Object pop() throws Exception {
        //判断是否为空栈
        if(isEmpty())
            throw new Exception("栈为空");
        Node2 p = top;
        top = p.next;
        return p.data;
    }
}

Java程序中有以下分隔符,圆括号" ( “和” ) “,方括号” [ “和” ] “,大括号” { “和” } “以及注释分隔符” "。以下是一些正确使用分隔符的例子:
a = b + ( c + d ) * ( e - f );
s[4] = t[a[2]] + u / (( i + j ) * k);
以下是分配符不匹配的句子:
a = ( b + c / ( d * e ) * f; //左括号多余
分析:

public class Example {
    private final int LEFT = 0; //记录分隔符为"左"分隔符
    private final int RIGHT = 1;    //记录分隔符为"右"分隔符
    private final int OTHER = 2;    //记录其他字符
    //判断分隔符类型
    public int verifyFlag(String str){
        if("(".equals(str)||"[".equals(str)||"{".equals(str)||"".equals(str)){
            return RIGHT;
        }
        else
            return OTHER;
    }
    //检验左右分隔符是否匹配
    public boolean matches(String str1,String str2){
        if("(".equals(str1)&&")".equals(str2)||
                "[".equals(str1)&&"]".equals(str2)||
                "{".equals(str1)&&"}".equals(str2)||
                "".equals(str2))
            return true;
        else {
            return false;
        }
    }
    public boolean isLegal(String str)throws Exception{
        //建立顺序栈
        if(!"".equals(str)&&str!=null){
            SqStack S = new SqStack(100);
            //将str拆分
            int length = str.length();
            for(int i=0;i