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

零、前言

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);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏琯琯博客

JavaScript 103 条技能

1、原生JavaScript实现字符串长度截取 function cutstr(str, len) { var temp; var ic...

29060
来自专栏Coco的专栏

谈谈一些有趣的CSS题目(四)-- 从倒影说起,谈谈 CSS 继承 inherit

10120
来自专栏码农阿宇

利用GDI+在Winfrom绘制验证码

string yzm; private void yangzhengma() { Bitma...

30570
来自专栏Android先生

快给你的app上锁吧(android图案解锁)

思路 这里又是一个九宫格布局,布局可以参考上一篇快给你的app上锁吧(android数字解锁),只不过这里的九宫格上我们画的是图片(bitmap)。onDraw...

32120
来自专栏Jack的Android之旅

android自定义钟表android自定义钟表

接下来就是设定这个自定义View的大小,在没有大小自适应的时候,view的高度我这位整个手机屏幕高度的三分之一,宽度为整个屏幕的宽度

10110
来自专栏游戏杂谈

as3--简单的文字提示队列

_______________________________________________________________

11320
来自专栏菩提树下的杨过

Silverlight:Mouse Avoiding 躲避鼠标效果

昨晚在一国外博客上(从域名后缀pl上猜想应该是波兰)看到这种效果(Mouse Avoid 躲避鼠标),是基于Flash/AS3开发的,这个示例把弹性运动,摩擦力...

22570
来自专栏菩提树下的杨过

Silverlight:利用Panel实现自定义布局

虽然Silverlight提供了几种基本的布局方式,比如Canvas,Grid,StackPanel,Border...,但有时候可能仍然会觉得不够用。 这时候...

22490
来自专栏Google Dart

Flutte部件目录-基本部件(三) 顶

要显示snackbar或持久底部表,请通过Scaffold.of获取当前BuildContext的ScaffoldState,然后使用ScaffoldState...

30810
来自专栏Flutter&Dart

Flutter之DataTable使用详解

57530

扫码关注云+社区

领取腾讯云代金券