数据结构学习笔记之栈(java)

发表于   |   分类于   |     |   次阅读

栈

基本概念

  • 栈是一个线性表，其插入和删除操作都在表的同一端进行。其中插入和删除元素的一端被称为栈顶，另一端被称为栈底。

  • 特点：先进后出。

  • 堆栈的抽象数据类型描述（ADT）

public interface MStack {
    boolean isEmpty();
    T getTop();//取栈顶元素
    void push(T x);//添加元素
    T pop();//删除栈顶元素并返回
}

实现

用顺序表实现的栈称为顺序栈，用链表实现的栈称为链栈。

链栈

  • 栈中的数据元素用一个链表来存储。需要确定哪一端对应于栈顶。如果把链表的前端作为栈顶，那么可以利用链表操作 addFront 和 removeFront 来实现堆栈的元素插入和删除，时间复杂度均为 O(1)。

  • 继承与聚合

    重用链表已经实现的功能，重用有两种方式继承与聚合。

继承方式实现链栈

public class MLinkStack extends MLinkList implements MStack{

    public MLinkStack(){
        super();
    }

    @Override
    public T getTop() {
        return get(0);
    }

    @Override
    public void push(T x) {
        addFront(x);
    }

    @Override
    public T pop() {
        return remove(0);
    }
}

聚合方式实现链栈

public class MLinkStack2 {
    private MLinkList list;
    public MLinkStack2(){
        list = new MLinkList();
    }
    public void push(T x){
        list.addFront(x);
    }
    public T pop(){
        return list.removeFront();
    }
    public T getTop(){
        return list.get(0);
    }
}

顺序栈

  • 利用数组实现的栈称为顺序栈，栈中的数据元素用一个一维数组来存储（T[] data）。一般将 data[0] 作为栈底，用一个整型变量 top 来作为指示栈顶位置的指针，称为栈顶指针。
  • 利用顺序表类 MSeqList 来实现顺序栈。聚合方式：
public final class MSeqStack {
    private MSeqList slist;//定义一个顺序表

    public MSeqStack(int num){
        slist = new MSeqList(num);
    }

    boolean isEmpty(){
        return slist.isEmpty();
    }

    public void push(T e){
        slist.add(e);
    }

    public T pop(){
        return slist.remove(slist.length() - 1);
    }

    public T getTop(){
        return slist.get(slist.length() - 1);
    }

    public String toString(){
        return slist.toString();
    }

    public T[] toArray(T a[]){
        return slist.toArray(a);
    }
}

算法应用

进制转换（十进制转r进制）

/**
     * 栈来实现十进制转r进制
     * @param n
     * @param r
     */
    public void decimaToBinary(int n, int r){
        MSeqStack seqStack = new MSeqStack<>(16);
        Integer x;
        while (n > 0){
            seqStack.push(n % r);
            n /= r;
        }
        while (!seqStack.isEmpty()){
            x = seqStack.pop();
            System.out.println(x);
        }
    }

表达式求值

此处讨论之含双目运算符的算术表达式，算术表达式的三种形式：

  1. 常规表达式：a b + (c - d / e) f
  2. 前缀式： + a b - c / d e f
  3. 后缀式: a b c d e / - f +

三种表达式的特点：

  1. 操作数之间的相对次序不变
  2. 运算符的相对次序不同

后缀表达式的运算特点：

  1. 运算符在式中出现的顺序恰为表达式的运算顺序。
  2. 每个运算符与它之前紧靠它的两个操作数构成一个最小表达式。

可以很容易的使用栈来实现后缀表达式的求值。

常规表达式转后缀表达式

从常规表达式中从左往右读取每一个记号，如果记号是操作数，则直接输出到后缀表达式。对于操作符，需要比较相邻两个操作符的优先级，如果当前操作符的优先高于栈顶操作符的优先级，则进栈。如果小于，则栈顶操作符出栈，并添加到后缀表达式，继续取栈顶操作符，重复此过程，直到当前操作符的优先级大于栈顶操作符的优先级。

算法 

public class Calculate {
    /**
     * 将字符串转化成List
     * @param str
     * @return
     */
    public ArrayList getStringList(String str){
        ArrayList result = new ArrayList();
        String num = "";
        for (int i = 0; i < str.length(); i++) {
            if(Character.isDigit(str.charAt(i))){
                num = num + str.charAt(i);
            }else{
                if(num != ""){
                    result.add(num);
                }
                result.add(str.charAt(i) + "");
                num = "";
            }
        }
        if(num != ""){
            result.add(num);
        }
        return result;
    }

    /**
     * 将中缀表达式转化为后缀表达式
     * @param inOrderList
     * @return
     */
    public ArrayList getPostOrder(ArrayList inOrderList){

        ArrayList result = new ArrayList();
        Stack stack = new Stack();
        for (int i = 0; i < inOrderList.size(); i++) {
            if(Character.isDigit(inOrderList.get(i).charAt(0))){
                result.add(inOrderList.get(i));
            }else{
                switch (inOrderList.get(i).charAt(0)) {
                    case '(':
                        stack.push(inOrderList.get(i));
                        break;
                    case ')':
                        while (!stack.peek().equals("(")) {
                            result.add(stack.pop());
                        }
                        stack.pop();
                        break;
                    default:
                        while (!stack.isEmpty() && compare(stack.peek(), inOrderList.get(i))){
                            result.add(stack.pop());
                        }
                        stack.push(inOrderList.get(i));
                        break;
                }
            }
        }
        while(!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }

    /**
     * 计算后缀表达式
     * @param postOrder
     * @return
     */
    public Integer calculate(ArrayList postOrder){
        Stack stack = new Stack();
        for (int i = 0; i < postOrder.size(); i++) {
            if(Character.isDigit(postOrder.get(i).charAt(0))){
                stack.push(Integer.parseInt(postOrder.get(i)));
            }else{
                Integer back = (Integer)stack.pop();
                Integer front = (Integer)stack.pop();
                Integer res = 0;
                switch (postOrder.get(i).charAt(0)) {
                    case '+':
                        res = front + back;
                        break;
                    case '-':
                        res = front - back;
                        break;
                    case '*':
                        res = front * back;
                        break;
                    case '/':
                        res = front / back;
                        break;
                }
                stack.push(res);
            }
        }
        return (Integer)stack.pop();
    }

    /**
     * 比较运算符等级
     * @param peek
     * @param cur
     * @return
     */
    public static boolean compare(String peek, String cur){
        if("*".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
            return true;
        }else if("/".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
            return true;
        }else if("+".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
            return true;
        }else if("-".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
            return true;
        }
        return false;
    }
}
  • 调用：
    Calculate calculate = new Calculate();
    String s = "12+(23*3-56+7)*(2+90)/2";
ArrayList result = calculate.getStringList(s);  //String转换为List
result = calculate.getPostOrder(result);   //中缀变后缀
int i = calculate.calculate(result);   //计算
System.out.println(i);