美文网首页Android技术栈Android开发手机移动程序开发
看得见的数据结构Android版之栈篇

看得见的数据结构Android版之栈篇

作者: e4e52c116681 | 来源:发表于2018-11-25 08:39 被阅读3次

零、前言

1.你应该很常用到方法里边再调用方法吧，你有没有想过计算机是怎么识别的
2.你肯定能感觉到，后调用的方法总是先返回，然后在上一个方法中在继续运算
3.后进先出，现实世界看起来确实有点不公平，但在计算机世界似乎才是真理，而且作用非常大
4.本例操作演示源码：希望你可以和我在Github一同见证：DS4Android的诞生与成长，欢迎star

1.留图镇楼：栈的最终实现的操作效果:
栈操作合集.gif
2.对于栈结构的简介：
栈是一种线性的数据结构
特性：仅栈顶元素可见、后进先出LIFO
操作：push入栈 pop弹栈 peek查看栈顶元素

一、定义栈的接口：IStack

栈是一种非常简单的数据结构，方法也很少，但灵活运用还是要技巧的
个人感觉栈很纯正，简约，而不简单。

栈操作.png 
/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:12:49
 * 邮箱：1981462002@qq.com
 * 说明：栈的接口
 */
public interface IStack<T>  {
    /**
     * 栈元素个数
     * @return  栈元素个数
     */
    int size();

    /**
     * 栈元素容积
     * @return 容积
     */
    int capacity();

    /**
     * 是否为空
     * @return  是否为空
     */
    boolean isEmpty();

    /**
     * 入栈
     * @param el 元素
     */
    void push(T el);

    /**
     * 出栈
     * @return 元素
     */
    T pop();

    /**
     * 取出元素
     * @return 元素
     */
    T peek();
}

二、栈的多种实现方式

同样，栈也是抽象概念，需要去实现，本文会用前面写过的数组表和单链表分别实现栈
注：双链表与单链表实现栈基本一致,从结构的简单性来看单链表有优势一些，所以未用双链表

1.数组表栈：

其实数组表已经有栈的所有功能，这里只是实现栈接口调用一下，最底层是数组实现

/**
 * 作者：张风捷特烈
 * 时间：2018/8/17 0017:12:56
 * 邮箱：1981462002@qq.com
 * 说明：栈的数组表实现
 */
public class ArrayChartStack<T> implements IStack<T> {
    private ArrayChart<T> array;//成员变量

    public ArrayChartStack(int capacity) {
        array = new ArrayChart<>(capacity);
    }

    public ArrayChartStack() {
        array = new ArrayChart<>();
    }

    @Override
    public int size() {
        return array.size();
    }

    @Override
    public int capacity() {
        return array.capacity();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

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

    @Override
    public void push(T el) {
        array.add(el);
    }

    @Override
    public T peek() {
        return array.get(size() - 1);
    }
}

栈的push入栈：
将元素插入到栈顶，即蓝色元素(注意：栈规定----除栈顶外其他约束都是不可见和不可操作的)

push操作.gif

栈的peek查看栈顶元素：

peek操作.gif

栈的pop出栈：将栈顶的元素弹出栈

pop操作.gif
2.单链表实现栈结构：
/**
 * 作者：张风捷特烈
 * 时间：2018/11/23 0017:22:40
 * 邮箱：1981462002@qq.com
 * 说明：栈的链表式集合实现
 */
public class SingleLinkedStack<E> implements IStack<E> {

    private SingleLinkedChart<E> mSingleLinkedChart;

    public SingleLinkedStack() {
        mSingleLinkedChart = new SingleLinkedChart<>();
    }


    @Override
    public int size() {
        return mSingleLinkedChart.size();
    }

    @Override
    public int capacity() {
        return mSingleLinkedChart.size();
    }

    @Override
    public boolean isEmpty() {
        return mSingleLinkedChart.isEmpty();
    }

    @Override
    public void push(E el) {
        mSingleLinkedChart.add(el);
    }

    @Override
    public E pop() {
        return mSingleLinkedChart.remove();
    }

    @Override
    public E peek() {
        return mSingleLinkedChart.get(0);
    }
}

如果你觉得栈很简单，可以自行研究一下[用栈平衡符号]、[后缀表达式]、[递归方法调用]
这三个是栈的经典应用，以后有机会要专门写一篇来讲述，本文只限于栈结构的实现，就不引申了。

三、链表和数组表实现栈的比较

1.数组表栈：ArrayChartStack测试
方法\数量 1000次 10000次 10W次 100W次 1000W次
push 0.0011秒 0.0034秒 0.0158秒 0.0726秒 1.020秒
pop 0.0006秒 0.0025秒 0.0085秒 0.0280秒 0.1751秒
2.链表栈：SingleLinkedStack测试
方法\数量 1000次 10000次 10W次 100W次 1000W次
push 0.0005秒 0.0027秒 0.0075秒 0.3817秒 3.1550秒
pop 0.0004秒 0.0022秒 0.0050秒 0.0223秒 0.1267秒

可见低数量下链表似乎更有优势，因为一开始数组表会经常扩容，越大扩容的次数越低
在1000W次的高次数下数组表看似要优秀一点，但它实际上可能占用了更大的空间
因为如果1000W次左右进行扩容，就有500W的空白空间，而链表则不会，虽然稍慢两秒，还是可以接受的
综合来看链表实现栈结构要优秀一些。

四、视图的画法

感觉本篇挺短的，就顺带把图画一下吧

1.绘制的思路：

一开始也挺郁闷的，因为栈不能访问非栈顶元素，那单用栈是画不出底下的元素的
又想使用栈的方法进行测试，所以折中一下，用一个ArrayList跟栈同步盛放，都画出来

进入和弹出动画为了好区分，用两个ValueAnimator控制，下面是成员变量

private Point mCoo = new Point(300, 200);//坐标系
private Picture mGridPicture;//网格canvas元件
private Path mPath;//主路径
private Paint mPaint;//主画笔
private Paint mTxtPaint;//数字画笔
private Paint mBoderPaint;//路径画笔
private Paint mCtrlPaint;//几个圆的画笔

//    private IStack<StackBox<E>> mStackBoxes = new ArrayChartStack<>();//数组表栈
private IStack<StackBox<E>> mStackBoxes = new SingleLinkedStack<>();//
//用于绘制非栈顶元素(由于Stack无法获取这些元素，所以此集合辅助绘制)
private List<StackBox<E>> mUnSeeStackItemBox = new ArrayList<>();
private OnCtrlClickListener<StackView<E>> mOnCtrlClickListener;///点击监听
private ValueAnimator mInAnimator;//入栈动画
private ValueAnimator mOutAnimator;//出栈动画
private boolean canAdd = true;//是否可添加---防止多次点击添加
private static final int OFFSET_OF_TXT_Y = 10;//文字的偏移

private static final Point[] CTRL_POS = new Point[]{//控制按钮的点位
        new Point(-120, 100),//添加
        new Point(-120, 300 + 50),//移除
        new Point(-120, 500 + 100),//查看栈顶
};
private static int[] CTRL_COLOR = new int[]{//控制按钮的颜色
        0xff1EF519,//添加
        0xffB946F4,//移除
        0xff2992F2,//查看栈顶
};
private static final String[] CTRL_TXT = new String[]{//控制按钮的文字
        "push",//添加
        "pop",//移除
        "peek",//查看栈顶
};
private static final int CTRL_RADIUS = 70;//控制按钮的半径

private static final int BOTTOM_OF_STACK = 700;//控制按钮的半径
private static final int WIDTH_OF_STACK = 300;//控制按钮的半径
private static final int STACK_X = 400;//控制按钮的半径
private static final int STACK_Y = 100;//控制按钮的半径
private static final int LEN_ABOVE_STACK = 200;//控制按钮的半径
private int mCurStackTopLine = BOTTOM_OF_STACK;//当前栈顶线
2.一些成员的初始化
private void init() {
    //初始化主画笔
    mPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
    mPaint.setColor(Color.BLUE);
    mPaint.setStrokeWidth(5);
    mPaint.setTextAlign(Paint.Align.CENTER);
    mPaint.setTextSize(50);
    //初始化主路径
    mPath = new Path();
    //初始化文字画笔
    mTxtPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
    mTxtPaint.setColor(Color.WHITE);
    mTxtPaint.setTextAlign(Paint.Align.CENTER);
    mTxtPaint.setTextSize(50);
    //初始化路径画笔
    mBoderPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
    mBoderPaint.setColor(Color.BLACK);
    mBoderPaint.setStrokeWidth(4);
    mBoderPaint.setStyle(Paint.Style.STROKE);
    mGridPicture = HelpDraw.getGrid(getContext());
    //初始化圆球按钮画笔
    mCtrlPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
    mCtrlPaint.setColor(Color.RED);
    mCtrlPaint.setTextAlign(Paint.Align.CENTER);
    mCtrlPaint.setTextSize(30);
    //初始化时间流ValueAnimator
    mInAnimator = ValueAnimator.ofFloat(0, 1);
    mInAnimator.setRepeatCount(-1);
    mInAnimator.setDuration(2000);
    mInAnimator.setRepeatMode(ValueAnimator.REVERSE);
    mInAnimator.setInterpolator(new LinearInterpolator());
    mInAnimator.addUpdateListener(animation -> {
        updateBall();//更新小球位置
        invalidate();
    });
    //初始化时间流ValueAnimator---移除
    mOutAnimator = ValueAnimator.ofFloat(0, 1);
    mOutAnimator.setRepeatCount(-1);
    mOutAnimator.setDuration(2000);
    mOutAnimator.setRepeatMode(ValueAnimator.REVERSE);
    mOutAnimator.setInterpolator(new LinearInterpolator());
    mOutAnimator.addUpdateListener(animation -> {
        updateOutBall();//更新小球位置
        invalidate();
    });
}
3.核心的三个操作：

在加入ArrayList时，将StackBox的x,y坐标根据元素个数进行初始计算：
stackBox.y = STACK_Y - BOTTOM_OF_STACK + Cons.BOX_HEIGHT * mStackBoxes.size();
当添加动画开始时，直到动画暂停，都要禁用添加

/**
 * 入栈
 *
 * @param data 数据
 */
public void addData(E data) {
    if (!canAdd) {
        return;
    }
    StackBox<E> stackBox = new StackBox<>(0, 0);
    stackBox.vY = 18;
    stackBox.data = data;
    stackBox.color = ColUtils.randomRGB();
    stackBox.x = STACK_X;
    stackBox.y = STACK_Y - BOTTOM_OF_STACK + Cons.BOX_HEIGHT * mStackBoxes.size();
    mStackBoxes.push(stackBox);
    mUnSeeStackItemBox.add(stackBox);
    
    StackBox box = mStackBoxes.peek();//更新栈顶点位
    box.x = STACK_X;
    box.y = STACK_Y - LEN_ABOVE_STACK;
    mInAnimator.start();
    canAdd = false;
}
/**
 * 查看栈顶元素
 */
public E findData() {
    if (mStackBoxes.isEmpty()) {
        Toast.makeText(getContext(), "栈为空", Toast.LENGTH_SHORT).show();
    }
    if (mStackBoxes.size() > 0) {
        return mStackBoxes.peek().data;
    }
    return null;
}
/**
 * 弹栈
 */
public void removeData() {
    if (mStackBoxes.isEmpty()) {
        Toast.makeText(getContext(), "栈为空", Toast.LENGTH_SHORT).show();
    }
    if (mStackBoxes.size() > 0) {
        mOutAnimator.start();
        canAdd = false;
    }
}
4.入栈和出栈的动画

这里动态的判断和修正栈顶的位置值，这是很关键的一步

/**
 * 入栈动画
 */
private void updateBall() {
    if (mStackBoxes.size() > 0) {
        StackBox ball = mStackBoxes.peek();
        ball.x += ball.vX;
        ball.y += ball.vY;
        if (ball.y > mCurStackTopLine) {
            ball.y = mCurStackTopLine;
            mInAnimator.pause();
            mCurStackTopLine = BOTTOM_OF_STACK
                    - (mUnSeeStackItemBox.size()) * Cons.BOX_HEIGHT;//更新栈顶线
            canAdd = true;
        }
    }
}

/**
 * 出栈动画
 */
private void updateOutBall() {
    if (mStackBoxes.size() > 0) {
        StackBox ball = mStackBoxes.peek();
        ball.x += ball.vX;
        ball.y -= ball.vY;
        if (ball.y < -Cons.BOX_HEIGHT) {
            mStackBoxes.pop();
            mUnSeeStackItemBox.remove(mUnSeeStackItemBox.size() - 1);
            mOutAnimator.pause();
            mCurStackTopLine += Cons.BOX_HEIGHT;
            canAdd = true;
        }
    }
}
5.核心的绘制方法：
/**
 * 绘制栈结构
 *
 * @param canvas
 */
private void dataView(Canvas canvas) {
    mPath.moveTo(STACK_X, STACK_Y);
    mPath.rLineTo(0, BOTTOM_OF_STACK);
    mPath.rLineTo(WIDTH_OF_STACK, 0);
    mPath.rLineTo(0, -BOTTOM_OF_STACK);
    canvas.drawPath(mPath, mBoderPaint);
    mPaint.setColor(Color.GRAY);
    for (StackBox<E> box : mUnSeeStackItemBox) {
        canvas.drawRect(box.x, box.y,
                box.x + WIDTH_OF_STACK, box.y + Cons.BOX_HEIGHT,
                mPaint);
        canvas.drawRect(box.x, box.y,
                box.x + WIDTH_OF_STACK, box.y + Cons.BOX_HEIGHT,
                mBoderPaint);
        canvas.drawText((String) box.data, box.x + WIDTH_OF_STACK / 2,
                box.y + Cons.BOX_HEIGHT / 2 + 5, mTxtPaint);
    }
    mPaint.setColor(Color.BLUE);
    if (mStackBoxes.size() > 0) {
        StackBox<E> peek = mStackBoxes.peek();
        canvas.drawRect(peek.x, peek.y,
                peek.x + WIDTH_OF_STACK, peek.y + Cons.BOX_HEIGHT,
                mPaint);
        canvas.drawText((String) peek.data, peek.x + WIDTH_OF_STACK / 2,
                peek.y + Cons.BOX_HEIGHT / 2 + 5, mTxtPaint);
    }
}

本系列后续更新链接合集：(动态更新)

后记：捷文规范

2.本文成长记录及勘误表
项目源码 日期 备注
V0.1--github 2018-11-23 看得见的数据结构Android版之栈结构的实现
3.更多关于我
笔名 QQ 微信 爱好
张风捷特烈 1981462002 zdl1994328 语言
我的github 我的简书 我的掘金 个人网站
4.声明

1----本文由张风捷特烈原创,转载请注明
2----欢迎广大编程爱好者共同交流
3----个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
4----看到这里，我在此感谢你的喜欢与支持

icon_wx_200.png

相关文章

网友评论

    本文标题：看得见的数据结构Android版之栈篇

    本文链接：https://www.haomeiwen.com/subject/gmnuqqtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    Android技术栈

    Android开发

    手机移动程序开发

    Android开发

    Android进阶之路

    安卓开发博客

    数据结构和算法分析

    图解数据结构

    关于我们|服务条款|联系我们|看得见的数据结构Android版之栈篇|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！