用数组和链表实现自制的栈和队列

数组和链表是常用的两种数据结构，在翻看了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 != null;
    }

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

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<Character> operatorsStack = new SugarArrayStack<>();
        Stackable<Float> valueStack = new SugarLinkedStack<>();
        StringBuilder sb = new StringBuilder();

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

                    Float firstPop = valueStack.pop();
                    Character 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(c);
            }
        }

        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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 《C++ Primer》读书笔记
    前言 把《C++ Primer》[https://book.douban.com/subject/25708312...
    尤汐Yogy阅读 9,545评论 1赞 51
  • 面试知识点1
    Java8张图 11、字符串不变性 12、equals()方法、hashCode()方法的区别 13、...
    Miley_MOJIE阅读 3,757评论 0赞 11
  • 信仰
    我相信 爱的本质一如 生命的单纯与温柔 我相信 所有的 光与影的反射和相投 我相信 满树的花朵 只源于冰雪中的一粒...
    采兰格格阅读 162评论 0赞 0
  • 171112
    昨晚的比较直白的被拒绝，心里没有什么感觉。好像这是应该的，我知道我并不是特别喜欢这个人。之前有过放弃追求，这么久一...
    天青色_250d阅读 132评论 0赞 0
  • 燕南飞
    春来秋往，不顾疲倦，没有忧伤，冥冥之中有一种力量，抑或说是自然的规律，倒不如说是信仰，燕如人，人亦如燕
    行走的老猫阅读 280评论 0赞 3