看得见的数据结构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);
}
}举报
腾讯云开发者
