数据结构-栈

栈

栈是限定仅在表尾进行插入和删除操作的线性表
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表

image.png

Java中的栈

Stack.png

Vector

Vector也是用数组实现的，相对于ArrayList，Vector是线程安全的。Vector使用synchronized 做线程同步。

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }   
 public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
     * Appends the specified element to the end of this Vector.
     *
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

Stack

Stack继承Vector其中添加了自己的方法来实现入栈和出栈，还是用的父类Vector的方法来执行元素操作

public
class Stack<E> extends Vector<E> {
    public Stack() {
    }
    public E push(E item) {
        addElement(item);
        return item;
    }
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    public boolean empty() {
        return size() == 0;
    }
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}

两个栈实现中缀表达式转后缀表达式并计算结果

数字输出，运算符进栈，括号匹配出栈，栈顶运算符优先级低出栈

• 中缀表达式：10 + ( 2 + 3 ) * 5 - 10 / 2 + 2
• 后缀表达式：10 2 3 + 5 * + 10 2 / - 1 +
• 结果：31

package com.execlib;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * 测试中缀表达式转后缀表达式并计算结果
 * 中缀表达式：10 + ( 2 + 3 ) * 5 - 10 / 2 + 2
 * 后缀表达式：10 2 3 + 5 * + 10 2 / - 1 +
 * 结果：31
 */
public class TestExp {
    public static Stack<String> symbolStack = new Stack();
    private static OptStack optStack = new OptStack();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while (true){
            System.out.println("Enter your exp:");
            str = br.readLine();
            if (str == null||str.trim()==null||str.trim()=="")
                continue;
            String pattern = "[\\ \\.0-9\\+\\-*/()]*";
            if (!Pattern.matches(pattern,str)){
                System.err.println("exp err！");
                continue;
            }
            String[] resStr = str.split(" ");
            for (int i = 0 ;i<resStr.length;i++){
                String item = resStr[i];
                if ("+".equals(item)||"-".equals(item)||"(".equals(item)){
                    symbolStack.push(item);
                }else if ("*".equals(item)||"/".equals(item)){
                    optStack.push(resStr[++i]);
                    optStack.push(item);
                    if (symbolStack.contains("-")||symbolStack.contains("+")){
                        while (symbolStack.size()!=0){
                            String peek = symbolStack.peek();
                            if ("-".equals(peek)||"+".equals(peek)){
                                optStack.push(symbolStack.pop());
                            }else {
                                break;
                            }
                        }
                    }
                }else if (")".equals(item)){
                    while (symbolStack.size()!=0){
                        String pop = symbolStack.pop();
                        if ("(".equals(pop)){
                            break;
                        }
                        optStack.push(pop);
                    }
                }else {
                    optStack.push(item);
                }
            }
            while ( symbolStack.size()!= 0){
                optStack.push(symbolStack.pop());
            }
            Object result = optStack.calculate();
            System.out.println("\nresult："+result);
        }
    }

    /**
     * 入栈并计算
     */
    public static class OptStack extends Stack<String>{
        @Override
        public String push(String item) {
            System.out.print(item+" ");
            if (this.size()>=2){
                if ("+-*/".contains(item)){
                    BigDecimal res = new BigDecimal("0");
                    BigDecimal sec = new BigDecimal(this.pop());
                    BigDecimal fir = new BigDecimal(this.pop());
                    if ("+".equals(item)){
                        res = fir.add(sec);
                    }else if ("-".equals(item)){
                        res = fir.subtract(sec);
                    }else if ("*".equals(item)){
                        res = fir.multiply(sec);
                    }else if ("/".equals(item)){
                        res = fir.divide(sec);
                    }
                    return super.push(res.toString());
                }
            }
            return super.push(item);
        }
        public Object calculate(){
            return this.peek();
        }
    }
}