数组和链表自制栈和队列

时间：2022-07-24 15:41:26

数组和链表是常用的两种数据结构，在翻看了Stack类，Iterable接口，Iterator接口，Queue的Java源码后，尝试用数组和链表来自己实现一下栈和队列。

自己造过*后，实实在在的理解了*，才能真正深入的使用*。代码如下：

**说明：**Stackable是我自己写的接口

数组实现栈

public class SugarArrayStack<E> implements Stackable<E> ,Iterable<E>{

private static final int DEFAULT_CAPACITY = 2;

private int N = 0;
private E[] a;


public SugarArrayStack() {
    resize(DEFAULT_CAPACITY);
}

public SugarArrayStack(int size){
    resize(size);
}

private void resize(int size){
    E[] temp = (E[])new Object[size];
    for(int i = 0; i < N; i++){
        temp[i] = a[i];
    }
    a = temp;
}

@Override
public void push(E e){
    if(N >= a.length - 1){
        resize(a.length * 2);
    }
    a[N++] = e;
}

@Override
public E pop(){
    E temp = peek();
    a[--N] = null;
    if(N >= 0 && N == a.length / 4){
        resize(a.length / 2);
    }
    return temp;
}

@Override
public E peek(){
    int index = N - 1;
    return a[index];
}

@Override
public int size(){
    return N;
}

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


@Override
public Iterator<E> iterator() {
    return new ArrayIterator(N);
}

private class ArrayIterator implements Iterator<E>{

    private int currentIndex;

    public ArrayIterator(int currentIndex) {
        this.currentIndex = currentIndex;
    }

    @Override
    public boolean hasNext() {
        return currentIndex > 0;
    }

    @Override
    public E next() {
        currentIndex--;
        return a[currentIndex];
    }
}
}

链表实现栈

public class SugarLinkedQueue<E> implements Iterable<E>{

private Node<E> mHeadNode;
private Node<E> mTailNode;
private int mCount = 0;

public void enqueue(E e){
    Node<E> newTailNode = new Node<>(e,null);
    if(mCount == 0){
        mTailNode = newTailNode;
        mHeadNode = newTailNode;
    }else{
        Node<E> oldTailNode = mTailNode;
        mTailNode = newTailNode;
        oldTailNode.nextNode = newTailNode;
    }
    mCount ++;
}

public E dequeue(){
    if(isEmpty()){
        throw new IllegalStateException("Please enqueue an element firstly");
    }
    mCount --;

    E tempE = mHeadNode.e;
    mHeadNode = mHeadNode.nextNode;
    return tempE;
}

public int size(){
    return mCount;
}

public boolean isEmpty(){
    return mCount == 0;
}

@Override
public Iterator<E> iterator() {
    return new QueueIterator(mHeadNode);
}

private class QueueIterator implements Iterator<E>{

    private Node<E> currentNode;

    public QueueIterator(Node<E> currentNode) {
        this.currentNode = currentNode;
    }

    @Override
    public boolean hasNext() {
        return currentNode != null;
    }

    @Override
    public E next() {
        E currentE = currentNode.e;
        currentNode = currentNode.nextNode;
        return currentE;
    }
}

private class Node<E>{
    private E e;
    private Node<E> nextNode;
    public Node(E e, Node<E> nextNode) {
        this.e = e;
        this.nextNode = nextNode;
    }
}

}

链表实现队列

public class SugarLinkedStack<E> implements Stackable<E> ,Iterable<E>{

private Node<E> headNode;
private int count = 0;

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

@Override
public int size() {
    return count;
}

@Override
public void push(E e) {
    count++;
    headNode = new Node<>(e, headNode);
}

@Override
public E pop() {
    if(count <= 0){
        throw new IllegalStateException("please push an element firstly");
    }
    count --;

    E e = headNode.e;
    headNode = headNode.nextNode;
    return e;
}

@Override
public E peek() {
    return headNode.e;
}

@Override
public Iterator<E> iterator() {
    return new LinkedIterator(headNode);
}

private class LinkedIterator implements Iterator<E>{

    private Node<E> currentNode;

    public LinkedIterator(Node<E> currentNode) {
        this.currentNode = currentNode;
    }

    @Override
    public boolean hasNext() {
        return currentNode.nextNode != null;
    }

    @Override
    public E next() {
        currentNode = currentNode.nextNode;
        return currentNode.e;
    }
}

private class Node<E> {
    private E e;
    private Node<E> nextNode;

    private Node(E e, Node<E> nextNode) {
        this.e = e;
        this.nextNode = nextNode;
    }
}
}

小结

在实现过程中，产生了一些心得和感受，如下：

  1. 新建一个Java类，顺序是：先初始化成员变量，然后再调用它的构造方法。因此，某些场景上，一些操作是放在成员变量上还是放在构造方法里是有选择和考量的
  2. 链表这种数据结构天生包含迭代的编程思想，用递归来解决遇到的问题
  3. 数组这种数据结构使用索引访问元素（指针的使用感），操作数组序号来解决遇到的问题
  4. 用链表的实现，插入和删除元素的操作和元素数量多少没有关系。
  5. 深刻理解Iterator遍历原理，这个接口提供了集合遍历的逻辑封装，逻辑分为两个部分：hasNext方法和next方法。这两个方法合在一起产生出递归的效果，从而实现集合遍历

自制栈实践

是时候使用自己造的*了

问题表述：给出一个字符串的算术表达式，求其值。比如“((( 10 + (34 - 24))*5)-(200/11))”

思路分析：用两个栈，一个保存运算符，一个保存操作数。将操作数压入操作数栈，将运算符压入运算符栈，忽略左括号，每遇到右括号，弹出一个运算符，弹出所需数量的操作数，计算后所得结果再压入操作数栈。

代码如下：

public static void main(String[] args) {
    String expression = "((( 10 + (34 - 24))*5)-(200/11))";
    float result = calculate(expression);
    System.out.println("result = "+result);
}

private static float calculate(String expression){
    if(expression != null && expression.length() > 0){

        Stackable<String> operatorsStack = new SugarArrayStack<>();
        Stackable<Float> valueStack = new SugarLinkedStack<>();

        StringBuilder sb = new StringBuilder();

        char[] charArray = expression.toCharArray();
        for(char c : charArray){
            String s = String.valueOf(c).trim();
            switch (s){
                case "(":
                    break;
                case "+":
                case "-":
                case "*":
                case "/":
                    pushNumberValue(valueStack, sb);
                    operatorsStack.push(s);
                    break;
                case ")":
                    pushNumberValue(valueStack, sb);

                    Float firstPop = valueStack.pop();
                    String operation = operatorsStack.pop();
                    float f;
                    switch (operation){
                        case "+":
                            f = valueStack.pop() + firstPop;
                            break;
                        case "-":
                            f = valueStack.pop() - firstPop;
                            break;
                        case "*":
                            f = valueStack.pop() * firstPop;
                            break;
                        case "/":
                            f = valueStack.pop() / firstPop;
                            break;
                        default:
                            throw new IllegalArgumentException("this operator haven't been supported now");
                    }
                    valueStack.push(f);
                    break;
                default:
                    sb.append(s);
            }
        }

        return valueStack.peek();
    }

    return -1;
}

private static void pushNumberValue(Stackable<Float> valueStack, StringBuilder sb) {
    int length = sb.toString().length();
    if(length > 0){
        float value = Float.parseFloat(sb.toString());
        valueStack.push(value);
        sb.delete(0, length);
    }
}

如上例子，最终输出的结果是：

result = 81.818184

这种计算存在一些缺陷：

  • 需要左右括号包装算术表达式
  • 在一个括号里，只能进行两个操作数的计算

小结

到此，我们用自己造的栈，实现了任意长度下的四则算术运算，今天的天气也比昨天格外得好了。

参考资料

  1. 算法 Algorithms Fourth Edition By Robert Sedgewick & Kevin Wayne
标签：

相关文章