欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法(栈和队列)

程序员文章站 2022-03-13 10:47:17
...

首语

  • 历经一个月的时间,自己终于搭建完成了个人网站,还在持续优化中,网站采用halo博客系统,功能非常强大!欢迎大家来我的网站逛逛。有什么建议可以留言!

网站地址:http://www.yanghujun.com

  • 接下来我们开始第二节的数据结构学习,栈和队列。

  • 栈是限定仅在表尾进行插入和删除操作的线性表。
  • 允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出 的线性表。
    数据结构与算法(栈和队列)

栈的顺序存储结构

  • 如用数组实现,栈底是:下标为0的一端。
    数据结构与算法(栈和队列)

栈的链式存储结构

数据结构与算法(栈和队列)

链栈的出入栈操作

  • 链栈的入栈操作
    数据结构与算法(栈和队列)
s->data=e;
s->next=stack->top;
stack->top=s;
stack->count++;
  • 链栈的出栈操作

数据结构与算法(栈和队列)

p=stack->top
stack->top=p->next;
free(p)
stack->count--;

栈的经典实用(逆波兰表达式法)

  • 标准四则运算表达式——中缀表达式
    9+(3-1)*3+10/2
  • 计算机采用——后缀表达式
    9 3 1 - 3 * + 10 2 / +
    数据结构与算法(栈和队列)
中缀表达式转后缀表达式

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

数据结构与算法(栈和队列)

代码实现

  • 中缀表达式->后缀表达式
/**
     * @param expression 逆波兰表达式
     * 数字输出,运算符进栈,括号匹配出栈,栈顶优先级低出栈
     * @return 后缀式链表
     */
    public static LinkedList<String> parse(String expression) {
        // 结果输出栈
        LinkedList<String> output = new LinkedList<>();
        // 运算符栈
        Stack<Character> operators = new Stack<>();
        // 字符串截取起始位置
        int startPos = 0;
        // 字符串截取末尾位置
        int endPos = 0;
        // 正序遍历表达式中的每一个字符c
        for (char c : expression.toCharArray()) {
            // 字符串截取的结束位置+1
            ++endPos;
            // 判断字符c是否为运算符。
            if (isOperator(c)) {
                // 若运算符c之前有可保存的信息则将其作为一个整体保存至output链表。
                if (startPos < endPos - 1)
                    output.add(expression.substring(startPos, endPos - 1));
                // 更新字符串截取的起始位置
                startPos = endPos;
                // 若运算符c为左括号"(",则直接存入运算符栈。
                if (c == '(') {
                    operators.push(c);
                    // 若运算符c为右括号")",则依次从运算符栈中弹出运算符并保存至output链表,直到遇到左括号为止。
                } else if (c == ')') {
                    char op;
                    while (!operators.isEmpty() && (op = operators.pop()) != '(') {
                        output.add(String.valueOf(op));
                    }
                    // 若运算符c为非括号运算符(即:四则运算符号)
                } else {

                    // 若运算符栈为空则直接将c压栈至运算符栈。
                    if (operators.isEmpty()) {
                        operators.push(c);
                        // 若运算符栈栈顶的运算符为左括号,则将c直接压栈至运算符栈。
                    } else if (operators.peek() == '(') {
                        operators.push(c);
                        // 若运算符c的优先级高于运算符栈栈顶的运算符优先级,则将c压栈至运算符栈。
                    } else if (getOperatorPriorityValue(c) > getOperatorPriorityValue(operators.peek())) {
                        operators.push(c);
                        // 若运算符c的优先级小于或等于运算符栈栈顶的运算符优先级,则依次从运算符栈中弹出运算符并保存至output链表,直到遇到左括号或c的优先级高于栈顶运算符优先级的为止。再将c压栈至运算符栈。
                    } else {
                        while (!operators.isEmpty() && getOperatorPriorityValue(c) <= getOperatorPriorityValue(operators.peek()) && operators.peek() != '(') {
                            output.add(String.valueOf(operators.pop()));
                        }
                        operators.push(c);
                    }
                }
            }
        }

        // 当表达式遍历完成后,将尚未保存的非运算符信息作为整体保存至output链表。若运算符栈中尚有运算符时,则依序弹出运算符到output链表。
        if (startPos < expression.length()) output.add(expression.substring(startPos));
        while (!operators.isEmpty()) {
            output.add(String.valueOf(operators.pop()));
        }
        return output;
    }

 // 运算符
    private final static char[] OP = new char[]{'+', '-', '*', '/', '(', ')'};
    /**
     * 判断字符是否是运算符
     * @param op 运算符
     * @return 是运算符返回true,不是则返回false
     */
    public static boolean isOperator(char op) {
        for (int i = 0; i < OP.length; ++i) {
            if (op == OP[i])
                return true;
        }
        return false;
    }
	/**
     * 获取运算符优先等级
     * @param op 运算符
     * @return 根据OP数组中运算符的顺序计算出运算符的优先等级:+ -是0级,* /是1级,( )是2级
     */
    public static int getOperatorPriorityValue(char op) {
        return (String.copyValueOf(OP).indexOf(op)) / 2;
    }

  • 后缀表达式计算
/**
     * 表达式计算
     * 先将中缀表达式转换为后缀表达式,再计算表达式的结果
     * @param expression 表达式
     * @return 运算结果
     */
    public static double operation(String expression) {

        // 使用逆波兰算法处理
        LinkedList<String> rpnList = RPN.parse(expression);

        // 保存每一步运算结果的操作数栈
        Stack<Double> operands = new Stack<>();

        // 若表达式第一位为运算符,则表达式无效


        // 遍历逆波兰表达式中每一项元素
        for (String elem : rpnList) {

            // 若是运算符
            if (RPN.isOperator(elem.charAt(0))) {


                // 从操作数栈取出栈顶的两个操作数
                double value2 = operands.pop();
                double value1 = operands.pop();

                // 获得运算结果
                double result = binaryOperation(elem.charAt(0), value1, value2);

                // 将计算结果压栈
                operands.push(result);

                // 如果是数值
            } else {
                operands.push(Double.parseDouble(elem));
            }
        }

        // 返回操作数栈中唯一的元素
        return operands.pop();
    }
  /**
     * 二元运算
     * @param operator 运算符
     * @param value1   值1
     * @param value2   值2
     * @return 运算结果
     */
    private static double binaryOperation(char operator, double value1, double value2) {
        switch (operator) {
            case '+':
                return value1 + value2;
            case '-':
                return value1 - value2;
            case '*':
                return value1 * value2;
            case '/':
                if (value2 == 0) throw new ArithmeticException("/ by zero.");
                return value1 / value2;
            default:
                throw new RuntimeException("");
        }
    }

栈(Stack)源码

/**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);
        return item;
    }
 /**
     * Adds the specified component to the end of this vector,
     * increasing its size by one. The capacity of this vector is
     * increased if its size becomes greater than its capacity.
     * <p>This method is identical in functionality to the
     * {@link #add(Object) add(E)}
     * method (which is part of the {@link List} interface).
     * @param   obj   the component to be added
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
/**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this
     * method for ensuring capacity without incurring the cost of an
     * extra synchronization.
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
/**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
    }
     /**
     * Deletes the component at the specified index. Each component in
     * this vector with an index greater or equal to the specified
     * {@code index} is shifted downward to have an index one
     * smaller than the value it had previously. The size of this vector
     * is decreased by {@code 1}.
     * <p>The index must be a value greater than or equal to {@code 0}
     * and less than the current size of the vector.
     * <p>This method is identical in functionality to the {@link #remove(int)}
     * method (which is part of the {@link List} interface).  Note that the
     * {@code remove} method returns the old value that was stored at the
     * specified position.
     * @param      index   the index of the object to remove
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
/**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    /**
     * Returns the component at the specified index.
     * <p>This method is identical in functionality to the {@link #get(int)}
     * method (which is part of the {@link List} interface).
     * @param      index   an index into this vector
     * @return     the component at the specified index
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return elementData(index);
    }

队列

  • 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表!
  • 插入的一端称为队尾,删除的一端称为队头。
    数据结构与算法(栈和队列)

队列的顺序存储

  • 缺点
    1.出队复杂度高o(n)
    2.容易假溢出。
    数据结构与算法(栈和队列)
    数据结构与算法(栈和队列)

循环队列

  • 把队列的这种头尾相接的顺序存储结构称为循环队列。
    数据结构与算法(栈和队列)

队列的连式存储及结构模式

  • 队列的链式存储结构,其实就是线性表的单链表,只不过是它只能尾进头出而已。
    数据结构与算法(栈和队列)
  • 空队列
    数据结构与算法(栈和队列)

队列(Queue)源码

/**
     * 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;
    }
    /**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this
     * method for ensuring capacity without incurring the cost of an
     * extra synchronization.
     *
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
相关标签: 数据结构与算法